Le plus proche voisin entre la couche de points et la couche de lignes? [fermé]

J'ai posé cette question plusieurs fois sur stackoverflow et irc entre #qgis et #postgis et j'ai également essayé de le coder ou de le mettre en œuvre moi-même dans postgis sans véritable réponse.

En utilisant la programmation (de préférence en python), j'aimerais tracer une ligne d'une couche de points à sa projection sur la ligne la plus proche d'une couche de lignes ou de polygones.

À l'heure actuelle, la plupart de mes données sont sous la forme ESRI et dans les formats postgis; Cependant, je préférerais ne pas utiliser une solution postgis car je suis principalement un utilisateur de shp + qgis.

Une solution idéale consisterait à implémenter GDAL / OGR avec des bibliothèques python ou similaires.

• Utilisation des bibliothèques GDAL / OGR par où dois-je commencer? serait-il possible de donner un plan de solution?
• Puis-je utiliser NetworkX pour effectuer l'analyse du voisin le plus proche?
• Est-ce réellement possible?

Si c'est plus facile, les points pourraient se connecter au point final du segment au lieu d'un point projeté

Cette question s'est avérée un peu plus délicate que ce que je pensais être la bonne. Il existe de nombreuses implémentations de la distance la plus courte elle-même, telles que la distance fournie par Shapely (à partir de GEOS). Peu de solutions fournissent le point d'intersection lui-même, mais seulement la distance.

Ma première tentative a tamponné le point en fonction de la distance entre le point et le polygone et a recherché des intersections, mais les erreurs d'arrondi l'empêchent de donner une réponse exacte.

Voici une solution complète utilisant Shapely, basée sur ces équations :

#!/usr/bin/env python
from shapely.geometry import Point, Polygon
from math import sqrt
from sys import maxint

# define our polygon of interest, and the point we'd like to test
# for the nearest location
polygon = Polygon(((0, 0), (0, 1), (1, 1), (1, 0), (0, 0)))
point = Point(0.5, 1.5)

# pairs iterator:
# http://stackoverflow.com/questions/1257413/1257446#1257446
def pairs(lst):
    i = iter(lst)
    first = prev = i.next()
    for item in i:
        yield prev, item
        prev = item
    yield item, first

# these methods rewritten from the C version of Paul Bourke's
# geometry computations:
# http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
def magnitude(p1, p2):
    vect_x = p2.x - p1.x
    vect_y = p2.y - p1.y
    return sqrt(vect_x**2 + vect_y**2)

def intersect_point_to_line(point, line_start, line_end):
    line_magnitude =  magnitude(line_end, line_start)
    u = ((point.x - line_start.x) * (line_end.x - line_start.x) +
         (point.y - line_start.y) * (line_end.y - line_start.y)) \
         / (line_magnitude ** 2)

    # closest point does not fall within the line segment, 
    # take the shorter distance to an endpoint
    if u < 0.00001 or u > 1:
        ix = magnitude(point, line_start)
        iy = magnitude(point, line_end)
        if ix > iy:
            return line_end
        else:
            return line_start
    else:
        ix = line_start.x + u * (line_end.x - line_start.x)
        iy = line_start.y + u * (line_end.y - line_start.y)
        return Point([ix, iy])

nearest_point = None
min_dist = maxint

for seg_start, seg_end in pairs(list(polygon.exterior.coords)[:-1]):
    line_start = Point(seg_start)
    line_end = Point(seg_end)

    intersection_point = intersect_point_to_line(point, line_start, line_end)
    cur_dist =  magnitude(point, intersection_point)

    if cur_dist < min_dist:
        min_dist = cur_dist
        nearest_point = intersection_point

print "Closest point found at: %s, with a distance of %.2f units." % \
   (nearest_point, min_dist)

Pour la postérité, il semblerait que cette extension ArcView résoud assez bien ce problème, dommage que ce soit sur une plate-forme morte écrite dans une langue morte ...

Une réponse PostGIS (pour multilinestring, si linestring, supprime la fonction st_geometryn)

select t2.gid as point_gid, t1.gid as line_gid, 
st_makeline(t2.geom,st_line_interpolate_point(st_geometryn(t1.geom,1),st_line_locate_point(st_geometryn(t1.geom,1),t2.geom))) as geom
from your_line_layer t1, your_point_layer t2, 
(
select gid as point_gid, 
(select gid 
from your_line_layer
order by st_distance(your_line_layer.geom, your_point_layer.geom)
limit 1 ) as line_gid
from your_point_layer
) as t3
where t1.gid = t3.line_gid
and t2.gid = t3.point_gid

