Triangulation point

I read about a Euler puzzle the other day. Here’s the brief description:

Given the X/Y coordinates of three random points, use logic to confirm whether the origin (0,0) falls within the triangle defined by the three points.

At first, I struggled with this. There were some obvious examples for which the origin would not be enclosed. For example, if all three points’ X values are positive, then the origin will not be in the triangle. The same goes for three negative X coordinates, three positive Y values and three negative Y values.

But when the signs of two of the points’ X coordinates differ, and the signs of two of the points’ Y coordinates differ, how can you confirm via logic whether the origin is enclosed?

Lots of thought went into various angles of investigation, all focused on the three vertices of the triangle and their relationship to the origin. But my friend Bal suggested thinking about the edges of the triangle rather than its vertices. And we figured that:

The origin is enclosed if and only if one of the edges crossed the Y axis at a negative Y value and another edge crossed it at a positive Y value.

I need to do the maths behind this—I don’t have the inclination right now—but this has broken the problem down beautifully, allowing it to be solved simply.

Comments

2 Responses to “Triangulation point”

  1. Shanahan on January 7th, 2009 01:00

    “Compute the oriented sum of angles between the point p and each of the polygon corners. If the total oriented angle is 360 degrees, the point is inside. If the total is 0, the point is outside.”

    http://foolstr.com/theory/148

    http://www.Foolstr.com

  2. Niknej on January 7th, 2009 06:28

    I’ll take your word for it!

Leave a Reply