December 03, 2020, 08:26:26 PM

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

Offline 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
  82.                                 s1.addlast p
  83.                         ElseIf mu>0
  84.                                 s2.addlast p
  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
  92.         out.addlast l
  93.         If out1
  94.                 For o:Object=EachIn out1
  95.                         out.addlast o
  96.                 Next
  97.         EndIf
  98.         out.addlast r
  99.         If out2
  100.                 For o:Object=EachIn out2
  101.                         out.addlast o
  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)
  139.                                 If mu<0 s1.addlast tp ElseIf mu>0 s2.addlast tp
  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
  147.                         out.addlast o
  148.                 Next
  149.         EndIf
  150.         out.addlast c
  151.         If out2
  152.                 For o:Object=EachIn out2
  153.                         out.addlast o
  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()
  177.                         points.addlast(p)
  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


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal