Math Help?

[Jeff Massung]

On Fri, Apr 30, 2010 at 2:15 PM, Devin Asay <devin_asay at byu.edu> wrote:

> Hi Scott,
>
> On Apr 30, 2010, at 1:05 PM, Scott Rossi wrote:
>
> > Hello List:
> >
> > Was wondering if those with more comprehensive math skills than I know
> how
> > to determine if one point X,Y falls within a triangular region defined by
> 3
> > points X1,Y1, X2,Y2, X3,Y3.  Thanks for any suggestions.
>
>

One solution to this problem is to "draw" a line from your point in any
random direction. Then count the number of line/line intersections occur
between the polygon and your imaginary line. If the number of intersections
is odd, then the point is inside. If the number of intersections is even,
then it is outside. I'll leave the line/line test as an exercise for the
reader (or someone else here), but using pseudo code:

function isPointInTriangle(pPt, pTri)
  local tLineSeg
  local tCount

  -- create a line from the point to 0,0
  put pPt & cr into tLineSeg
  put 0, 0 after tLineSeg

  -- test the intersection between our imaginary line and the triangle
  if lineIntersect(tLineSeg, line 1 to 2 of pTri) is true then add 1 to
tCount
  if lineIntersect(tLineSeg, line 2 to 3 of pTri) is true then add 1 to
tCount
  if lineIntersect(tLineSeg, line 3 of pTri & cr & line 1 of pTri) is true
then add 1 to tCount

  -- point is inside if tCount is odd
  return tCount is 1 or tCount is 3
end isPointInTriangle

function lineIntersect(pLine1, pLine2)
  -- TODO:
end lineIntersect

Note: this works for any N-sided (convex) polygon. There is the possible
edge case of the random line segment you created passing through a vertex of
the polygon. But this is solved by just picking another random line and
testing again.

Hope this helps.

Jeff M.