Math Help?

[Jeff Massung]

On Fri, Apr 30, 2010 at 2:38 PM, Jeff Massung <massung at gmail.com> wrote:

> 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:
>


And just because I do this kind of work professionally and fun (yes, I'm
weird), another option open to you is to treat each line in the triangle as
a plane and test to see which side of the line your point happens to fall
on. You do this with each line segment in the triangle and if the sign of
the result is ever negative then the point is outside the triangle,
otherwise it's inside. This requires doing some dot product math (trivial),
though...

Given a line segment AB, and a point C, take the dot product of AC * AB:

dot = [(B-A).x * (C-A).x] + [(B-A).y * (C-A).y]

The dot product (of two, normalized vectors) will give you the cosine of the
angle between them. You actually don't care about the cosine, but the cosine
of [0,90] will be >= 0 and the cosine of (90,180] will be < 0. That's all
you care about.

So, if you have a triangle made up of points A,B,C and a random point D, you
can do:

dot[0] = AD * AB
dot[1] = BD * BC
dot[2] = CD * CA

If any of those dot products are negative, then the point is outside the
triangle. If all of them are positive, then the point is inside the
triangle.

This is all from memory really fast, though, it's possible that I got the
signs flipped (negative = inside and positive = outside), but that's easy
enough to test and fix.

Cheers,

Jeff M.