Ближайший сосед между точечным слоем и линейным слоем? [закрыто]

37

Я несколько раз задавал этот вопрос по stackoverflow и irc между #qgis и #postgis, и я также пытался кодировать его или реализовать сам в postgis без реального ответа.

Используя программирование (наиболее предпочтительно Python), я хотел бы нарисовать линию от точечного слоя до его проекции на ближайшую линию линии или слоя многоугольника.

На данный момент большая часть моих данных представлена ​​в форме ESRI и в формате postgis; однако я бы предпочел держаться подальше от решения postgis, так как я в основном пользователь shp + qgis.

Идеальным решением было бы реализовать GDAL / OGR с Python или подобными библиотеками.

  • Использование библиотек GDAL / OGR с чего мне начать? Можно ли дать план решения?
  • Могу ли я использовать NetworkX для анализа ближайшего соседа?
  • Это действительно возможно?

Если это проще, точки могут соединяться с конечной точкой сегмента вместо проецируемой точки

dassouki
источник
Можно ли ограничить линию ортогональностью к отрезку?
WolfOdrade
@wolfOdrade - В общем, это не имеет значения.
Дассуки

Ответы:

33

Этот вопрос оказался немного сложнее, чем я думал, чтобы получить право. Существует множество реализаций самого короткого расстояния, такого как предоставленное Shapely расстояние (от GEOS). Однако лишь немногие решения обеспечивают точку пересечения, но только расстояние.

Моя первая попытка буферизовала точку на расстоянии между точкой и многоугольником и искала пересечения, но ошибки округления не дают точного ответа.

Вот полное решение с использованием Shapely, основанное на этих уравнениях :

#!/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)

Для потомков, похоже, что это расширение ArcView прекрасно справляется с этой проблемой, слишком плохо, что на мертвой платформе, написанной на мертвом языке ...

SCW
источник
1
Интересно, есть ли способ индексировать точки многоугольника, чтобы избежать явного перечисления ...
mlt
@mlt не совсем уверен, о чем вы думаете, но есть некоторые подходы, которые могут помочь в зависимости от геометрии. Могли бы выполнить базовое приведение лучей, чтобы определить соответствующие ближайшие сегменты, если производительность была проблемой. В этом ключе перемещение этого в C или Pyrex улучшило бы вещи.
СБ
Я имею в виду pairsэто алгоритмически O (N) или что-то. Решение @eprand, возможно, можно изменить, чтобы использовать KNN, но мне пока удалось обойтись без PostGIS ...
mlt
Я больше не могу редактировать свой предыдущий комментарий :( Возможно, решение Никласа Авена с ST_Closestpoint и ST_Shortestline будет самым быстрым, если PostGIS - это вариант.
mlt
Правильно, вы можете использовать алгоритм KNN в Python напрямую. Я не верю, что ST_Shortestline использует KNN, он просто повторяется, основываясь на моем прочтении postgis.refractions.net/documentation/postgis-doxygen/d1/dbf/…
scw
8

Ответ PostGIS (для многоканальной строки, если линейная строка, удалите функцию 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
eprand
источник
4

Это немного устарело, но я искал решения этой проблемы сегодня (точка -> линия). Самое простое решение, с которым я столкнулся для этой связанной проблемы:

>>> 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)
alphabetasoup
источник
4

Если я вас правильно понимаю, функциональность, о которой вы просите, встроена в PostGIS.

Чтобы получить точку, спроецированную на линию, вы можете использовать ST_Closestpoint (в PostGIS 1.5)

Некоторые советы о том, как его использовать, вы можете прочитать здесь: http://blog.jordogskog.no/2010/02/07/how-to-use-the-new-distance-related-functions-in-postgis-part1/

Например, можно найти ближайшую точку на многоугольнике к другому многоугольнику.

Если вы хотите провести линию между двумя ближайшими точками на обеих геометриях, вы можете использовать ST_Shortestline. ST_Closestpoint - это первая точка в ST_Shortestline

Длина ST_Shortestline между двумя геометриями такая же, как ST_Distance между геометриями.

Никлас Авен
источник
3

См. Комментарий ниже относительно того, как мой ответ не следует считать надежным решением ... Я оставлю этот оригинальный пост здесь, чтобы другие могли изучить проблему.

Если я понимаю вопрос, эта общая процедура должна работать.

Чтобы найти кратчайший путь между точкой (как определено с помощью x, y или x, y, z) и полиномом (как определено соединительным набором из x, y или x, y, z) в евклидовом пространстве:

1) Из заданной пользователем точки (я назову ее pt0) найдите ближайшую вершину полилинии (pt1). OGRinfo может опрашивать вершины полилинии, и тогда вычисления расстояния могут быть сделаны стандартными методами. Например, выполнить итерацию по расстоянию, рассчитанному как * Math.cos (ptx_radians) * Math.pow ((Math.sin ((pt0_radians-ptx_radians) / 2)), 2)))

