Given four pairs of coordinates, three of them describing the vertices of a triangle on a plane, is it possible to determine whether the point described by the fourth pair is inside or outside the triangle figure?
Also, How about a point within a quadrilateral described by its four vertices?
Yes it is.
Is the question really “what’s the most efficient algorithm for determining the answer analytically”?
(Pairs of coordinates?)
Brought to you by the department of redundancy department.
Here’s the method I’ve used, which is similar to the one Desmostylus gives. I don’t know which one I like better yet…
Draw the vectors PA, PB, and PC. Take the three cross products PA × PB, PB × PC, and PC × PA. For each of these three vectors, take the dot product with the the perpendicular vector to the plane*. This will give you three scalars. If they all have the same sign, P is inside triangle ABC. If one of them has a different sign, it’s outside. If one or more has a value of 0, then P is on the triangle.
This method should also work with a convex n-gon. You just have to take n cross products and n dot products. For a non-convex n-gon, though, it gets tricky. Quadrilaterals should be okay, however.
Here’s the C++ code I wrote for it, by the way. In this case, the points are all in the x-y plane, so the perpendicular to the plane is in the z-direction. So, instead of dot products, I just take the z-component:
int Within(vect2d Omega, vect2d Alpha, vect2d Beta, vect2d Gamma) {
vect3d A = Alpha, B = Beta, C = Gamma, Z = Omega;
if ((((A - Z) * (B - Z)).z > 0)
!= (((A - C) * (B - C)).z > 0)) return 0;
if ((((B - Z) * (C - Z)).z > 0)
!= (((B - A) * (C - A)).z > 0)) return 0;
if ((((C - Z) * (A - Z)).z > 0)
!= (((C - B) * (A - B)).z > 0)) return 0;
return 1;
}
Actually, I think I might take that back; a coordinate is one member of a set of numbers, a single coordinate is required to describe a point on a one-dimensional line, but to describe a point on a 2D plane, a pair of coordinates is required.
Freakin’ spacing.
Area of a triangle can be found using the determinant:
A = abs(1/2 * |x1 y1 1| )
|x2 y2 1|
|x3 y3 1|
Note that it’s entirely possible for a quadrilateral to be concave, so you have to be careful about extending this method.
You’re right about that. I was thinking parallelogram, for some reason. For a general quadrilateral, you can divide it up into two triangles, and test point P for both of them. This is not as simple as it sounds, however. If you split quadrilateral ABCD into triangles ABC and CDA, for instance, you must test B to make sure it’s not inside triangle CDA, and D to make sure it’s not inside triangle ABC. If either of those tests fails, you can use triangles BCD and DAB instead. At any rate, even if your 4-gon is convex, you run the risk of P lying on the dividing line between your two triangles.
Um, if P is a vertex of the triangle, that would be screamingly obvious from the original conditions.
Speaking of which, and not to deflate any of the sound methods described above, but wouldn’t it be way, way, way easier just to graph the system and inspect it? If the point shows up too close to one of the lines in your sketch, find the equation for the line in slope-intercept form and test the point for <, > or =. Seems like less work to me, and 100% reliable.
It would if there can be any sort of rigorous method of defining ‘close to’ - I’m looking for methods that could be efficiently implemented by a computer program.
It is also possible for a set of four coordinate pairs to produce not a quadrilateral, but a figure that looks like a pair of triangles joined at the vertices (sort of hourglass shaped).
No, that’s getting silly. You’re looking for interior points. If you’re going to say that five points could define a pentagram rather than a pentagon, then there’s no solution to your question.
What I said to Achernar about the possibility of concavity in a quadrilateral referred to an “arrowhead” or a “chevron” shape. Not an “hourglass” shape. Minimum circumfrence or minimum perimeter is the criterion.
I don’t see how that’s possible, given that the shape you describe requires five points.
That is rather a bold statement and I don’t feel that the question is a silly one; given a set of points and instructed to link them one to the next (and back to the start) in a given order, surely it must be possible to detect closed polygons produced…
No it doesn’t; the central point that appears as two linked vertices is not described - they are coincidental to the fact that two of the lines have crossed (like this)
OK. Given an ordered set of n points, it’s possible to determine whether the area enclosed by the polyline connecting those points includes a given point P. That wasn’t the OP.
It might help, Mange, if you provided a few more details about the problem you’re trying to solve.
Ah, gotcha. But allowing lines to cross opens up a whole new can of worms, doesn’t it?
Nothing related to any specific project, just something that I have idly wondered about from time to time. I probably should have defined the question a little more clearly, sorry.
