math problem

BlitzMax Forums/BlitzMax Programming/math problem

maverick69

(Posted 2007) [#1]

i have a list of points. i connect those points trough lines, so i get an area. now i want to check if another point is within the area of the connected points or not. any ideas how this could be solved.

here is a my code example so far:

SuperStrict

Graphics 640,480,0,60

Global Path:TPath = New TPath

Path.AddPoint(630,336)
Path.AddPoint(610,337)
Path.AddPoint(211,382)
Path.AddPoint(544,439)
Path.AddPoint(630,466)

Local check:Byte

While (Not KeyDown(KEY_ESCAPE))
	Cls
	Path.DrawPoints()
	If MouseHit(1) Then check = Path.IsPointInsideArea(MouseX(),MouseY())
	If check Then DrawText("TRUE",10,10) Else DrawText("FALSE",10,10)
	Flip
Wend

Type TPoint
	Field x:Int, y:Int
End Type

Type TPath
	Field Points:TList
	
	Method New()
		Points = CreateList()
	End Method
	
	Method IsPointInsideArea:Byte(x:Int, y:Int)
		'
		' how to check???
		'
	End Method
	
	Method AddPoint(x:Int, y:Int)
		Local p:TPoint = New TPoint
		p.x = x
		p.y = y
		ListAddLast(Points,p)
	End Method
	
	Method DebugPoints()
		For Local p:TPoint = EachIn Points
			DebugLog p.x+"/"+p.y
		Next
	End Method
	Method DrawPoints()
		Local ox:Int, oy:Int
		ox=-1
		oy=-1
		Local fx:Int, fy:Int
		For Local p:TPoint = EachIn Points
			If ox=-1 Then fx=p.x ; fy=p.y
			If ox>-1 Then DrawLine ox,oy,p.x,p.y
			ox = p.x
			oy = p.y
		Next
		DrawLine ox,oy,fx,fy
	End Method
End Type

tonyg

(Posted 2007) [#2]

It's going to be very similar to this

maverick69

(Posted 2007) [#3]

i have found this ressource on the web and tried to adapt it to blitzmax:

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

here's my attemp:

	Method CheckPoint:Byte(x:Double, y:Double)
		Local npol:Int = CountList(Points)
		Local pol:Object[] = ListToArray(Points)
		Local i:Int, j:Int, c:Byte
		j=npol-1
		For i=0 To npol-2
			j=i+1
			Local ypi:Double= TPoint(pol[i]).y
			Local xPi:Double= TPoint(pol[i]).x
			Local ypj:Double= TPoint(pol[j]).y
			Local xPj:Double= TPoint(pol[j]).x
			If ((((ypi<=y) And (y<ypj)) Or ((ypj<=y) And (y<ypi))) And (x < (xpj - xpi) * (y-ypi) / (ypj - ypi) + xpi))
				c = Not c
			End If
		Next
		Return c		
	End Method

however it doesn't work when i get close to the edges. have i implemented something wrong?

tonyg

(Posted 2007) [#4]

Was my suggestion no good?
Ok, try this which includes (among other things) a point to this

maverick69

(Posted 2007) [#5]

@tonyg: your first example didn't work with a "n" number of points...

wow the link to "convex polygon collisions and other useful functions" is great. will have a look at it. thanks!

Floyd

(Posted 2007) [#6]

Your polygon is not convex so you really need the first method you used.

The C loop is a little tricky. The variable i runs from 0 to npol-1.
j is always i-1, except for the first time through the loop when it is npol-1.

The key idea is that j=i++ sets j=i and then increments i.

	Method CheckPoint:Byte(x:Double, y:Double)
		Local npol:Int = CountList(Points)
		Local pol:Object[] = ListToArray(Points)
		Local i:Int, j:Int, c:Byte
		j=npol-1
		For i=0 To npol-1
			Local ypi:Double= TPoint(pol[i]).y
			Local xPi:Double= TPoint(pol[i]).x
			Local ypj:Double= TPoint(pol[j]).y
			Local xPj:Double= TPoint(pol[j]).x
			If ((((ypi<=y) And (y<ypj)) Or ((ypj<=y) And (y<ypi))) And (x < (xpj - xpi) * (y-ypi) / (ypj - ypi) + xpi))
				c = Not c
			End If
			j = i
		Next
		Return c		
	End Method

maverick69

(Posted 2007) [#7]

@floyd: thanks... it works with your corrected code :)