blob: 778a9abe674a8e7adc423efd80dca737f29cd5ce (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
proc lequal {l1 l2} {
foreach elem $l1 {
if {$elem ni $l2} {
return 0
}
}
foreach elem $l2 {
if {$elem ni $l1} {
return 0
}
}
return 1
}
proc pointsFromAscii {ascii} {
set x 0
set y 0
set points [list]
foreach line [split $ascii \n] {
foreach char [split $line ""] {
if {$char == "*"} {
lappend points [list $x $y]
}
set x [+ $x 1]
}
set x 0
set y [+ $y 1]
}
return $points
}
proc testCH {name expected points} {
puts "\n$name"
set ch [region convexHull $points]
lassign $ch vertices edges
puts $edges
assert [lequal $edges $expected]
}
testCH "Empty list" \
[list] [list]
testCH "One point" \
[list [list 0 0]] [pointsFromAscii "*"]
testCH "Line" \
[list [list 0 1] [list 1 0]] \
[pointsFromAscii "* *"]
testCH "Line with point in middle" \
[list [list 0 2] [list 2 0]] \
[pointsFromAscii "* * *"]
testCH "Line with point in middle, shuffeled" \
[list [list 0 1] [list 1 0]] \
[list [list 0 0] [list 0 10] [list 0 5]]
testCH "Triangle" \
[list [list 0 2] [list 2 1] [list 1 0]] \
[pointsFromAscii "
* *
*
"]
testCH "Collinear points" \
[list [list 0 5] [list 5 2] [list 2 0]] \
[pointsFromAscii "
* * *
* *
*
"]
testCH "Triangle with bounded point" \
[list [list 1 3] [list 3 0] [list 0 1]] \
[pointsFromAscii "
*
*
*
*
"]
testCH "Square" \
[list [list 0 2] [list 2 3] [list 3 1] [list 1 0]] \
[pointsFromAscii "
* *
* *
"]
testCH "Square with bounded point" \
[list [list 0 3] [list 3 4] [list 4 1] [list 1 0]] \
[pointsFromAscii "
* *
*
* *
"]
testCH "Square with bounded point #2" \
[list [list 1 4] [list 4 3] [list 3 0] [list 0 1]] \
[pointsFromAscii "
*
*
*
*
*
"]
testCH "Pentagon" \
[list [list 1 3] [list 3 4] [list 4 2] [list 2 0] [list 0 1]] \
[pointsFromAscii "
*
*
*
*
*
"]
|