C'est un peu vieux, mais je cherchais des solutions à ce problème aujourd'hui (point -> ligne). La solution la plus simple que j'ai rencontrée pour ce problème est la suivante:

>>> from shapely.geometry import Point, LineString
>>> line = LineString([(0, 0), (1, 1), (2, 2)])
>>> point = Point(0.3, 0.7)
>>> point
POINT (0.3000000000000000 0.7000000000000000)
>>> line.interpolate(line.project(point))
POINT (0.5000000000000000 0.5000000000000000)

Si je vous ai bien compris, les fonctionnalités que vous demandez sont intégrées à PostGIS.

Pour obtenir un point projeté sur une ligne, vous pouvez utiliser ST_Closestpoint (sur PostGIS 1.5).

Vous trouverez quelques conseils sur son utilisation à l' adresse suivante : http://blog.jordogskog.no/2010/02/07/how-to-use-the-new-distance-related-functions-in-postgis-part1/

Il est également possible de trouver le point le plus proche d'un polygone par exemple.

Si vous voulez que la ligne entre les deux points les plus proches sur les deux géométries, vous pouvez utiliser ST_Shortestline. ST_Closestpoint est le premier point de ST_Shortestline

La longueur de ST_Shortestline entre deux géométries est la même que ST_Distance entre les géométries.

Voir le commentaire ci-dessous sur la façon dont ma réponse ne doit pas être considérée comme une solution fiable ... Je vais laisser cet article original ici pour que les autres puissent examiner le problème.

Si je comprends la question, cette procédure générale devrait fonctionner.

Pour trouver le chemin le plus court entre un point (défini par x, y ou x, y, z) et une polyine (définie par un ensemble de connexions constitué de x, y ou x, y, z) dans l'espace euclidien:

1) À partir d'un point défini par l'utilisateur (je l'appellerai pt0), trouvez le sommet le plus proche de la polyligne (pt1). OGRinfo peut interroger les sommets d'une polyligne, puis des calculs de distance peuvent être effectués via des méthodes standard. Par exemple, parcourez une distance calculée comme suit: distance_in_radians = 2 * math.asin (math.sqrt (math.pow ((math.sin ((pt.serveur), (pt0_radians-ptx_radians) / 2)), 2)), 2) + math.cos (pt0_radians) * math.cos (ptx_radians) * math.pow ((math.sin ((pt0_radians-ptx_radians) / 2)), 2)))

2) Enregistrer la valeur de distance minimale associée (d1) et (pt1)

3) examinez les deux segments qui s’éloignent de pt1 (dans la chaîne ogrinfo, ce seront les sommets antérieurs et suivants). Enregistrez ces sommets (n2 et n3).

4) créer la formule y = mx + b pour chaque segment

5) Reliez votre point (pt0) à la perpendiculaire pour chacune de ces deux formules

6) Calculer la distance et les intersections (d2 et d3; pt2, pt3)

7) Comparez les trois distances (d1, d2, d3) pour la plus courte. Votre pt0 vers le nœud associé (pt1, pt2 ou pt3) est le lien le plus court.

C'est un courant de conscience qui répond - j'espère que ma vision mentale du problème et de la solution me convient.

Voici un script python pour QGIS> 2.0 élaboré à partir des astuces et solutions données ci-dessus. Cela fonctionne très bien pour un nombre raisonnable de points et de lignes. Mais je ne l'ai pas essayé avec une énorme quantité d'objets.

Bien sûr, il fallait copier en mode inactif ou toute autre solution moins "solution pythonique" et l'enregistrer sous "le plus proche.point.py".

Dans la boîte à outils QGIS, accédez au script, aux outils, ajoutez un script, puis choisissez-le.

##Vector=group
##CLosest_Point_V2=name
##Couche_de_Points=vector
##Couche_de_Lignes=vector