2) Сохраните соответствующее минимальное значение расстояния (d1) и (pt1)

3) посмотрите на два сегмента, отходящих от pt1 (в подкладке ogrinfo это будут предыдущие и последующие вершины). Запишите эти вершины (n2 и n3).

4) создать формулу y = mx + b для каждого сегмента

5) Свяжите свою точку (pt0) с перпендикуляром для каждой из этих двух формул

6) Рассчитать расстояние и пересечения (d2 и d3; pt2, pt3)

7) Сравните три расстояния (d1, d2, d3) для самых коротких. Ваш pt0 для связанного узла (pt1, pt2 или pt3) является самой короткой ссылкой.

Это ответ потока сознания - надеюсь, моя ментальная картина проблемы и решения подходит.

Гленнон
источник
Это не будет работать в целом. Например, точка = (1,1), линия = ((0,2), (0,3), (3,0), (2,0)). Если вы набросаете это, то увидите, что «самые близкие» вершины на линии не примыкают к сегменту, который проходит ближе всего к точке ... Я думаю, что единственный способ справиться с этим - проверить каждый сегмент (возможно, используя ограничивающие рамки, чтобы избежать немного оптимизировать) НТН.
Том
3

Вот скрипт на Python для QGIS> 2.0, созданный из советов и решений, приведенных выше. Он отлично работает за разумное количество точек и линий. Но я не пробовал это с огромным количеством предметов.

Конечно, его нужно было скопировать в режиме ожидания или как-нибудь еще менее «питоническое решение» и сохранить как «closest.point.py».

В наборе инструментов QGIS выберите сценарий, инструменты, добавьте сценарий и выберите его.

##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
jean-christophe.baudin@onema.fr
"""
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()

!!! ВНИМАНИЕ !!! Обратите внимание, что некоторые «странные» / неправильные спроецированные точки могут быть получены из-за этой команды линии:

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

В этом counterSelecзначении указывается, сколько из них возвращается. Фактически каждая точка должна проецироваться на максимально короткое расстояние до каждого линейного объекта; и минимальное найденное расстояние даст правильную линию и проецируемую точку в качестве ближайших соседей, которых мы ищем. Чтобы сократить время цикла, используется ближайшая команда Neighbor. При выборе counterSelecзначения, уменьшенного до 1, будет возвращен «первый» встреченный объект (точнее, ограничивающий прямоугольник), и он может оказаться неправильным. Объекты с разными размерами линий могут быть обязательными для выбора, могут быть 3, 5 или даже больше ближайших объектов для определения кратчайшего расстояния. Чем выше значение, тем дольше это занимает. С сотнями точек и линий он начинает очень медленно работать с 3 или 5 ближайшими соседями, с тысячами он может ошибаться с такими значениями.

Жан-Кристоф Боден
источник
3

В зависимости от ваших интересов и варианта использования может быть полезно изучить «алгоритмы сопоставления карт». Например, есть проект RoadMatcher на OSM вики: http://wiki.openstreetmap.org/wiki/Roadmatcher .

Подземье
источник
Это для спроса на поездки и прогнозирования. Обычно мы делим области на зоны анализа трафика (полигоны) и устанавливаем центроид многоугольника как «фиктивного» источника всего трафика в этой зоне. Затем мы рисуем x или y линии «фиктивных дорожных связей» из этой точки до ближайших дорог и равномерно распределяем трафик из этой зоны по этим фиктивным связям и по фактическому слою дороги
dassouki
Ах, так ваша цель автоматизировать создание этой "фиктивной дорожной связи"?
Подземье
действительно :) или фиктивная ссылка (и)
dassouki