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

[Timothy Ellersiek]

Hi there,

currently I'm trying to implement a graph reduction algorithm to reduce 
intersecting GPS trails (
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1336099 ) to find 
the "perfect" trajectory.
To do this I basically have to find faces in a multi directed graph 
graph in order to find the left and right face
of an edge in a specific face. At the end of the day similar to what the 
postgis topology library does.
Now, in many libaries I can find cycle algorithms for undirected / 
directed graphs but they obviously
don't consider the geographic relevance of the vertices in my graph 
structure.

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.

Thank you for your time,

- Tim