0

2D空間に2つの凸多角形がある場合、線上の任意の点で、いずれかの凸多角形の最も近い点から等距離にある線分をどのように作成しますか？

点ではなく凸多角形のボロノイ図の実装を検討していますが、2つの多角形だけの線の計算を開始する方法がわかりません。だから私はこれを一度に一歩踏み出してここから始めると思いました。

編集質問をもう少し明確にするために、平面（またはそのサブセット）を二等分したいと思います。

左側にポリゴンA、右側にポリゴンBがあるとします。平面を左側の点と右側の点に分割する二等分線があります。線上のすべての点は、どちらのポリゴンからも等距離にあります。線の左側のすべての点は、ポリゴンBよりもポリゴンAに近くなります。線の右側のすべての点は、ポリゴンBに最も近くなります。

これは、私が書いたMatlabスクリプトによって生成された、ブルートフォース近似を強制する画像です。

おおよその二等分線

問題は、2つのポリゴンの「間」のスペースを調べるほど単純ではないと思います。これは、線が2つの形状の間の領域を直接超えて延びる必要があるためです。そして理想的には、2つ以上の形状に一般化する解決策を見つけたいと思います。これは、私には、問題をさらに複雑にしているように見えます。これは、それがどのように見えるかについての（明らかに非常に大まかな）概算です：

より複雑な例

4

2 に答える 2

1

さて、一度に1ステップずつ進めて、ポリゴン自体の最も近いポイントを調べます。AのaがBに最も近い点であり、BのbがAに最も近い点であるとしましょう。ABの中点が目的のセグメントにあることがわかります。

の可能性は何ですか？Aの頂点にすることも、片側の点にすることもできます。同じことがbにも当てはまります。「等距離セグメント」はどうなりますか？それぞれの場合にそれらを構築する方法は？

これらのセグメントはポリゴンの辺から等距離にあるため、対応する辺を含む線の角度を二等分する線の一部である必要があります。

于 2011-11-15T18:34:09.030 に答える
1

私はあなたを正しく理解していますが、2つの凸多角形の間のスペースを効果的に二等分する線が必要だと仮定していますか？もしそうなら、そして...

  1. 2つのポリゴン（P1とP2）を結ぶ線を見つけます
    • X座標とY座標の平均を計算して、各ポリゴンの中心（P1.centreとP2.centre）を見つけます。
    • 他の中心に最も近い各ポリゴンの頂点を見つけます（P1.vc＆P2.vc）
  2. P1.vcとP2.vcが、P1とP2を結ぶ線を定義することになります。
    • P1.vcとP2.vcの中点（mp）を見つけます

二等分線=mpを通過するP1.vcとP2.vcを結ぶ線の垂線

于 2011-11-15T19:11:57.117 に答える