Point inside poly

This code has been declared by its author to be Public Domain code.

Point inside poly by _JIM

2009

Find out if a point is inside a polygon in a really fast way

'Finds out if a point is on the left or right side of a segment
Function LineIntersectOX(lx1:Float, ly1:Float, lx2:Float, ly2:Float, px:Float, py:Float)
	Local newpx:Float
	
	If ((ly1 < py) And (ly2 > py) ..
		Or (ly1 > py) And (ly2 < py)) And (lx1 > px) And (lx2 > px)
		Return True
	End If
	
	Local b = ((ly1 <= py) And (ly2 >= py)) Or ((ly1 >= py) And (ly2 <= py))
	If (b = False)
		Return False
	EndIf
	
	'Thanks to Nate the Great
	If ly2 = ly1 Then
		Return False
	Else	
		newpx = ((py - ly1) / (ly2 - ly1)) * (lx2 - lx1) + lx1
		If (px < newpx) Return True
	EndIf
	Return False
End Function

'finds out if a point is inside a polygon
Function PointInPoly(px:Float, py:Float, poly:Float[])
	Local i:Int
	Local sum:Int

	For i = 0 To Int(poly.length / 2) - 2
		Local p1x:Float = poly[i * 2]
		Local p1y:Float = poly[i * 2 + 1]
		Local p2x:Float = poly[(i + 1) * 2]
		Local p2y:Float = poly[(i + 1) * 2 + 1]
		
		sum:+LineIntersectOX(p1x, p1y, p2x, p2y, px, py)
	Next
	
	If (poly.length > 4)
		Local p1xd:Float = poly[0]
		Local p1yd:Float = poly[1]
		Local p2xd:Float = poly[poly.length - 2]
		Local p2yd:Float = poly[poly.length - 1]
		
		sum:+LineIntersectOX(p1xd, p1yd, p2xd, p2yd, px, py)
	End If
	
	Return sum Mod 2
End Function

Comments

Nate the Great

2009

thanks! this works great except one thing

when I run this code after about a minute, it randomly says untitled1.exe has stopped working...

Graphics 640,480,0,60

While Not KeyDown(key_escape)
Cls


DrawLine 340,234,123,456
DrawLine 340,234,200,100
DrawLine 100,100,200,100
DrawLine 123,456,100,100

Local poly:Float[] = [340.0,234.0,123.0,456.0,100.0,100.0,200.0,100.0]

If pointinpoly(MouseX(),MouseY(),poly) Then
	SetColor 255,0,0
Else
	SetColor 255,255,255
EndIf


Flip
Wend

'Finds out if a point is on the left or right side of a segment
Function LineIntersectOX(lx1:Float, ly1:Float, lx2:Float, ly2:Float, px:Float, py:Float)
	Local newpx:Float
	
	If ((ly1 < py) And (ly2 > py) ..
		Or (ly1 > py) And (ly2 < py)) And (lx1 > px) And (lx2 > px)
		Return True
	End If
	
	Local b = ((ly1 <= py) And (ly2 >= py)) Or ((ly1 >= py) And (ly2 <= py))
	If (b = False)
		Return False
	EndIf
	
	newpx = ((py - ly1) / (ly2 - ly1)) * (lx2 - lx1) + lx1
	If (px < newpx) Return True
	Return False
End Function

'finds out if a point is inside a polygon
Function PointInPoly(px:Float, py:Float, poly:Float[])
	Local i:Int
	Local sum:Int

	For i = 0 To Int(poly.length / 2) - 2
		Local p1x:Float = poly[i * 2]
		Local p1y:Float = poly[i * 2 + 1]
		Local p2x:Float = poly[(i + 1) * 2]
		Local p2y:Float = poly[(i + 1) * 2 + 1]
		
		sum:+LineIntersectOX(p1x, p1y, p2x, p2y, px, py)
	Next
	
	If (poly.length > 4)
		Local p1xd:Float = poly[0]
		Local p1yd:Float = poly[1]
		Local p2xd:Float = poly[poly.length - 2]
		Local p2yd:Float = poly[poly.length - 1]
		
		sum:+LineIntersectOX(p1xd, p1yd, p2xd, p2yd, px, py)
	End If
	
	Return sum Mod 2
End Function

edit: it only happens when your mouse is even with the top two verticies...

Nate the Great

2009

ok here's a solution -

'Finds out if a point is on the left or right side of a segment
Function LineIntersectOX(lx1:Float, ly1:Float, lx2:Float, ly2:Float, px:Float, py:Float)
	Local newpx:Float
	
	If ((ly1 < py) And (ly2 > py) ..
		Or (ly1 > py) And (ly2 < py)) And (lx1 > px) And (lx2 > px)
		Return True
	End If
	
	Local b = ((ly1 <= py) And (ly2 >= py)) Or ((ly1 >= py) And (ly2 <= py))
	If (b = False)
		Return False
	EndIf
	
	If ly2 = ly1 Then
		Return False
	Else	
		newpx = ((py - ly1) / (ly2 - ly1)) * (lx2 - lx1) + lx1
		If (px < newpx) Return True
	EndIf
	Return False
End Function

'finds out if a point is inside a polygon
Function PointInPoly(px:Float, py:Float, poly:Float[])
	Local i:Int
	Local sum:Int

	For i = 0 To Int(poly.length / 2) - 2
		Local p1x:Float = poly[i * 2]
		Local p1y:Float = poly[i * 2 + 1]
		Local p2x:Float = poly[(i + 1) * 2]
		Local p2y:Float = poly[(i + 1) * 2 + 1]
		
		sum:+LineIntersectOX(p1x, p1y, p2x, p2y, px, py)
	Next
	
	If (poly.length > 4)
		Local p1xd:Float = poly[0]
		Local p1yd:Float = poly[1]
		Local p2xd:Float = poly[poly.length - 2]
		Local p2yd:Float = poly[poly.length - 1]
		
		sum:+LineIntersectOX(p1xd, p1yd, p2xd, p2yd, px, py)
	End If
	
	Return sum Mod 2
End Function

this is amazingly fast! ~2 ms for 10,000 calls

_JIM

2009

Ooops, guess I missed that error :)

Thanks for fixing it and glad you find it usefull (or at least fast :) )

EDIT: The code is now fixed

Code Archives Forum