"""
This script intent to provide a count as for the SQL Funciton CLosestPoint
Ce script vise a recréer dans QGIS la Focntion SQL : CLosest Point
It rely on the solutions provided in "Nearest neighbor between a point layer and a line layer"
  http://gis.stackexchange.com/questions/396/nearest-pojected-point-from-a-point-                               layer-on-a-line-or-polygon-outer-ring-layer
V2 du  8 aout 2016
[email protected]
"""
from qgis.core import *
from qgis.gui import *
from PyQt4.QtCore import *
from PyQt4.QtGui import *
import os
import sys
import unicodedata 
from osgeo import ogr
from math import sqrt
from sys import maxint

from processing import *

def magnitude(p1, p2):
    if p1==p2: return 1
    else:
        vect_x = p2.x() - p1.x()
        vect_y = p2.y() - p1.y()
        return sqrt(vect_x**2 + vect_y**2)

def intersect_point_to_line(point, line_start, line_end):
    line_magnitude =  magnitude(line_end, line_start)
    u = ((point.x()-line_start.x())*(line_end.x()-line_start.x())+(point.y()-line_start.y())*(line_end.y()-line_start.y()))/(line_magnitude**2)
    # closest point does not fall within the line segment, 
    # take the shorter distance to an endpoint
    if u < 0.0001 or u > 1:
        ix = magnitude(point, line_start)
        iy = magnitude(point, line_end)
        if ix > iy:
            return line_end
        else:
            return line_start
    else:
        ix = line_start.x() + u * (line_end.x() - line_start.x())
        iy = line_start.y() + u * (line_end.y() - line_start.y())
        return QgsPoint(ix, iy)

layerP = processing.getObject(Couche_de_Points)
providerP = layerP.dataProvider()
fieldsP = providerP.fields()
inFeatP = QgsFeature()

layerL = processing.getObject(Couche_de_Lignes)
providerL = layerL.dataProvider()
fieldsL = providerL.fields()
inFeatL = QgsFeature()

counterP = counterL= nElement=0

for featP in layerP.selectedFeatures():
    counterP+=1
if counterP==0:
    QMessageBox.information(None,"information:","Choose at least one point from point layer_"+ str(layerP.name())) 

indexLine=QgsSpatialIndex()
for featL in layerL.selectedFeatures():
    indexLine.insertFeature(featL)
    counterL+=1
if counterL==0:
    QMessageBox.information(None,"information:","Choose at least one line from point layer_"+ str(layerL.name()))
    #QMessageBox.information(None,"DEBUGindex:",str(indexBerge))     
ClosestP=QgsVectorLayer("Point", "Projected_ Points_From_"+ str(layerP.name()), "memory")
QgsMapLayerRegistry.instance().addMapLayer(ClosestP)
prClosestP = ClosestP.dataProvider()

for f in fieldsP:
    znameField= f.name()
    Type= str(f.typeName())
    if Type == 'Integer': prClosestP.addAttributes([ QgsField( znameField, QVariant.Int)])
    if Type == 'Real': prClosestP.addAttributes([ QgsField( znameField, QVariant.Double)])
    if Type == 'String': prClosestP.addAttributes([ QgsField( znameField, QVariant.String)])
    else : prClosestP.addAttributes([ QgsField( znameField, QVariant.String)])
prClosestP.addAttributes([QgsField("DistanceP", QVariant.Double),
                                        QgsField("XDep", QVariant.Double),
                                        QgsField("YDep", QVariant.Double),
                                        QgsField("XProj", QVariant.Double),
                                        QgsField("YProj", QVariant.Double),
                                        QgsField("Xmed", QVariant.Double),
                                        QgsField("Ymed", QVariant.Double)])
featsP = processing.features(layerP)
nFeat = len(featsP)
"""
for inFeatP in featsP:
    progress.setPercentage(int(100 * nElement / nFeatL))
    nElement += 1
    # pour avoir l'attribut d'un objet/feat .... 
    attributs = inFeatP.attributes()
"""

