ですから、私は仕事のために、任意の領域を探索するロボットコントローラーに取り組んでいます。領域は一連の頂点（ポリゴン）によって定義されます。次に例を示します。
ロボットは真ん中から始まり、最も外側の境界に到達しようとし、それからずっとそれをたどります。ただし、地形の性質上、特定のエリアに到達できず、特定の地域しか探索できない場合があります。
私がやりたいのは、探索されていないすべての個々の領域を計算し、次のようにそれらの境界を定義する頂点を返すことです。
これが計算された後、A、B、およびCのジオメトリを含むポリゴンの新しい配列が必要になります。
残念ながら、これを行うための優れた高速アルゴリズムを思い付くことができません。これを計算するための最良の方法は何ですか？
外側の境界ポリゴンから内側のピンク（探索済み）ポリゴンを引いたブール差が必要なISTM。ただし、これには単純なアルゴリズムがないため、さまざまなポリゴンクリッピングライブラリを確認して選択することをお勧めします。
これは、いくつかのクリッピングライブラリのかなり最近の比較です-http://rogue-modron.blogspot.com.au/2011/04/polygon-clipping-wrapper-benchmark.html
また、私自身のオープンソースフリーウェアポリゴンクリッパー用の恥知らずなプラグ-http ://angusj.com/delphi/clipper.php
1 つの方法は、たとえば、 pが境界から ε の距離内にある場合に限り、おそらく何らかの許容範囲 ε > 0 に従って、点pが囲んでいる領域の境界に「接している」という述語を定義することです。次に、探索された領域の境界をトラバースし、各頂点の次の述語に注意します。次に、領域は、s の最大文字列、それらの s を囲む2 つの頂点、およびその間の境界領域の境界 によって区切られます。例として使用した文字列は、リージョンB : 5の概要を示しています。T..,T, T, T, F, F, F, F, F, T, T,...FTFF