Bonjour,<br><br>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.<br>
<br>Emilie Laffray<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Brian Quinion</b> <span dir="ltr"><<a href="mailto:openstreetmap@brian.quinion.co.uk">openstreetmap@brian.quinion.co.uk</a>></span><br>
Date: 21 July 2010 13:20<br>Subject: [OSM-dev] Help with implementation of multiplicatively weighted Voronoi diagram for nominatim<br>To: <a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br><br><br>Hi,<br>

<br>
I've been trying to get a working implementation of a multiplicatively<br>
weighted Voronoi diagram written now for nearly a week and I'm really<br>
struggling.<br>
<br>
The intention is to use it to improve the the indexing quality and<br>
speed of nominatim with regards to mixing city, town and village<br>
points in some layers - I'm sure many of you have noticed the current<br>
problem were towns and villages end up inside city boundaries<br>
(producing weird addresses).<br>
<br>
I have a working implementation for a non-weighted algorithm using<br>
Fortune's algorithm [1] - if anyone has the time and maths skills to<br>
adapt that it would be wonderful (can Fortune's algorithm even do<br>
multiplicatively weighted Voronoi diagrams?) beyond that I've been<br>
looking at adapting the demo from cgal [2] but I'm struggling due to<br>
my poor C++ skills (and the fact that the c++ code makes use of insane<br>
numbers of templates).  For someone who is really good with c++ or<br>
already familiar with cgal it would probably be fairly easy.<br>
<br>
Alternatively if anyone is aware of any other implementation or is<br>
able to implement anything based on a different library that would<br>
also be good.  I think it really has to be c or c++ - anything else<br>
would be tricky to integrate.  Potentially an implementation in R [3]<br>
using the postgresql module is another possibility.<br>
<br>
If anyone can help let me know - otherwise I will struggle onwards and<br>
hope to get somewhere!<br>
<br>
--<br>
 Brian<br>
<br>
<br>
[1] <a href="http://en.wikipedia.org/wiki/Fortune%27s_algorithm" target="_blank">http://en.wikipedia.org/wiki/Fortune's_algorithm</a><br>
<br>
[2] <a href="http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html" target="_blank">http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html</a><br>

<br>
[3] <a href="http://www.r-project.org/" target="_blank">http://www.r-project.org/</a><br>
<br>
_______________________________________________<br>
dev mailing list<br>
<a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br>
<a href="http://lists.openstreetmap.org/listinfo/dev" target="_blank">http://lists.openstreetmap.org/listinfo/dev</a><br>
</div><br>