for inFeatP in layerP.selectedFeatures():
    progress.setPercentage(int(100 * nElement / counterL))
    nElement += 1
    attributs=inFeatP.attributes()
    geomP=inFeatP.geometry()
    nearest_point = None
    minVal=0.0
    counterSelec=1
    first= True
    nearestsfids=indexLine.nearestNeighbor(geomP.asPoint(),counterSelec)
    #http://blog.vitu.ch/10212013-1331/advanced-feature-requests-qgis
    #layer.getFeatures( QgsFeatureRequest().setFilterFid( fid ) )
    request = QgsFeatureRequest().setFilterFids( nearestsfids )
    #list = [ feat for feat in CoucheL.getFeatures( request ) ]
    # QMessageBox.information(None,"DEBUGnearestIndex:",str(list))
    NBNodes=0
    Dist=DistT=minValT=Distance=0.0
    for featL in  layerL.getFeatures(request):
        geomL=featL.geometry()
        firstM=True
        geomL2=geomL.asPolyline()
        NBNodes=len(geomL2)
        for i in range(1,NBNodes):
            lineStart,lineEnd=geomL2[i-1],geomL2[i]
            ProjPoint=intersect_point_to_line(geomP.asPoint(),QgsPoint(lineStart),QgsPoint(lineEnd))
            Distance=magnitude(geomP.asPoint(),ProjPoint)
            toto=''
            toto=toto+ 'lineStart :'+ str(lineStart)+ '  lineEnd : '+ str(lineEnd)+ '\n'+ '\n'
            toto=toto+ 'ProjPoint '+ str(ProjPoint)+ '\n'+ '\n'
            toto=toto+ 'Distance '+ str(Distance)
            #QMessageBox.information(None,"DEBUG", toto)
            if firstM:
                minValT,nearest_pointT,firstM = Distance,ProjPoint,False
            else:
                if Distance < minValT:
                    minValT=Distance
                    nearest_pointT=ProjPoint
            #at the end of the loop save the nearest point for a line object
            #min_dist=magnitude(ObjetPoint,PProjMin)
            #QMessageBox.information(None,"DEBUG", " Dist min: "+ str(minValT))
        if first:
            minVal,nearest_point,first = minValT,nearest_pointT,False
        else:
            if minValT < minVal:
                minVal=minValT
                nearest_point=nearest_pointT
                #at loop end give the nearest Projected points on Line nearest Line
    PProjMin=nearest_point
    Geom= QgsGeometry().fromPoint(PProjMin)
    min_dist=minVal
    PX=geomP.asPoint().x()
    PY=geomP.asPoint().y()
    Xmed=(PX+PProjMin.x())/2
    Ymed=(PY+PProjMin.y())/2
    newfeat = QgsFeature()
    newfeat.setGeometry(Geom)
    Values=[]
    #Values.extend(attributs)
    fields=layerP.pendingFields()
    Values=[attributs[i] for i in range(len(fields))]
    Values.append(min_dist)
    Values.append(PX)
    Values.append(PY)
    Values.append(PProjMin.x())
    Values.append(PProjMin.y())
    Values.append(Xmed)
    Values.append(Ymed)
    newfeat.setAttributes(Values)
    ClosestP.startEditing()  
    prClosestP.addFeatures([ newfeat ])
    #prClosestP.updateExtents()
ClosestP.commitChanges()
iface.mapCanvas().refresh()

!!! ATTENTION !!! Faites attention au fait que certains points "étranges" / mal projetés peuvent être produits à cause de cette commande de ligne:

nearestsfids=indexLine.nearestNeighbor(geomP.asPoint(),counterSelec)

La counterSelecvaleur qu'il contient définit combien de plus proches voisins sont retournés. En fait, chaque point doit être projeté à la distance la plus courte possible pour chaque objet de la ligne; et la distance minimale trouvée donnerait la bonne ligne et le point projeté comme voisins les plus proches que nous cherchons. Afin de réduire le temps de boucle, la commande Voisin la plus proche est utilisée. Choisir une counterSelecvaleur réduite à 1 renverra le "premier" objet rencontré (sa boîte englobante plus exactement) et il se peut que ce ne soit pas le bon. Différents objets de taille de ligne peuvent obliger à choisir peuvent être 3 ou 5, voire des objets plus proches afin de déterminer la distance la plus courte. Plus la valeur est élevée, plus cela prend de temps. Avec des centaines de points et de lignes, il commence à devenir très lent avec 3 ou 5 voisins les plus proches, avec des milliers, il peut être déréglé par ces valeurs.

En fonction de vos intérêts et de votre cas d'utilisation, il pourrait être utile d'examiner les "algorithmes de correspondance de carte". Par exemple, il existe un projet RoadMatcher sur le wiki OSM: http://wiki.openstreetmap.org/wiki/Roadmatcher .