7

現在、ポイント フィーチャ (ポイント フィーチャには 142 のポイントが含まれます) と複数のポリゴン (約 10) があるプロジェクトに取り組んでいます。すべての単一点と R の最も近いポリゴン フィーチャとの間の距離を計算したいと考えています。

私の現在のアプローチは退屈で、少し長くなっています。現在、すべてのポイントとすべてのポリゴンの間の距離を計算することを計画しています。たとえば、142 ポイントとポリゴン A の間の距離、142 ポイントとポリゴン B の間の距離、142 ポイントとポリゴン C の間の距離などを計算します。これらの距離計算の 1 つのサンプル コードを次に示します。

dist_cen_polya <- dist2Line(centroids_coor, polygonA_shp)

これらの計算を行った後、すべてのポイントと最も近いポリゴンの間の最小/最も近い距離を選択するコードを記述します。問題は、この手順が面倒だということです。

計算の労力/計算時間を最小限に抑えるパッケージ/コードを知っている人はいますか? 単一のポイントを最も近いポリゴン フィーチャと比較したり、ポイントと対象のすべてのポリゴンとの間の距離を計算したりするパッケージを本当に使用したいですか?

ありがとうございました。

4

2 に答える 2

14

ここでは、rgeos トポロジ ライブラリのgDistance関数を使用しています。総当たりダブルループを使用していますが、驚くほど高速です。142 ポイントと 10 ポリゴンの場合、所要時間は 2 秒未満です。ループを実行するためのよりエレガントな方法があると確信しています。 

   require(rgeos)

    # CREATE SOME DATA USING meuse DATASET
    data(meuse)
      coordinates(meuse) <- ~x+y
        pts <- meuse[sample(1:dim(meuse)[1],142),]  
    data(meuse.grid) 
      coordinates(meuse.grid) = c("x", "y") 
        gridded(meuse.grid) <- TRUE 
          meuse.grid[["idist"]] = 1 - meuse.grid[["dist"]]    
        polys <- as(meuse.grid, "SpatialPolygonsDataFrame")
          polys <- polys[sample(1:dim(polys)[1],10),]   
    plot(polys)
      plot(pts,pch=19,cex=1.25,add=TRUE)      

    # LOOP USING gDistance, DISTANCES STORED IN LIST OBJECT
    Fdist <- list()
      for(i in 1:dim(pts)[1]) {
        pDist <- vector()
          for(j in 1:dim(polys)[1]) { 
            pDist <- append(pDist, gDistance(pts[i,],polys[j,])) 
          }
        Fdist[[i]] <- pDist
      } 

    # RETURN POLYGON (NUMBER) WITH THE SMALLEST DISTANCE FOR EACH POINT  
    ( min.dist <- unlist(lapply(Fdist, FUN=function(x) which(x == min(x))[1])) ) 

    # RETURN DISTANCE TO NEAREST POLYGON
    ( PolyDist <- unlist(lapply(Fdist, FUN=function(x) min(x)[1])) ) 

    # CREATE POLYGON-ID AND MINIMUM DISTANCE COLUMNS IN POINT FEATURE CLASS
    pts@data <- data.frame(pts@data, PolyID=min.dist, PDist=PolyDist)

    # PLOT RESULTS
    require(classInt)
    ( cuts <- classIntervals(pts@data$PDist, 10, style="quantile") )
       plotclr <- colorRampPalette(c("cyan", "yellow", "red"))( 20 )
         colcode <- findColours(cuts, plotclr)
    plot(polys,col="black")
      plot(pts, col=colcode, pch=19, add=TRUE)

min.dist ベクトルは、ポリゴンの行番号を表します。たとえば、このベクトルをそのまま使用して、最も近いポリゴンをサブセット化できます。

near.polys <- polys[unique(min.dist),]

PolyDist ベクトルには、フィーチャの投影単位での実際のデカルト最小距離が含まれています。

于 2013-05-09T00:12:46.257 に答える
1

多角形には、非常に多くの線があります。ポイントがポリゴン内にある場合、またはエッジ上にある場合、ポリゴン間の距離はゼロです。

したがって、実際には2つのケースを探しています:

  1. ポイントがポリゴンの内側にあるかどうかを確認します（1 つのポリゴンよりも多い場合があることに注意してください
  2. すべてのエッジのコレクションを取得し、エッジからポイントまでの各距離を計算します。最も近い距離は、エッジが属するポリゴンの距離も示します。

したがって、これは単純なアルゴリズムで、ポリゴンごとに 10 個のエッジを考慮すると、すべてのポイントで O(10 * 10) * 142 になります。つまり、100 * 142 = 14200 回の操作になります。=> O(m * deltaE) * n (m はポリゴンの数、deltaE はポリゴンあたりのエッジの平均数、n はポイントの数)。

ここで、これを高速化できるかどうかを確認します。最初に思い浮かぶのは、各ポリゴンにバウンディング ボックス チェックまたはバウンディング サークルを使用できることです。

別のアイデアは、一連の角度に対して各ポリゴンの最も近いエッジを準備することです。たとえば、8 つの角度 (45° ごと) がある場合、別のエッジに取って代わられるすべてのエッジをリストから削除できます (したがって、削除されたエッジの任意のポイントは、同じエッジの他のエッジの任意のポイントよりも常に大きな距離になります)。ポリゴン。

このようにして、通常、複雑さを大幅に軽減できます。長方形の場合、エッジは 4 つではなく 1 つまたは 2 つしかありません。通常の 8 つのエッジのポリゴンを考えると、通常は 1 つまたは 2 つになり、ポリゴンごとに最大 3 つのエッジになります。

各エッジに法線ベクトルを追加すると、ポイントが内側にあるかどうかを計算でき、スキャンラインまたはその他のチェックを実行する必要があります (またはそのコンベックスを知っている)。

2 次元空間を x と y で等間隔に分離するようなマッピング インデックスも可能です。このようにして、9 つのセクターにあるポリゴンをテストするだけで済みます。

次のバージョンでは、各ノードの各バウンディング ボックス (円) を最小予想距離と最大予想距離についてチェックする必要がある R ツリーを使用する可能性があります。したがって、最小距離が別のノードの最大距離よりはるかに大きいノードのポリゴンをチェックする必要はありません。

もう 1 つのことは、マップ データのように特定のツリーのような順序がある場合です。ストリートマップでは、常に世界 -> 地域 -> 国 -> 郡 -> 都市 -> 都市セクター ->...

このようにして、数百万のポリゴンを含む全世界の地図で最も近い場所を、ほぼ 10 ミリ秒未満の妥当な時間で検索できます。

つまり、ここには多くのオプションがあります。また、ポリゴン リストを前処理し、ポリゴンのバイナリ スペース パーティション ツリーを使用するか、角度のあるアプローチを使用するか、さらに洗練されたものを使用して、関連するエッジを抽出します。それはあなた次第です。平均的な複雑さとして O(log(n) * log(deltaE)) が O(log(n)) になるような対数範囲で何かをすることで終わると思います。

于 2014-06-13T10:00:41.850 に答える