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

2010-07-22 Par sujet Emilie Laffray 
2010/7/22 Vincent de Chateau-Thierry 

>
> Un seul node "place" à l'intérieur d'une limite admin de niveau 8, c'est un
> cas banal en France
> en zone urbaine dense où on n'aura pas (pas encore) figuré de nodes pour
> les quartiers.
> Par exemple La Garenne-Colombes : http://osm.org/go/0BPC1CqS--
> Ce qui est souhaitable, c'est en tout cas de n'avoir qu'un seul node place
> éligible
> au titre d'admin_centre, pour reprendre la modélisation proposée ici :
>
> http://wiki.openstreetmap.org/wiki/WikiProject_France/Tracer_les_limites_administratives#Tags_de_la_relation
>
> C'est pour tendre vers cette unicité que Nominatim recourt à des polygones
> de Voronoï, en substitut de limites
> administratives ou postales. Le but reste de pouvoir associer sans trop
> d'ambiguïté un nom de rue à un nom de ville/village
> dont l'emprise, si elle n'existe pas, aura été approximée par un polygone
> dépendant de l'importance supposée de la "place" :
> c'est la pondération ("weighted") recherchée dans le message initial.
>

Son algorithme de base était basé sur une importance des points en tant que
tel, ce qui est assez proche de l'algorithme que j'utilise au boulot pour
notre service de reverse geocoding (u-blox). L'avantage de passer de points
a un polygone c'est la vitesse dans la base de donnée. Un algorithme base
sur des points (a la Geonames) est environ 4 a 6 fois plus lent dans mes
tests que sur des polygones, d'où l'intérêt d'utiliser des diagrammes de
Voronoi qui offre la possibilité de créer un maillage avec aucune
superposition.

Emilie Laffray
___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-22 Par sujet julien 
> Vincent de Chateau-Thierry a écrit :
>>
>> C'est pour tendre vers cette unicité que Nominatim recourt à des
>> polygones de Voronoï, en substitut de limites
>> administratives ou postales. Le but reste de pouvoir associer sans trop
>> d'ambiguïté un nom de rue à un nom de ville/village
>> dont l'emprise, si elle n'existe pas, aura été approximée par un
>> polygone dépendant de l'importance supposée de la "place" :
>> c'est la pondération ("weighted") recherchée dans le message initial.
>>
>> vincent
>>
>>
> Intéressant, je ne connaissais que la version "points" Delaunay/Voronoï.
> De quoi sont composés les limites des cellules ? D'une combinaison
> d'arcs de cercles et de segments de droites.

Dans mes souvenir, uniquement des segments de droite.

La ponderation correspond a la taille des cellules si tu parle biologie,
la réputation du magasin si tu parle zone de chalandise, la population (ou
importance administrative) si on parle de carte.


___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-22 Par sujet Benoît ROUSSEAU 

Vincent de Chateau-Thierry a écrit :


C'est pour tendre vers cette unicité que Nominatim recourt à des polygones de 
Voronoï, en substitut de limites
administratives ou postales. Le but reste de pouvoir associer sans trop 
d'ambiguïté un nom de rue à un nom de ville/village
dont l'emprise, si elle n'existe pas, aura été approximée par un polygone dépendant de 
l'importance supposée de la "place" :
c'est la pondération ("weighted") recherchée dans le message initial.

vincent

  

Intéressant, je ne connaissais que la version "points" Delaunay/Voronoï.
De quoi sont composés les limites des cellules ? D'une combinaison 
d'arcs de cercles et de segments de droites.

Benoît R.

___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-22 Par sujet Vincent de Chateau-Thierry 

>> De : "Nicolas Dumoulin"
>>
>> Le jeudi 22 juillet 2010 01:28:02 Pieren, vous avez écrit : 
>>> 2010/7/21 Vincent de Chateau-Thierry 
>>> Et pour les autres (ceux qui ne savent pas coder un Weighted Voronoi), 
>>> une autre manière d'aider Nominatim à devenir plus pertinent, c'est de 
>>> mapper... des limites administratives :-) . 
>> Il arrive qu'il y ait plusieurs nodes 'place' à l'intérieur d'une même 
>> limite administrative (c'est aussi ce que relève Brian dans son message et 
>> pour lequel il souhaite améliorer les résultats de nominatim). 
>
> Je ne comprends pas le message subtil. Ça me paraît obligé qu'il y ait 
> plusieurs nodes 
> "place" à l'intérieur d'une limite administrative. Je vois mal une commune 
> avec un seul
> lieu habité. J'ai peur de rater qqch …
>

Un seul node "place" à l'intérieur d'une limite admin de niveau 8, c'est un cas 
banal en France
en zone urbaine dense où on n'aura pas (pas encore) figuré de nodes pour les 
quartiers. 
Par exemple La Garenne-Colombes : http://osm.org/go/0BPC1CqS--
Ce qui est souhaitable, c'est en tout cas de n'avoir qu'un seul node place 
éligible
au titre d'admin_centre, pour reprendre la modélisation proposée ici :
http://wiki.openstreetmap.org/wiki/WikiProject_France/Tracer_les_limites_administratives#Tags_de_la_relation

C'est pour tendre vers cette unicité que Nominatim recourt à des polygones de 
Voronoï, en substitut de limites
administratives ou postales. Le but reste de pouvoir associer sans trop 
d'ambiguïté un nom de rue à un nom de ville/village
dont l'emprise, si elle n'existe pas, aura été approximée par un polygone 
dépendant de l'importance supposée de la "place" :
c'est la pondération ("weighted") recherchée dans le message initial.

