November 28, 2020, 02:04:47 AM

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

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] Point inside convex polygon by Warpy [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
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

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.