[postgis-devel] Finding geographic faces in a planar graph

[Sandro Santilli]

On Tue, Jul 29, 2014 at 05:30:54PM +0200, Timothy Ellersiek wrote:

> The solution of Postgis Topology from Sandro Santilli however finds
> left and right faces in a
> plane geographical way, no matter whether the edges are connected in
> a particular cycle, all they do is have
> to touch each other, where the inner face is anti-clockwise and vice versa.
> 
> This is exactly what I am trying to implement in python but I can't
> find a publication that actually deals with this problem.
> I would be very grateful if you could point me in the right
> direction or just give me a couple of hints how I could deal with
> this.

What PostGIS Topology functions do is they build the cycle as soon
as a circuit gets created.

Here's an idea of the algorithm used:

First you order edges outgoing from start and end nodes to find out the
"next" edges (turning lefr or turning right).

Then you start walking along one side of the new edge.
Eventually, you'll find yourself back to the starting edge, either
on the other side or on the same side.
If you're on the same side a circuit was created (a face was "splitted",
in PostGIS Topology and ISO terms). Otherwise the circuit is still open.

If a circuit was created, a new face is born, and you can update
all edges that you walked on the side of, setting their left or right
face (depending on whether you walked on their left or right side).

I'm not sure this answers your question :)

--strk;