December 03, 2020, 08:26:26 PM

### Author Topic: [bmx] Convex Hull by Warpy [ 1+ years ago ]  (Read 413 times)

#### BlitzBot

• Jr. Member
•  • Posts: 1 ##### [bmx] Convex Hull by Warpy [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
Title : Convex Hull
Author : Warpy
Posted : 1+ years ago

Description : Suppose you have a set of points, and you want a simple polygon that will enclose them all. You might want to do this for hitboxes, or something like that. Clearly there are trivial solutions, such as a rectangle from the top-leftmost points to the bottom-rightmost points, but that leaves you a lot of empty space that isn't really inside the set.
The convex hull of a set of points is the smallest convex polygon (ie, every point on the edge can 'see' every other point on the edge, or, the polygon doesn't have any 'dents' or 'spikes' in it) containing every point in the set.
This algorithm that I found on the internet is a pretty quick way of computing the convex hull of a set of points.

Code :
Code: BlitzMax
1. Rem
2.
3. HOW IT WORKS
4.
5. Function Quickhull (takes a set of points, returns the points on the hull in clockwise order):
6. Pick a line AB which you know is a chord of the hull. The line between the leftmost and rightmost points is a suitable one.
7. Put everything to the left of AB in a set s1 , and everything to the right of AB in a set s2.
8. Then call findhull on s1 and s2, and join together the resulting lists.
9. A is the first point on the hull, then the results of findhull on s1, then B, then the results of findhull on s2.
10.
11. Function Findhull (takes a set of points sk and a line AB, returns some of the points on the hull in order)
12. Find the point C which is furthest from AB.
13. Ignore the points inside ABC as they can't be in the hull.
14. Split sk into points which are on the left of AC (called s1) and those on the right (called s2)
15. Call findhull again on s1 and AC , then on s2 and CB.
16. The list of points returned is the result of s1 plus C plus the result of s2.
17.
18.
19. EndRem
20.
21.
22. 'little type for keeping track of 2d points
23. Type point
24.         Field x#,y#
25.
26.         Function create:point(x#,y#)
27.                 p:point=New point
28.                 p.x=x
29.                 p.y=y
30.                 Return p
31.         End Function
32. End Type
33.
34. 'returns True if p1 and p2 are on the same side of the line a->b
35. Function sameside(p1x#,p1y#,p2x#,p2y#,ax#,ay#,bx#,by#)
36.         cp1# = (bx-ax)*(p1y-ay)-(p1x-ax)*(by-ay)
37.         cp2# = (bx-ax)*(p2y-ay)-(p2x-ax)*(by-ay)
38.         If cp1*cp2 >= 0 Then Return True
39. End Function
40.
41. 'Clever little trick for telling if a point is inside a given triangle
42. 'If for each pair of points AB in the triangle, P is on the same side of AB as
43. 'the other point in the triangle, then P is in the triangle.
44. Function pointintriangle(px#,py#,ax#,ay#,bx#,by#,cx#,cy#)
45.         If sameside(px,py,ax,ay,bx,by,cx,cy) And sameside(px,py,bx,by,ax,ay,cx,cy) And sameside(px,py,cx,cy,ax,ay,bx,by)
46.                 Return True
47.         Else
48.                 Return False
49.         EndIf
50. End Function
51.
52. 'Quickhull function - call this one with a set of points.
53. Function quickhull:TList(s:TList)
54.         If s.count()<=3 Return s
55.         l:point=Null
56.         r:point=Null
57.         For p:point=EachIn s
58.                 If l=Null
59.                         l=p
60.                 ElseIf p.x<l.x
61.                         l=p
62.                 EndIf
63.                 If r=Null
64.                         r=p
65.                 ElseIf p.x>r.x
66.                         r=p
67.                 EndIf
68.         Next
69.
70.         an#=ATan2(r.y-l.y,r.x-l.x)
71.         rx#=Cos(an)
72.         ry#=Sin(an)
73.         sx#=Cos(an+90)
74.         sy#=Sin(an+90)
75.
76.         s1:TList=New TList
77.         s2:TList=New TList
78.         For p:point=EachIn s
79.                 If p<>l And p<>r
80.                         mu#=(l.y-p.y+(ry/rx)*(p.x-l.x))/(sy-sx*ry/rx)
81.                         If mu<0
83.                         ElseIf mu>0
85.                         EndIf
86.                 EndIf
87.         Next
88.
89.         out1:TList=findhull(s1,l,r)
90.         out2:TList=findhull(s2,r,l)
91.         out:TList = New TList
93.         If out1
94.                 For o:Object=EachIn out1
96.                 Next
97.         EndIf
99.         If out2
100.                 For o:Object=EachIn out2
102.                 Next
103.         EndIf
104.
105.         Return out
106. End Function
107.
108. 'Findhull helper function - you never need to call this
109. Function findhull:TList(sk:TList,p:point,q:point)
110.         If Not sk.count() Return Null
111.         c:point=Null
112.         out:TList=New TList
113.         maxdist#=-1
114.         an#=ATan2(q.y-p.y,q.x-p.x)
115.         rx#=Cos(an)
116.         ry#=Sin(an)
117.         sx#=-ry
118.         sy#=rx
119.         For tp:point=EachIn sk
120.                 If tp<>p And tp<>q
121.                         mu#=(p.y-tp.y+(ry/rx)*(tp.x-p.x))/(sy-sx*ry/rx)
122.                         If maxdist=-1 Or Abs(mu)>maxdist
123.                                 c=tp
124.                                 maxdist=Abs(mu)
125.                         EndIf
126.                 EndIf
127.         Next
128.         an#=ATan2(c.y-p.y,c.x-p.x)
129.         rx#=Cos(an)
130.         ry#=Sin(an)
131.         sx#=Cos(an+90)
132.         sy#=Sin(an+90)
133.         s1:TList=New TList
134.         s2:TList=New TList
135.         For tp:point=EachIn sk
136.                 If tp<>c
137.                         If Not pointintriangle(tp.x,tp.y,p.x,p.y,q.x,q.y,c.x,c.y)
138.                                 mu#=(p.y-tp.y+(ry/rx)*(tp.x-p.x))/(sy-sx*ry/rx)
140.                         EndIf
141.                 EndIf
142.         Next
143.         out1:TList=findhull(s1,p,c)
144.         out2:TList=findhull(s2,c,q)
145.         If out1
146.                 For o:Object=EachIn out1
148.                 Next
149.         EndIf
151.         If out2
152.                 For o:Object=EachIn out2
154.                 Next
155.         EndIf
156.         Return out
157. End Function
158.
159.
160. '''DEMO Left click to place points, right click to compute hull, left click again to clear screen
161.
162. Graphics 800 , 800 , 0
163.
164. points:tlist = New tlist
165. state=0
166. While Not KeyHit(KEY_ESCAPE)
167.         For p:point = EachIn points
168.                 DrawRect p.x , p.y , 1 , 1
169.         Next
170.
171.         Select state
172.         Case 0
173.                 If MouseHit(1)
174.                         p:point = New point
175.                         p.x = MouseX()
176.                         p.y = MouseY()
178.                 EndIf
179.                 If MouseHit(2)
180.                         h:tlist = quickhull(points)
181.                         state = 1
182.                 EndIf
183.         Case 1
184.                 n = 0
185.                 ox# = - 1
186.                 oy#=-1
187.                 For p:point = EachIn h
188.                         If ox >= 0
189.                                 DrawLine ox , oy , p.x , p.y
190.                         EndIf
191.                         ox = p.x
192.                         oy = p.y
193.                         DrawText n , p.x , p.y
194.                         n:+ 1
195.                 Next
196.                 If MouseHit(1)
197.                         points = New tlist
198.                         state = 0
199.                 EndIf
200.         End Select
201.         Flip
202.         Cls
203. Wend