0

The problem: given vertices that define a polygon, determine whether another point $P$ lies inside the polygon or not.

Proposed solution: suppose we have a triangle $A, B, C$. Calculate the areas of the triangles that $P$ forms with the other points: $PAB, PBC, PAC$. Iff $P$ lies inside the triangle, then $\text{area}(PAB) + \text{area}(PBC) + \text{area}(PAC) = \text{area}(ABC)$.

I found this method described here, and it seems to work for any polygon. Is this the case? If so, is there a reference? I can't find it listed as any of the common solutions to this problem.

Eli Rose
  • 8,141
  • "fourth point" -- so your polygon is a triangle? – Eric Towers Sep 10 '19 at 00:25
  • 1
    Your polygon is convex? If not: even if $P$ is inside and $AB$ is one of the edges, it could be that $PA$ and/or $PB$ lies partly outside – GEdgar Sep 10 '19 at 00:33
  • For a triangle, if you’re careful about the order of the vertices you can compare signs of determinants instead. – amd Sep 10 '19 at 01:19

1 Answers1

1

Sure; that works. But you have to be sure to take the area rather than the signed area, which may mean throwing in an absolute value. It's far more efficient to test that for each vertex U, your fourth point X lies on the same side of the edge not containing U as does U. So if U = A, then you test U against BC and X against BC, and if the signs match, you're good. Repeat for the other two edges.

If you have millions of points to test as your "fourth point" while the triangle remains constant, you can win big by doing some precomputation. Tomas Akenine-Moller has written many papers on this subject, and they're probably the best thing out there.

John Hughes
  • 93,729
  • Thanks! Does this method work even for concave polygons? – Eli Rose Sep 10 '19 at 16:36
  • 1
    Well, since your question asked about triangles, that's what I answered. When you changed the question, it made my answer look stupid. When you ask "does 'this method' work?", it's not clear whether you mean your area-based method or Moller's triangle-test approach. I suppose it doesn't really matter -- neither (as described) works. – John Hughes Sep 10 '19 at 23:20
  • The real secret sauce is to compute the linking number of a 0-sphere (your test point, plus a point at infinity) with the polygon. If that's 0, the point is outside; if it's $\pm 1$, the point's inside. If the computation blows up, it's on an edge. And if it's something other than $0, \pm 1$, then your polygon's not simple. – John Hughes Sep 10 '19 at 23:21