4

ポイントと任意の2Dエンティティ（円、ポリゴン、ライン、ポリライン、アークなど）のセットが与えられた場合、次のような既存の戦略を知っている人はいますか。

  1. ポイントがエンティティの任意の組み合わせで囲まれている（囲まれている）かどうかを判断しますか？閉じた形状で「内部」テストを実行するのは簡単ですが、これでは、特にネストされた形状や交差する形状では、必ずしも必要なものが得られるとは限りません。

  2. 私のポイントの周りに閉じたポリゴンを形成する線/エンティティの最小の（最も近い？）セットを見つけますか？（塗りつぶしを考えますが、色に依存しません）

4

1 に答える 1

7

私は過去に商用製品でこの問題に取り組んできました。分析曲線について質問されましたが、少なくとも2回微分可能な曲線についてより一般的に説明します。ポリゴンを個別の線分のセットとして処理します。曲線をセグメント化する必要はありませんが、必要に応じて、アルゴリズムを少し調整することができます。

また、私の論文であるGraphics Gems Vのマトリックスベースの楕円ジオメトリを参照して、楕円間の交差を見つけることもできます。

基本的な考え方：

  1. テストポイントから+x方向の光線を考えます。
  2. 次に、テストポイントから光線に沿って歩くアリについて考えてみます。
  3. アリが曲線の1つとの最初の交差点に当たると、可能な限り鋭く左に曲がり、その交差点に選択した方向を示す矢印を残します。（交差点がない場合、明らかにポイントは制限されていません。）
  4. カーブの終わりになると、それ自体が2倍になります。
  5. そのポイントで交差する複数の曲線がある場合は、最も左側の曲線が選択されます。
  6. 1つまたは複数の曲線が実際に交差点で光線に接している場合は、より高い導関数を使用して、選択する曲線と方向を決定できます。（このアリは微積分を知っています。）
  7. アリがカーブに沿って散歩するとき、それは常に上記のように可能な限り最大の左折をします。交差点の曲線間に接線がある場合は、高階導関数を使用して、「最も左にある」曲線を決定します。（詳細はアリに任されています）。
  8. その移動中に、アリは光線との最初の交差点に何度も来ることがあります。しかし、矢印（手順3で残した矢印）の方向に進んでいることがわかるとすぐに、移動が完了し、「輪郭」を通過します。問題は、ポイントがその輪郭にあるかどうかを判断することになります。

「等高線」は位相幾何学的実体です。これは、「頂点」で接続された「セグメント」の閉じたリングです。

「セグメント」は、特定の方向の輪郭によって使用される曲線の一部です。

「頂点」は、セグメント間の接続です。頂点は平面上の（x、y）位置に関連付けられていますが、同じ位置に複数の頂点が存在する場合があります。その点で交わる等高線のセグメントの各ペアに1つずつです。曲線の終点ごとに頂点（拍車の頂点）、またはアリが遭遇する曲線と曲線の交点があります。

輪郭（このコンテキストでは）は幾何学的エンティティではありません！飛行機の上の単純な閉じた道とは考えないでください。アリはセグメントに沿って進み、最後に到達して、元の状態に戻る可能性があります。これは「拍車」と呼ばれ、いずれかの方向に1つずつ、2つの輪郭セグメントが含まれます。または、カーブセグメントの一方向に沿って進み、他のカーブに沿って少し歩き回り、セグメントの他の方向に沿って戻る場合があります。

したがって、曲線のセットにAからBまでの線が1つしかなく（無限の線がないと仮定します）、光線がPでそれに当たる場合でも、輪郭V0（P）-V1（ A）-V2（P）-V3（B）-4つのセグメントを持つV0 V0-V1、V1-V2、V2-V3、V3-V0。V0とV2は別個の頂点であり、どちらもPに配置されていることに注意してください。

次に、ポイントが輪郭内にあるかどうかをテストします。

光線（テストポイントで発生する光線であれば問題ありません）と等高線の交点を見つけます。等高線との交点の数のパリティ（偶数または奇数）のみが本当に必要です。パリティが奇数の場合、ポイントは曲線で囲まれ、偶数の場合はそうではありません。

二重にトラバースされたセグメントはパリティに何も寄与しないため、無視できます。これは、2回トラバースされたセグメントには、等高線上に2回存在するため、常に偶数の交差があるためです。

例：

この曲線セットを考えてみましょう。私は線を使うので、あまり一生懸命働きません：

カーブセット

ケース1-ポイントは制限されていません。等高線での曲線セグメントの使用は、点線の矢印で示されています。光線輪郭交差パリティの数は偶数です。

無制限のポイント

ケース2-ポイントは制限されています。光線と輪郭の交差パリティは奇数です。

境界点

うまくいかない可能性があるのは次のとおりです。

  1. さまざまな数値上の理由から、輪郭を見つけることができません。たとえば、交差点を見逃す可能性があります。たとえば、2つの曲線が曲線でほぼ接しています。単一の交差点として表示される場合がありますが、光線交差点のパリティテストを実行すると、単一の交差点が表示されるため、パリティが反転するはずがありません。

  2. 正しい方向の決定を行うのに十分な導関数を計算できない場合があります。解析幾何学の場合、これは決して当てはまらないはずです。

  3. 光線は輪郭の頂点（セグメント間の接続）に当たります。（単一の（x、y）ポイントに複数の頂点が存在する可能性があることに注意してください。これらはそれぞれ個別に処理する必要があります。）

この場合、頂点の入力セグメントと出力セグメントが頂点の光線の同じ側にあるかどうかを判断する必要があります。それらが同じ側にある場合、パリティは影響を受けません。それ以外の場合、パリティは反転します。曲線の1つが頂点で光線に接している場合、これを決定するために高階導関数を使用する必要がある場合があります。

  1. 線分はテスト光線と同一線上にあります。これは実際には2の特殊なケースですが、扱いが簡単です。無視してください。

詳細はたくさんありますが、あなたはそれらを処理できるはずです。不要な交差点を計算しないように、必ず空間ツリーを使用してください。

2番目の質問に対する答えは、二重にトラバースされたセグメントを等高線から削除することです。これにより、複数のサブコンターが生成される場合があります。それらの1つにあなたのポイントが含まれます。

于 2012-12-12T23:18:46.490 に答える