snippetMinor
Given a DCEL, how do you identify the unbounded face
Viewed 0 times
dceltheyouidentifyunboundedfacehowgiven
Problem
I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.
This correctly identifies all faces, however I'm struggling to come up with a way to identify the unbounded face surrounding my graph.
So far my only idea is that by building a polygonal representation of every face, I could find the face polygon which 'contains' all the others, but this seems kind of messy.
This correctly identifies all faces, however I'm struggling to come up with a way to identify the unbounded face surrounding my graph.
So far my only idea is that by building a polygonal representation of every face, I could find the face polygon which 'contains' all the others, but this seems kind of messy.
Solution
Take any extreme vertex (say among the vertices having the minimum x-coordinate, the one that minimizes y). This vertex is incident to two edges touching the outer face. Namely the first and the last half-edges leaving this vertex. The first one has the outer face on its right and the last one on its left.
Context
StackExchange Computer Science Q#116518, answer score: 3
Revisions (0)
No revisions yet.