[OSM-dev] Help with implementation of multiplicatively weighted Voronoi diagram for nominatim

[Brian Quinion]

Hi,

I've been trying to get a working implementation of a multiplicatively
weighted Voronoi diagram written now for nearly a week and I'm really
struggling.

The intention is to use it to improve the the indexing quality and
speed of nominatim with regards to mixing city, town and village
points in some layers - I'm sure many of you have noticed the current
problem were towns and villages end up inside city boundaries
(producing weird addresses).

I have a working implementation for a non-weighted algorithm using
Fortune's algorithm [1] - if anyone has the time and maths skills to
adapt that it would be wonderful (can Fortune's algorithm even do
multiplicatively weighted Voronoi diagrams?) beyond that I've been
looking at adapting the demo from cgal [2] but I'm struggling due to
my poor C++ skills (and the fact that the c++ code makes use of insane
numbers of templates).  For someone who is really good with c++ or
already familiar with cgal it would probably be fairly easy.

Alternatively if anyone is aware of any other implementation or is
able to implement anything based on a different library that would
also be good.  I think it really has to be c or c++ - anything else
would be tricky to integrate.  Potentially an implementation in R [3]
using the postgresql module is another possibility.

If anyone can help let me know - otherwise I will struggle onwards and
hope to get somewhere!

--
 Brian


[1] http://en.wikipedia.org/wiki/Fortune's_algorithm

[2] http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html

[3] http://www.r-project.org/