[postgis-devel] Finding geographic faces in a planar graph
timothy.ellersiek at geog.uni-heidelberg.de
Tue Jul 29 08:30:54 PDT 2014
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
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,
More information about the postgis-devel