Builds loops from a set of undirected edges, turning left at each vertex
until either a repeated vertex (for LoopType::SIMPLE) or a repeated edge
(for LoopType::CIRCUIT) is found. The loops are further grouped into
"components" such that all the loops in a component are connected by
shared vertices. Finally, the loops in each component are divided into
two "complements" such that every edge in one complement is the sibling
of an edge in the other complement. This corresponds to the fact that
given any set of non-crossing undirected loops, there are exactly two
possible interpretations of the region that those loops represent (where
one possibility is the complement of the other). This method does not
attempt to resolve this ambiguity, but instead returns both possibilities
for each connected component and lets the client choose among them.
This method is used to build single polygons. (Use GetDirectedComponents
to build polygon meshes, even when the input edges are undirected.) To
convert the output of this method into a polygon, the client must choose
one complement from each component such that the entire set of loops is
oriented consistently (i.e., they define a region such that the interior
of the region is always on the left). The non-chosen complements form
another set of loops that are also oriented consistently but represent
the complementary region on the sphere. Finally, the client needs to
choose one of these two sets of loops based on heuristics (e.g., the area
of each region), since both sets of loops are equally valid
interpretations of the input.
Each loop is represented as a sequence of edges. The edge ordering and
loop ordering are automatically canonicalized in order to preserve the
input ordering as much as possible. Loops are non-crossing provided that
the graph contains no crossing edges. If some edges cannot be turned
into loops, returns false and sets "error" appropriately.
Builds loops from a set of undirected edges, turning left at each vertex until either a repeated vertex (for LoopType::SIMPLE) or a repeated edge (for LoopType::CIRCUIT) is found. The loops are further grouped into "components" such that all the loops in a component are connected by shared vertices. Finally, the loops in each component are divided into two "complements" such that every edge in one complement is the sibling of an edge in the other complement. This corresponds to the fact that given any set of non-crossing undirected loops, there are exactly two possible interpretations of the region that those loops represent (where one possibility is the complement of the other). This method does not attempt to resolve this ambiguity, but instead returns both possibilities for each connected component and lets the client choose among them.
This method is used to build single polygons. (Use GetDirectedComponents to build polygon meshes, even when the input edges are undirected.) To convert the output of this method into a polygon, the client must choose one complement from each component such that the entire set of loops is oriented consistently (i.e., they define a region such that the interior of the region is always on the left). The non-chosen complements form another set of loops that are also oriented consistently but represent the complementary region on the sphere. Finally, the client needs to choose one of these two sets of loops based on heuristics (e.g., the area of each region), since both sets of loops are equally valid interpretations of the input.
Each loop is represented as a sequence of edges. The edge ordering and loop ordering are automatically canonicalized in order to preserve the input ordering as much as possible. Loops are non-crossing provided that the graph contains no crossing edges. If some edges cannot be turned into loops, returns false and sets "error" appropriately.
REQUIRES: options.degenerate_edges() == { DISCARD, DISCARD_EXCESS } REQUIRES: options.edge_type() == UNDIRECTED REQUIRES: options.siblings_pairs() == { DISCARD, DISCARD_EXCESS, KEEP } [since REQUIRE, CREATE convert the edge_type() to DIRECTED]