Taken right out of "Computer Graphics Handbook, Geometry and Mathematics" by Michael E. Mortenson:
Given a test point P
t determine if it is inside, outside, or on the boundary of a polygon (convex or concave). Do this in two steps:
1. Using the polygon vertex points, find the min-max box.
i. If P
t is not inside the min-max box, then it is not inside the polygon.
ii. If P
t is inside, proceed to the next step.
2. Compute the intersection of y=y
t with the edges of the polygon. Consider only the edges whose end points straddle y
t. Count intersections with a vertex as two. There are always an even number of intersections. Pair the x coordinates of the intersections in ascending order; for example, (x
1, x
2) (x
3, x
4), and so on. Then:
i. If x
t falls inside an interval, for example x
1 < x
t > x
2, then P
t is inside the polygon.
ii. If x
t is identically equal to on of the interval limits, then P
t is on the boundary.
iii. Otherwise P
t is outside the polygon.
So I did that:
;;Determines if a point is inside a polygon defined by an ordered list of points.
;;Return 1 if point is inside the boundary, 2 if it is on the boundary and nil otherwise.
;;Only works for 2D points, if 3D points are supplies, the Caddr is ignored and
;;it will give unpredictable results...well, it already gives unpredictable results, so nevermind.
(Defun PointInsidePolygonP ( PNT lstPOINTS FUZZ / dXmin dXmax pntXs pntXe pntTest lstTest lstPairs cnt )
(Cond
((< (Car PNT) (SetQ dXmin (Apply (Function Min) (MapCar (Function Car) lstPOINTS))))
nil
)
((> (Car PNT) (SetQ dXmax (Apply (Function Max) (MapCar (Function Car) lstPOINTS))))
nil
)
((< (Cadr PNT) (Apply (Function Min) (MapCar (Function Cadr) lstPOINTS)))
nil
)
((> (Cadr PNT) (Apply (Function Max) (MapCar (Function Cadr) lstPOINTS)))
nil
)
(T
(SetQ pntXs (List dXmin (Cadr PNT))
pntXe (List dXmax (Cadr PNT))
lstPOINTS (Cons (Car lstPOINTS) (Reverse lstPOINTS)) ;add fisrt point to the front of the revered list
cnt 0
)
(Repeat (1- (Length lstPOINTS))
(If (SetQ pntTest (Inters (Nth cnt lstPOINTS) (Nth (1+ cnt) lstPOINTS) pntXs pntXe)) ;segment intersects test line
(SetQ lstTest (Cons pntTest lstTest) ) ;add it once
)
(SetQ cnt (1+ cnt) )
)
(SetQ lstTest (VL-Sort (MapCar (Function Car) lstTest) (Function <)) ) ;sort list of x coords
(Repeat 2 ;strip duplicates from front and back
(If (Equal (Car lstTest) (Cadr lstTest) FUZZ)
(SetQ lstTest (Cdr lstTest) )
)
(SetQ lstTest (Reverse lstTest) )
)
(While lstTest ;make list of pairs
(SetQ lstPairs (Cons (List (Car lstTest) (Cadr lstTest)) lstPairs) )
(SetQ lstTest (Cddr lstTest) )
)
(SetQ lstPairs (Reverse lstPairs) )
(Cond
((Or (VL-Member-If (Function (Lambda (l) (Equal (Car PNT) l FUZZ))) (MapCar (Function Car) lstPairs))
(VL-Member-If (Function (Lambda (l) (Equal (Car PNT) l FUZZ))) (MapCar (Function Cadr) lstPairs))
)
2
)
((VL-Member-If (Function (Lambda (l) (And (> (Car PNT) (Car l)) (< (Car PNT) (Cadr l))))) lstPairs)
1
)
(T
nil
)
)
)
)
)
(Defun GetPolylinePoints ( POLY / entPoly lstReturn )
(SetQ entPoly (EntGet POLY) )
(SetQ lstReturn (List (Cdr (Assoc 10 entPoly))) )
(While (Assoc 10 (SetQ entPoly (Cdr (Member (Assoc 10 entPoly) entPoly))) )
(SetQ lstReturn (Cons (Cdr (Assoc 10 entPoly)) lstReturn) )
)
(Reverse lstReturn )
)
(Defun C:TestME ( / ePolyLine pntPick )
(SetQ ePolyLine (Car (EntSel "Pick a Polyline")) )
(SetQ pntPick (GetPoint "Pick a Point") )
(PointInsidePolygonP pntPick (GetPolylinePoints ePolyLine) 0.00001 )
)
At first I had tested to see if the line straddles the test line like this:
(And (Or (And (< (Cadr (Nth cnt lstPOINTS)) (Cadr PNT))
(> (Cadr (Nth (1+ cnt) lstPOINTS)) (Cadr PNT) )
)
(And (> (Cadr (Nth cnt lstPOINTS)) (Cadr PNT))
(< (Cadr (Nth (1+ cnt) lstPOINTS)) (Cadr PNT) )
)
) ;segment straddles test line
(SetQ pntTest (Inters (Nth cnt lstPOINTS) (Nth (1+ cnt) lstPOINTS) pntXs pntXe) ) ;segment intersects test line
)
)
..but it was throwing out points when the test line intersected a vertex, so I threw it out. Then I had it determine if the test point was on one of the vetices like this:
(If (Or (Equal pntTest (Nth cnt lstPOINTS) FUZZ)
(Equal pntTest (Nth (1+ cnt) lstPOINTS) FUZZ)
) ;test point is on a vertex
(SetQ lstTest (Cons pntTest lstTest) ;add it twice
lstTest (Cons pntTest lstTest)
)
(SetQ lstTest (Cons pntTest lstTest) ) ;add it once
)
...but the intersection of the two line segments at the vertex were returning two points already, so I threw that out also.
Now here is the problem: if the test line intersects a vertex of the polygon, it adds two points to lstTest. However, if the vertex is on a boudary between an area that is in and an area that is out, it needs to be only one point. At first I thaught to strip the pairs that occur at the start and the end of the test line, but that is not nessicarilly valid either. here are some examples:
should be two points
should be one point
should be two points
Basically, if both line segments are on one side of the test line then it should be two points, otherwise it should be one. This would probably get ugly it the polygon went horizontal for a while and one segment was colinear with the test line.
..Any ideas?
(also, on a side note: this is my first post, I finally found this place after walking around in the wilderness for months after Cadvault died. I'm very glad to be here. this type of forum is very important to me and I appreciate all of you. I have taken a few days to look around and get familliar with the swamp and I've already seen some names I recognize. It's good to be back.
On with the LiSPing!!)