Point Inside Polygon

[thinkertoys]

There is no way to test via script if a point is inside or outside a poly 
- 'within' will return if the point is within the rect of the poly, but 
that's about it. I recently needed such a script, explored many 
algorithms & then found a very elegant, simple and fast solution 
developed by Bob Stein in 1997 ( it's described here: 
http://www.linuxjournal.com/article.php?sid=2029 )

Below is the algorithm converted to work w/ MC/Rev - where p is the point 
to be tested and pts is the poly's points. A small demo stack ( < 20K)  
is available - just type the following into your message box:
 go stack url "http://www.cyburb.com/rev/Pt_In_Poly.rev"

function ptInPoly p, pts
  put false into inside
  put item 1 of p into xt
  put item 2 of p into yt
  put item 1 of line 1 of pts into xOld
  put item 2 of line 1 of pts into yOld
  repeat with i = 2 to the number of lines in pts
    put item 1 of line i of pts into xNew
    put item 2 of line i of pts into yNew
    if (xNew > xOld) then --flip
      put xOld into x1
      put xNew into x2
      put yOld into y1
      put yNew into y2
    else
      put xNew into x1
      put xOld into x2
      put yNew into y1
      put yOld into y2
    end if
    if (xNew < xt) = (xt <= xOld) and  ((yt-y1)*(x2-x1)) < 
((y2-y1)*(xt-x1)) then put not inside into inside
    put xNew into xOld
    put yNew into yOld
  end repeat
  return inside
end ptInPoly


Eric Holst
Thinker Toys, Inc