4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Won't have the opportunity to try this until later, but that sounds right! Thank you! $\endgroup$
    – Alistair401
    Commented Oct 31, 2019 at 10:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.