vincent

Une messagerie gratuite, garantie à vie et des services en plus, ça vous tente ?
Je crée ma boîte mail www.laposte.net


___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Nicolas Dumoulin 
Le jeudi 22 juillet 2010 01:28:02 Pieren, vous avez écrit :
> 2010/7/21 Vincent de Chateau-Thierry 
> 
> > Et pour les autres (ceux qui ne savent pas coder un Weighted Voronoi),
> > une autre manière d'aider Nominatim à devenir plus pertinent, c'est de
> > mapper... des limites administratives :-) .
> 
> Il arrive qu'il y ait plusieurs nodes 'place' à l'intérieur d'une même
> limite administrative (c'est aussi ce que relève Brian dans son message et
> pour lequel il souhaite améliorer les résultats de nominatim).

Je ne comprends pas le message subtil. Ça me paraît obligé qu'il y ait 
plusieurs nodes "place" à l'intérieur d'une limite administrative. Je vois mal 
une commune avec un seul lieu habité.
J'ai peur de rater qqch …

-- 
Nicolas Dumoulin
http://wiki.openstreetmap.org/wiki/User:NicolasDumoulin

___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Pieren 
2010/7/21 Vincent de Chateau-Thierry 

> Et pour les autres (ceux qui ne savent pas coder un Weighted Voronoi), une
> autre manière d'aider Nominatim à devenir plus pertinent, c'est de mapper...
> des limites administratives :-) .
>
>
Il arrive qu'il y ait plusieurs nodes 'place' à l'intérieur d'une même
limite administrative (c'est aussi ce que relève Brian dans son message et
pour lequel il souhaite améliorer les résultats de nominatim).

Pieren
___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Vincent de Chateau-Thierry 

Bonsoir,

Emilie Laffray a écrit :

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.
Et pour les autres (ceux qui ne savent pas coder un Weighted Voronoi), 
une autre manière d'aider Nominatim à devenir plus pertinent, c'est de 
mapper... des limites administratives :-) .


vincent

___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Benoît ROUSSEAU 




Emilie Laffray a écrit :

  
  2010/7/21 Benoît ROUSSEAU 
  
Bonjour,
    LA référence c'est http://www.cs.cmu.edu/~quake/triangle.html.
Peut être voir avec son auteur.
    Voir aussi pour info le site dans son ensemble (une des pages) : http://www.voronoi.com/wiki/index.php?title=Voronoi_Applications.
Benoît R.

Sont adresse openstreet...@brian.quinion.co.uk
n'est pas la bonne je vous laisse lui transférer.

  
  
  
Tu peux me tutoyer :)
Le lien que tu as donne ne permet pas de faire ce qu'il veut notamment
de creer un poids pour chacun des noeuds. L'implementation que tu
pointes est juste un diagramme de Voronoi de base. C'est pour cela
qu'il regarde l'implementation dans CGAL, notamment une implementation
de Appolinaris.
  
Emilie Laffray

Ouaip, bah je "m'a trompé" dans ces intentions, alors qu'il dit bien
qu'il a une implémentation de base fonctionnelle.
Halala lecture en diagonale, réponse trop rapide > trafic inutile.
Je sors le fouet...
Mais j'aurai appris l'existence de ces graphs avec poids. Faut que je
regarde la chose  :)
Benoît R.



___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Emilie Laffray 
2010/7/21 Benoît ROUSSEAU 

>  Bonjour,
> LA référence c'est 
> http://www.cs.cmu.edu/~quake/triangle.html.
> Peut être voir avec son auteur.
> Voir aussi pour info le site dans son ensemble (une des pages) :
> http://www.voronoi.com/wiki/index.php?title=Voronoi_Applications.
> Benoît R.
>
> Sont adresse openstreet...@brian.quinion.co.uk n'est pas la bonne je vous
> laisse lui transférer.
>

Tu peux me tutoyer :)
Le lien que tu as donne ne permet pas de faire ce qu'il veut notamment de
creer un poids pour chacun des noeuds. L'implementation que tu pointes est
juste un diagramme de Voronoi de base. C'est pour cela qu'il regarde
l'implementation dans CGAL, notamment une implementation de Appolinaris.

Emilie Laffray
___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet Benoît ROUSSEAU 




Bonjour,
    LA référence c'est http://www.cs.cmu.edu/~quake/triangle.html.
Peut être voir avec son auteur.
    Voir aussi pour info le site dans son ensemble (une des pages) : http://www.voronoi.com/wiki/index.php?title=Voronoi_Applications.
Benoît R.

Sont adresse openstreet...@brian.quinion.co.uk
n'est pas la bonne je vous laisse lui transférer.

Emilie Laffray a écrit :
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 
Date: 21 July 2010 13:20
Subject: [OSM-dev] Help with implementation of multiplicatively
weighted Voronoi diagram for nominatim
To: d...@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
  
[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
  d...@openstreetmap.org
  http://lists.openstreetmap.org/listinfo/dev
  
  
  

___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr
  
  


Ce message entrant est certifié sans virus connu.
Analyse effectuée par AVG - www.avg.fr 
Version: 9.0.851 / Base de données virale: 271.1.1/3019 - Date: 07/21/10 08:36:00

  





___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr

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

2010-07-21 Par sujet 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 
Date: 21 July 2010 13:20
Subject: [OSM-dev] Help with implementation of multiplicatively weighted
Voronoi diagram for nominatim
To: d...@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

[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
d...@openstreetmap.org
http://lists.openstreetmap.org/listinfo/dev
___
Talk-fr mailing list
Talk-fr@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-fr