Polygon-in-polygon testing

The picture shows some counterexamples, including one that shows the problem is not even as easy as checking that all vertices of one polygon are inside the other polygon.

One possible approach would be to check that none of the sides of the two polygons intersect and that one vertex is inside.

See for example: https://stackoverflow.com/a/4833823

enter image description here


Let $p_1$ be the quadrilateral with vertices $(1,0), (0,1), (-1,0), (0,-1)$. Then your conditions are for the bounding box $b$ of $p_1$, not for $p_1$ itself. In particular, a small $p_0$ fits in one corner of $b$ but is completely outside $p_1$.

It is not even sufficient to use a point-in-polygon algorithm to test whether the vertices of $p_0$ are all inside $p_1$ because $p_1$ might not be convex.

The only general way is to check that their union is $p_1$. For that you may need a polygon clipping tool like gpc. See also the Weiler–Atherton clipping algorithm and boolean operations on polygons.


No, this doesn't work at all.

enter image description here

This bounding box test guarantees that the polygons are disjoint, when the boxes are disjoint. Otherwise it says nothing.

A relatively simple and correct test is to check that there are no pairwise side intersections, which is done by exhaustive segment-segment intersection tests. Then either the polygons are disjoint or one wholly included in the other. You make the final decision by taking some vertex and applying a point-in-polygon test wrt the other polygon.

If you are after an efficient solution, you can resort to a sweepline algorithm, during which you sweep an horizontal line across all vertices and maintain a list of the horizontal segments the polygons are cutting. Then you reduce to a 1D segment containment problem.

Tags:

Geometry

Polygons

Algorithms

Related

Why is eigendecomposition $V \Lambda V^{-1}$ not $V^{-1} \Lambda V$ Minimum value of $\frac{x}{y^2}+\frac{y}{z^2}+\frac{z}{x^2}$ What is the maximum even number that can not be expressed as sum of two composite odd numbers? Use Fourier series of odd function to evaluate $1-\frac15+\frac17-\frac1{11}+\cdots$ Show that $a+b+c+\sqrt {\frac {a^2+b^2+c^2}{3}}\le4$, Show that $\prod_{k=1}^n \left(\prod_{j=1}^k\frac{k}{j}\right)$ is always an integer. How to find range of a rational function? Half-full cone of water Fractional part of $1+\frac{1}{2}+\dots+\frac{1}{n}$ dense in $(0,1)$ Integrate functions from point 'a' to point 'a' proof How can we tackle this integral $\int_{0}^{1}{2x^2-2x+\ln[(1-x)(1+x)^3]\over x^3\sqrt{1-x^2}}\mathrm dx=-1?$ Is there a coordinate system where a point is defined with two angles?

Recent Posts