November 28, 2020, 02:04:47 AM

Author Topic: [bmx] Point inside convex polygon by Warpy [ 1+ years ago ]  (Read 614 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Point inside convex polygon
Author : Warpy
Posted : 1+ years ago

Description : Normally it's quite difficult to tell if a point is inside an arbitrary polygon. For a concave polygon, or one with holes in, the <a href="http://www.blitzmax.com/codearcs/codearcs.php?code=2037" target="_blank">scanning method[/url] is the way to go.
But when you've got a convex polygon, things get a lot easier! Remember that the definition of a convex polygon is "A polygon such that every line segment between two vertices of the polygon does not go exterior to the polygon (i.e., it remains inside or on the boundary of the polygon)."
We can use this fact to split a convex polygon into a fan of triangles, originating from one of its vertices. Then the point is inside the polygon if and only if it is inside one of the triangles, which is easy to check with a little bit of <a href="http://www.blitzmax.com/codearcs/codearcs.php?code=1992" target="_blank">maths[/url].

Remember that this only works on a *convex* polygon, not just any one, so only use it when you know you've got one, such as a <a href="http://www.blitzmax.com/codearcs/codearcs.php?code=2050" target="_blank">convex hull[/url].


Code :
Code: BlitzMax
  1. 'little type for keeping track of 2d points
  2. Type point
  3.         Field x#,y#
  4.        
  5.         Function create:point(x#,y#)
  6.                 p:point=New point
  7.                 p.x=x
  8.                 p.y=y
  9.                 Return p
  10.         End Function
  11. End Type
  12.  
  13. 'returns True if p1 and p2 are on the same side of the line a->b
  14. Function sameside(p1x#,p1y#,p2x#,p2y#,ax#,ay#,bx#,by#)
  15.         cp1# = (bx-ax)*(p1y-ay)-(p1x-ax)*(by-ay)
  16.         cp2# = (bx-ax)*(p2y-ay)-(p2x-ax)*(by-ay)
  17.         If cp1*cp2 >= 0 Then Return True
  18. End Function   
  19.        
  20. 'Clever little trick for telling if a point is inside a given triangle
  21. 'If for each pair of points AB in the triangle, P is on the same side of AB as
  22. 'the other point in the triangle, then P is in the triangle.
  23. Function pointintriangle(px#,py#,ax#,ay#,bx#,by#,cx#,cy#)
  24.         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)
  25.                 Return True
  26.         Else
  27.                 Return False
  28.         EndIf
  29. End Function
  30.  
  31. 'returns True if (x,y) is inside convex polygon defined by list of points
  32. 'points must be in clockwise (or anticlockwise) order.
  33. 'won't work for just any polygon!
  34. 'Works by splitting polygon into triangles, and checking each of those
  35. Function pointinside(x# , y# , points:tlist)
  36.         p1:point = Null
  37.         p2:point = Null
  38.         For p:point = EachIn points
  39.                 If p1
  40.                         If p2
  41.                                 If pointintriangle(x , y , p1.x , p1.y , p2.x , p2.y , p.x , p.y)
  42.                                         Return True
  43.                                 EndIf
  44.                         EndIf
  45.                         p2=p
  46.                 Else
  47.                         p1 = p
  48.                 EndIf
  49.         Next
  50.         Return False
  51. End Function


Comments :


Jesse(Posted 1+ years ago)

 I have been using This point in poly function:<a href="http://www.darwin3d.com/gamedev/articles/col0199.pdf" target="_blank">http://www.darwin3d.com/gamedev/articles/col0199.pdf[/url]when I get a chance I will test and compare  both codes. If its  significantly faster (wich I am almost shure it is) I will add it to my library.  Thanks for sharing.


Warpy(Posted 1+ years ago)

 As far as I can tell, that's just talking about general polygons again?


Jesse(Posted 1+ years ago)

 Yes, I am not disputing that. There are three sample c programs that illustrate what is being explained. I have converted them to bmax and I am using them in my library. they work efficiently well for my purpose I am also using the npoly lib made in blitzbasic which I have adopted and modified for my personal use.  I am not trying to discredit you. I think your example is a great alternative to the said code.  I am not a great programmer nor am I trying to reinvent the wheel, I want some code that will prevent me from wasting hours/days by the computer trying to solve. so I leave my doors open to alternative and/or better solutions. I apreciate your sharing so that people like me can leach :). And yes I have contributed. not much of a discovery but stuff I had problems with and figured out. may be usefull for somebody. "I will not give up with out a fight!"


Warpy(Posted 1+ years ago)

 Yeah of course, I just thought I was missing something simple there!


spacerat(Posted 1+ years ago)

 This seems to be working fine for the concave polygon I just tested it with. Perhaps it works sometimes for concave polygons, but not reliably for all of them.


Warpy(Posted 1+ years ago)

 Yep, that's true.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal