Im_too_old_for_this_shit's blog

Find the faces of Planar straight-line graph
By Im_too_old_for_this_shit, 10 years ago, In English

Given a Planar straight-line graph not necessary connected. How to find the DCEL of this planar subdivision (in other words how to find all faces) ? Generally I am interested in the case when faces may contain holes (inner components).

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A generic idea that quickly comes to my mind is to build a spaning tree, treating connected components as vertices (it's not very hard to prove that adding these additional edges won't change the faces). Sorry, but I don't have time to think about the exact algorithm of doing this.

But you didn't tell about the problem you want to solve, and that's bad. One attempt to guess: you have a map and want to quickly answer in what country a specific point lies. If so, there exists a sweepline algorithm, which uses persistent binary search trees and disjoint sets. I can explain it later, if you want.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    As a problem, imagine you have a planar subdivision and a set of points. You want to classify this points according to the face they belong to (i.e. two points are in the same class iff they are in the same face). For simplicity assume you are interested in offline version and graph is not necessary connected. If the graph is connected I can solve the online version, but if it can contain holes it is necessary to find all faces and save them as a DCEL. I couldn't find any paper about this but I think it is a quite standard problem and maybe researched earlier. The main problem I have is to find for each outer component its inner components (the only face that has no outer component is the unbounded face but we can add a big rectangle bounding this subdivision and assume that each face has outer component). See image . I think something like to draw a beam parallel to X axis from each rightmost point of inner component and it will intersect at first time either its outer component or another inner component of the same outer component but I am not so sure about degenerate cases.. About your sweepline with persistent BST and DSU I haven't heard before, maybe you can provide me with links.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I mean an algorithm like this.

      Try to think about the way to build the slab decomposition using a sweepline. At first, try to solve the case when you have just a concave polygon and you know all the queries (hint: store the decomposition in a BST). Then move to the online case (use persistent BST). Then move to multiple faces (disjoint sets will help you to cope with faces looking like English letter X). Then you'll see that your algorithm will work with holes without any additional modifications.

      I could explain everything in details, but I think it'd much better for you to invent the algorithm yourself.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It seems I fully caught your idea. Your persistent BST is really nice. Will try to implement it one of these days. Thank you very much.

        → Reply