HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Given a DCEL, how do you identify the unbounded face

Submitted by: @import:stackexchange-cs··
0
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.

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.