Tetangga terdekat antara lapisan titik dan lapisan? [Tutup]

Saya telah menanyakan pertanyaan ini beberapa kali di stackoverflow dan irc antara #qgis dan #postgis dan saya juga mencoba untuk kode atau menerapkannya sendiri di postgis tanpa jawaban nyata.

Menggunakan pemrograman (paling disukai python), saya ingin menggambar garis dari lapisan titik, ke proyeksi pada garis terdekat dari garis atau lapisan poligon.

Sampai sekarang sebagian besar data saya dalam bentuk ESRI dan format postgis; namun, saya lebih suka menjauh dari solusi postgis karena saya sebagian besar adalah pengguna shp + qgis.

Solusi ideal adalah dengan mengimplementasikan GDAL / OGR dengan python atau pustaka sejenis

• Menggunakan perpustakaan GDAL / OGR di mana saya harus mulai? apakah mungkin untuk memberikan rencana solusi?
• Bisakah saya menggunakan NetworkX untuk melakukan analisis tetangga terdekat?
• Apakah ini sebenarnya mungkin?

Jika lebih mudah, titik dapat terhubung ke titik akhir segmen alih-alih titik yang diproyeksikan

Pertanyaan ini ternyata sedikit lebih rumit daripada yang saya kira benar. Ada banyak implementasi jarak terpendek itu sendiri, seperti jarak yang disediakan Shapely (dari GEOS). Beberapa solusi menyediakan titik persimpangan itu sendiri, tetapi hanya jarak.

Upaya pertama saya buffer titik dengan jarak antara titik dan poligon, dan mencari persimpangan, tetapi kesalahan pembulatan mencegah hal ini memberikan jawaban yang tepat.

Berikut solusi lengkap menggunakan Shapely, berdasarkan persamaan ini :

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

Untuk anak cucu, sepertinya ekstensi ArcView ini menangani masalah ini dengan cukup baik, sayang sekali pada platform mati yang ditulis dalam bahasa mati ...

Jawaban PostGIS (untuk multilinestring, jika linestring, hapus fungsi 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

Ini agak lama, tapi saya sedang mencari solusi untuk masalah ini hari ini (point -> line). Solusi paling sederhana yang pernah saya temui untuk masalah terkait ini adalah:

>>> 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)

Jika saya mengerti Anda benar, fungsionalitas yang Anda minta sudah ada di PostGIS.

Untuk mendapatkan titik yang diproyeksikan pada sebuah garis, Anda dapat menggunakan ST_Closestpoint (di PostGIS 1.5)

Beberapa petunjuk tentang cara menggunakannya Anda dapat membaca di sini: http://blog.jordogskog.no/2010/02/07/how-to-use-the-new-distance-related-functions-in-postgis-part1/

Dapat digunakan juga untuk menemukan titik terdekat pada poligon ke poligon lain misalnya.

Jika Anda ingin garis antara dua titik terdekat pada kedua geometri, Anda dapat menggunakan ST_Shortestline. ST_Closestpoint adalah poin pertama di ST_Shortestline

Panjang ST_Shortestline antara dua geometri sama dengan ST_Distance antara geometri.

Lihat komentar di bawah mengenai bagaimana jawaban saya tidak boleh dianggap sebagai solusi yang dapat diandalkan ... Saya akan meninggalkan posting asli ini di sini supaya orang lain dapat memeriksa masalahnya.

Jika saya mengerti pertanyaannya, prosedur umum ini harus berhasil

Untuk menemukan jalur terpendek antara titik (sebagaimana didefinisikan oleh x, y atau x, y, z) dan polyine (sebagaimana didefinisikan oleh himpunan h, x atau y, x, y) yang menghubungkan dalam ruang Euclidean:

1) Dari titik yang ditentukan pengguna (saya akan menyebutnya pt0), cari titik terdekat dari polyline (pt1). OGRinfo dapat mensurvei simpul polyline, dan kemudian perhitungan jarak dapat dilakukan melalui metode standar. Sebagai contoh, lakukan iterasi lebih dari satu perhitungan jarak seperti: distance_in_radians = 2 * math.asin (math.sqrt (math.pow ((math.sin ((pt0_radians-ptx_radians) / 2)), 2) + math.cos (pt0_radians) * math.cos (ptx_radians) * math.pow ((math.sin ((pt0_radians-ptx_radians) / 2)), 2))))

2) Menyimpan nilai jarak minimum terkait (d1) dan (pt1)

3) lihat kedua segmen yang berasal dari pt1 (dalam ogrinfo linestring, ini akan menjadi simpul sebelum dan sesudahnya). Rekam simpul-simpul ini (n2 dan n3).

4) buat y = mx + b formula untuk setiap segmen

5) Kaitkan poin Anda (pt0) dengan tegak lurus untuk masing-masing dari dua formula tersebut

6) Hitung jarak dan persimpangan (d2 dan d3; pt2, pt3)

7) Bandingkan tiga jarak (d1, d2, d3) untuk yang terpendek. PT0 Anda ke simpul terkait (pt1, pt2, atau pt3) adalah tautan terpendek.

Itulah aliran kesadaran jawaban - semoga, gambaran mental saya tentang masalah dan solusi cocok.

Berikut ini adalah skrip python untuk QGIS> 2.0 yang dibuat dari petunjuk dan solusi yang diberikan di atas. Ini berfungsi dengan baik untuk jumlah poin dan garis yang masuk akal. Tetapi saya tidak mencobanya dengan sejumlah besar objek.

Tentu saja itu harus disalin dalam keadaan diam atau apapun yang kurang "solusi pythonic" dan simpan sebagai "terdekat.point.py".

Dalam kotak alat QGIS buka skrip, alat, tambahkan skrip, dan pilih itu.

##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()

!!! PERINGATAN !!! Perhatikan bahwa beberapa poin proyeksi "aneh" / salah dapat dihasilkan karena perintah baris ini:

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

The counterSelecnilai di dalamnya mengatur berapa banyak nearestNeighbor dikembalikan. Sebenarnya setiap titik harus diproyeksikan pada jarak sesingkat mungkin untuk setiap objek garis; dan jarak minimum yang ditemukan akan memberikan garis yang benar dan titik yang diproyeksikan sebagai tetangga terdekat yang kami cari. Untuk mengurangi waktu pengulangan, perintah Neighbor terdekat digunakan. Memilih counterSelecnilai yang dikurangi menjadi 1 akan mengembalikan objek "pertama" yang dipenuhi (itu kotak pembatas lebih tepatnya) dan mungkin bukan yang benar. Objek ukuran garis yang berbeda mungkin harus memilih mungkin 3 atau 5, atau bahkan lebih banyak objek terdekat untuk menentukan jarak terdekat. Semakin tinggi nilainya, semakin lama. Dengan ratusan titik dan garis mulai menjadi sangat lambat dengan 3 atau 5 tetangga terdekat, dengan ribuan mungkin bug dengan nilai-nilai tersebut.

Bergantung pada minat dan penggunaan kasus Anda, mungkin berguna untuk melihat "algoritma pencocokan peta". Misalnya, ada proyek RoadMatcher di wiki OSM: http://wiki.openstreetmap.org/wiki/Roadmatcher .