Check Whether a Polygon "Fits into" a 2-D Triangular Mesh

Question

Suppose there is a polygon $\mathcal{P}\subset\mathbb{R}^2$ and a set of triangles $\mathcal{T}\equiv\{T_i\}_i$ that partitions $\mathcal{P}$. My question is, given any polygon $\mathcal{Q}\subset \mathcal{P}$, is there any algorithm (other than exhaustive searching) to determine whether there exists a set $\{T_{i_j}\}_j\subset \mathcal{T}$ such that $$ \mathcal{Q} = \bigcup_j T_{i_j}? $$ Any help or hint will be greatly appreciated!

Answer 1

(Note: $\mathcal{P}$ and $\mathcal{Q}$ are supposed to be convex polygons with a non-empty interior, and all triangles in $\mathcal{T}$ to have a non-empty interior, too. It may be that the method proposed below still works for other cases, but I have not checked).

"$\mathcal{Q}$ is the union of triangles from $\mathcal{T}$" is equivalent to "all true $\mathcal{Q}$ vertices are vertices from triangles in $\mathcal{T}$, and edges of $\mathcal{Q}$ are covered by edges in $\mathcal{T}$".

By "true vertex", here I mean a vertex where the two adjoint edges are non-aligned. Said otherwise, if the vertex can be suppressed without changing the polygon interior, it is a false vertex. So it may be necessary to first remove false vertices from $\mathcal{Q}$.

Then the check step 1 consists in searching for each $\mathcal{Q}$ vertex in $\mathcal{T}$ vertices. To do this efficiently:

• First sort all $\mathcal{T}$ vertices. Use for that any total order on $\mathbb{R}^2$; it does not need to be continuous, so it could be: sort according to first coordinate, if equal then sort according to second coordinate$^{(1)}$. Complexity of this sorting is $n \log (n)$, if there are $n$ vertices in triangles of $\mathcal{T}$.
• Then look for each vertex of $\mathcal{Q}$ in the sorted list. Each lookup has complexity $\log(n)$, so if $\mathcal{Q}$ has $q$ vertices, complexity is $q \log(n)$.

The step 2 consists in checking that $\mathcal{Q}$'s edges are covered by $\mathcal{T}$'s edges. For this:

• Take a vertex in $\mathcal{Q}$, and the identical vertex in $\mathcal{T}$ (call it $A$).
• Take the neighbour vertex in $\mathcal{Q}$ and the identical vertex in $\mathcal{T}$ (call it $B$). Check these two vertices of $\mathcal{T}$ are linked by an edge in $\mathcal{T}^{(2)}$.
• If they are not, explore in turn all neighbour vertices of $A$ in $\mathcal{T}$. If none of them is in the right direction, $\mathcal{Q}$ is not made of triangles. If one of them is in the right direction (as triangles are assumed to be non-flat, there cannot be more than one), repeat (search its neighbours) until $B$ is found.
• Repeat for next vertex in $\mathcal{Q}$.
• So complexity for this search is $q \frac r 2 s$, where $r$ is the average number of edges for a vertex in $\mathcal{T}$, and $s$ is the average number of edges in $\mathcal{T}$ that an edge in $\mathcal{Q}$ covers.

So total complexity is $(Cn+Dq) \log(n) + E q \frac r 2 s$, where $C$, $D$ and $E$ are constants that depend upon the individual operations needed to do the sort and searches.

(1) Assuming here that testing for equality is "perfect", i.e. not taking into account floating point artefacts, which may be present in some applications.

(2) This assumes $\mathcal{T}$ is stored in a way that is convenient for this kind of check.

Answer 2

(I do not assume convexity of the two simple polygons)

In $O(qt)$ time, determine for each triangle whether any of its vertices are outside $\mathcal Q$. (Can be done by counting “windings” around the tested vertices; I assume this can be done error-free, eg because all coordinates are integers)

Select those triangles which have none of their vertices outside $\mathcal Q$. Remains to check whether the union of these triangles is all of $\mathcal Q$ or a proper subpolygon. To do so, compute both areas in $O(q+t)$ time and compare (again assuming exactness, eg integer coordinates).