Got a tip for us?
Let us know
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
macOS question for the geometry folks
- Thread starter wala
- Start date
- Sort by reaction score
Here's a way. It's based on the idea of a point being to the left or right of a line (or directly on it). If you think of a line formed from two points starting at one point and traveling toward the second point, then another point could be:
1. To the left of the line.
2. To the right of the line.
3. Directly on the line.
For a triangle, there are three lines formed. If you think about going around the triangle, from point to point in one direction, a point is inside the triangle if it is either to the right of all three lines, or to the left of all three lines. And it turns out to be easy to compute if a point is to the left, right, or on a line formed by two points:
Given the line formed by points (v0.x, v0.y) and (v1.x, v1.y), and the point (p.x, p.y) you compute this value:
d = (v1.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.x)
if d is greater than zero, p is to the right of the line. If d is less than zero, p is to the left of the line. And if d is zero, then the point is on the line. So you can do the computation for all three sides of the triangle formed by v0, v1, and v2:
d0 = (v1.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.x)
d1 = (v2.x-v1.x) * (p.y-v1.y) - (v2.y-v1.y) * (p.x-v1.x)
d2 = (v0.x-v2.x) * (p.y-v2.y) - (v0.y-v2.y) * (p.x-v2.x)
now, if (d0 < 0 and d1 < 0 and d2 < 0) or (d0 > 0 and d1 > 0 and d2 > 0) then the point is in the triange.
If you want to count being on the edge of the triangle as being in it, then you would use (d0 <= 0 and d1 <= 0 and d2 <= 0) or (d0 >= 0 and d1 >= 0 and d2 >= 0).
In C++ code:
Would work as well using double or float in place of int.
1. To the left of the line.
2. To the right of the line.
3. Directly on the line.
For a triangle, there are three lines formed. If you think about going around the triangle, from point to point in one direction, a point is inside the triangle if it is either to the right of all three lines, or to the left of all three lines. And it turns out to be easy to compute if a point is to the left, right, or on a line formed by two points:
Given the line formed by points (v0.x, v0.y) and (v1.x, v1.y), and the point (p.x, p.y) you compute this value:
d = (v1.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.x)
if d is greater than zero, p is to the right of the line. If d is less than zero, p is to the left of the line. And if d is zero, then the point is on the line. So you can do the computation for all three sides of the triangle formed by v0, v1, and v2:
d0 = (v1.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.x)
d1 = (v2.x-v1.x) * (p.y-v1.y) - (v2.y-v1.y) * (p.x-v1.x)
d2 = (v0.x-v2.x) * (p.y-v2.y) - (v0.y-v2.y) * (p.x-v2.x)
now, if (d0 < 0 and d1 < 0 and d2 < 0) or (d0 > 0 and d1 > 0 and d2 > 0) then the point is in the triange.
If you want to count being on the edge of the triangle as being in it, then you would use (d0 <= 0 and d1 <= 0 and d2 <= 0) or (d0 >= 0 and d1 >= 0 and d2 >= 0).
In C++ code:
Code:
bool isPointInsideTriangle(int px, int py, int v0x, int v0y, int v1x, int v1y, int v2x, int v2y)
{
int d0 = (v1x-v0x) * (py-v0y) - (v1y-v0y) * (px-v0x);
int d1 = (v2x-v1x) * (py-v1y) - (v2y-v1y) * (px-v1x);
int d2 = (v0x-v2x) * (py-v2y) - (v0y-v2y) * (px-v2x);
return (d0 < 0 && d1 < 0 && d2 < 0) || (d0 > 0 && d1 > 0 && d2 > 0);
}