26

2D空間でポイントからポリゴンまでの距離を決定しようとしています。ポイントはポリゴンの内側または外側にあります。ポリゴンは凸面または凹面にすることができます。

ポイントがポリゴン内またはポリゴンの外側にあり、距離がユーザー定義の定数よりも小さい場合d、プロシージャはTrue;を返す必要があります。Falseそうでなければ。

私は同様の質問を見つけました：点から多面体または多角形までの距離。しかし、私の場合、空間は2Dであり、ポリゴンは凹面である可能性があるため、それとはどういうわけか異なります。

dポリゴンをオフセットしてポリゴンの内側または外側を判別するよりも簡単な方法があるはずです。

私がグーグルで検索するためのアルゴリズム、コード、またはヒントをいただければ幸いです。

4

6 に答える 6

29

最善の策は、すべての線を反復処理して、点から線分までの最小距離を見つけることです。

ポイントからラインセグメントまでの距離を見つけるには、最初に任意のポイントP1を選択P2してライン上でポイントからラインまでの距離を見つけます（エンドポイントを使用するのが賢明かもしれません）。P1次に、からあなたのポイントまでのベクトルを取り、内積がどこにあるP0かを見つけます。この値をで割って、値を取得します。(P2-P1) . (P0 - P1).||P2-P1||^2r

これで、ポイントとしてを選択P1した場合、が0から1の間であるP2かどうかを簡単に確認できます。 が1より大きい場合は、が最も近いポイントであるため、距離はです。が0未満の場合、は最も近いポイントであるため、距離はです。rrP2||P0-P2||rP1||P0-P1||

の場合0<r<1、あなたの距離はsqrt(||P0-P1||^2 - (r * ||P2-P1||)^2)

擬似コードは次のとおりです。

for p1, p2 in vertices:

  var r = dotProduct(vector(p2 - p1), vector(x - p1))
  //x is the point you're looking for

  r /= (magnitude(vector(p2 - p1)) ** 2)

  if r < 0:
    var dist = magnitude(vector(x - p1))
  else if r > 1:
    dist = magnitude(vector(p2 - x))
  else:
    dist = sqrt(magnitude(vector(x - p1)) ^ 2 - (r * magnitude(vector(p2-p1))) ^ 2)

  minDist = min(dist,minDist)
于 2012-06-11T16:32:11.453 に答える
2

作業点から線分までの距離関数がある場合は、それを使用して、点からポリゴンの各エッジまでの距離を計算できます。もちろん、最初にポイントがポリゴンの内側にあるかどうかを確認する必要があります。

于 2012-06-11T16:27:19.297 に答える
1

高速またはシンプルが必要ですか？
エッジケースでは常に完全に正しい必要がありますか、それともほとんどの場合十分に問題ありませんか？

一般的な解決策は、各頂点までの距離を見つけ、最小値のペアを見つけ（凸多角形の外側のポイントの場合、これらは隣接していない可能性があることに注意してください）、各セグメントのポイントとラインの交点を確認することです。

大きく複雑な形状の場合は、おおよそのポリゴン境界ボックス（長方形または六角形）を格納し、詳細を確認する前に最も近い辺を見つけることもできます。

正確に1行の特殊なケースを処理するためのコードも必要になる場合があります。

于 2012-06-11T16:37:07.170 に答える
1

これが他の誰かを助ける場合、私はdoverbinの答えをリバースエンジニアリングして、3つのケースが何を計算しているのかをグラフィカルに表示することがなぜ機能したのかを理解しました。（ドーバービン、必要に応じてこれを回答に自由に組み込んでください。）

ドバービンの答えの図解

于 2021-12-05T21:39:56.070 に答える
0

私はこのポインタであなたを助けることができます：

といくつかの意見：

  • Martin Beckettの回答が指摘しているように、最も近いポイントのみをチェックする必要があります。別のセグメントが非常に近くで「予測」される可能性があるためですが、実際には必要に応じて近くにはなりません。
于 2012-06-11T16:53:48.943 に答える
0

残りの回答とのパフォーマンスの違いについてはわかりませんが、Boost C ++ライブラリには、distanceと呼ばれる一般的な実装があります。あらゆる場合の複雑さに関する情報があり、問題のある場合は線形です。

私も数日前にこの問題の解決策を探していました。この発見を共有したいと思います。それが誰かに役立つことを願っています。

于 2019-07-30T08:18:48.560 に答える