1
$\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.

$\endgroup$
0
$\begingroup$

Take any extreme vertex (say among the ones with minimum x-coordinate, the one that minimizes y). This vertex is incident with 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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