2
$\begingroup$

This is a question about splitting a very general kind of polygon into a list of simple polygons.

Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit interval $[0,1]$ in the plane $\mathbb{R}^2$. For an $e \in E$ we call the image of $0$ the 'starting-point' of $e$ and the image of $1$ the 'end-point' of $e$.

We request that for any points $p \neq q \in \mathbb{R}^2$ at least one $e \in E$ exists for which $p$ is the starting-point and $q$ the end-point of e.

We will consider two edge-classes: $L$ be the class of all line-segments in the plane and $A$ the class of all line-segments and all circular-arc-segments in the plane.

For an edge-class $E$ we define the 'most-general-E-polygon' as a finite set $V$ (vertices) of different points $P_1,\ldots,P_n$ in the plane together with an automorphism $s:V \to V$ ('successor') which has, considered as a permutation, no subcycle shorter than $n$. Then for each $P \in V$ we have an edge $e$ from $E$ which starts at $P$ and ends at $s(P)$.

So a 'most-general-E-polygon' can have edges that intersect in arbitrary complicated ways, it can have edges that are part of other edges, it can have vertices that are on an edge but are neither start nor end point of the edge and so on.

Now let a 'simple-E-polygon' be a general-E-polygon that is homeomorphic to the unit circle. Alternatively one could define it as a general-E-polygon where two edges either do not intersect or intersect in the end-point of one edge and the start-point of the other edge and where, considered as a graph, all vertices of the simple-E-polygon have degree 2.

It seems plausible that a most-general-E-polygon $P$ for $E = L$ or for $E = A$ can be decomposed into a union of simple-E-polygons $Ps_1,\ldots,Ps_m$ together with edges $e_1,...,e_n$ of class $E$ and where the interiors of two $Ps_i, Ps_j$ are either disjoint or one is contained in the other.

Now how could an efficient algorithm look like, that computes such a decomposition for the edge classes $L$ and $A$ from above?

Probably one would start with computing all intersection points of all occuring edges by a kind of sweep-line algorithm.

Already at this point numerical difficulties, especially with floating point calculation and $E = A$ will probably rise. (The input vertices are given with floating point coordinates and the result shall also be in this form - this is a practical requirement stemming from our use-case of this algorithm).

Is there already a concrete implementation (at least for $E = L$) in existence?

Improve this question
$\endgroup$
3
  • $\begingroup$ I may be missing the point of the 'edge classes' definition compared to the usual definition of a polygon. Does your definition of general polygon capture something that a definition like "A general polygon is a closed polygonal chain where the vertices may also be connected by (certain types of) arcs rather than line segments" misses? In the case of line segments, computing a DCEL may be useful. A similar data structure should apply to arcs as well. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 12 at 8:18
  • $\begingroup$ @Discrete lizard I did not know the notion of 'polygonal chain' and indeed a closed polygonal chain with edges from class E is the same as my 'most-general-E-polygon'. The main problem seems to be to account for floating point limitations in the computation of all intersections of all occuring edges (probably with a sweepline algorithm). At least this was the main problem in a floating point boolean ops for polygons software that our company let develop externally and for which an algorithm solving the problem above shall be used as a 'preconditioner'. $\endgroup$
    – Jürgen Böhm
    Commented Jul 12 at 13:57
  • 1
    $\begingroup$ This is the line arrangement problem i.e. to construct the plane graph from geometry. CGAL has implementations of 2D Arrangements. $\endgroup$
    – pcpthm
    Commented Jul 14 at 10:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.