CODEWITHSUNDEEP
algorithmpolygon
Legatio
Legatio

Reputation: 319

Polygon in Polygon Algorithm

The problem is relatively simple, determine if a polygon is completely inside, completely outside, or cut by another polygon, however, the polygons may share vertices or parts of edges. First I thought just check for every vertex in polygon A if it lies inside/outside of polygon B, this fails as soon as B cuts A, see:

Left: A would be classified as outside of B

Right: A would be classified as in the inside of B

The next Idea was, check for intersections if there are any, it's classified as cut, if there are none, check for any point of A if it's inside B. This, however, fails in cases where this checked point falls on an edge of B, where it could be both, inside or outside.

So, just check the all points of A against B, until a point is found that doesn't lie on an edge of B, this, however, can also fail, if all points of A lie on edges of B, see:

Left: A should be classified as inside

Right: A should be classified as outside

So the question remains, how can you in this case without a doubt determine if polygon A lies inside or outside polygon B, if edges and vertices may be shared.

Upvotes: 0

Views: 635

Answers (2)

OmG
OmG

Reputation: 18858

If you want an algorithm, you can find two O(nlog(n)) algorithm in this article (Two efficient algorithms for determining intersection points between simple polygons) for the intersection of two simple polygones. Then, if you find that the intersection of two simple polygons is the same as one of them (order vertices and check their equalities), you will find the solution.

Moreover, you can find an implementation in python shapely package.

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

So all vertices of the green polygon lie on the boundary of the black polygon, and there are no "obvious" x-shaped edge intersections (you should have already already eliminated those; or you could insert an artificial vertex at each intersection point to reduce the problem to the below case).

First, for every vertex of either polygon that lies on the boundary of another polygon, insert an artificial vertex to the other polygon at that point (if there isn't one already there). You do that for all green vertices, and maybe some black vertices. This is needed so that all edge intersections are simple. Two edges have no common points, one common point (at their common vertex), or all common points (both vertices and everything in between; such edges are identical).

Once all intersections are simple, the problem is easy.

For all midpoints of green edges, determine if said midpoints are inside or outside of the black polygon. Discard those that are on the boundary.

If they are all inside, the green polygon is inside the black one. If all are outside, then it is NOT inside (could be outside, or the black one could be inside the green one; reverse the roles and do the procedure again to determine which is the case). If some are inside and some outside, then there's a funny intersection.

Don't have any midpoint that is not on the boundary? The two polygons are identical.

Upvotes: 1

Related Questions