[OSM-talk-fr] [Technique] Fwd: [OSM-dev] Help with implementation of multiplicatively weighted Voronoi diagram for nominatim

[Emilie Laffray]

Bonjour,

je sais qu'il y a des gens tres pointus ici, donc je me permets de reposter.
Le createur de Nominatim a besoin d'aide pour implementer un weighted
Voronoi diagram utilisant CGAL. Donc s'il y a des gens qui peuvent aider,
lui envoyer un message.

Emilie Laffray

---------- Forwarded message ----------
From: Brian Quinion <openstreetmap at brian.quinion.co.uk>
Date: 21 July 2010 13:20
Subject: [OSM-dev] Help with implementation of multiplicatively weighted
Voronoi diagram for nominatim
To: dev at openstreetmap.org


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<http://en.wikipedia.org/wiki/Fortune%27s_algorithm>

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

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

_______________________________________________
dev mailing list
dev at openstreetmap.org
http://lists.openstreetmap.org/listinfo/dev
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20100721/33868549/attachment.htm>