1

次のようなポリゴンチェーンがあります...

代替テキスト

...画像にチェーンがある場合、パスを交差させずに同じ形状を定義するチェーンを計算するにはどうすればよいですか？

具体的には、画像の入力チェーンの場合、必要な結果は次のようになります。

A1、
A2、A2とA3の
交差 、A3とA4の 交差、A4、A5、A3とA4の交差、A3、A3とA2 の交差、A6






あらゆるチェーンでこれを実現するアルゴリズムを探していますが、何をしようとしているのかわからないため、解決策を探すのは難しいです。

私がやろうとしていることの名前があれば、それを知ることは大いに役立つでしょう。

助けてくれてありがとう！

4

1 に答える 1

3

簡単なアルゴリズムは次のとおりです。

for each line segment in the chain:
    Identify any segments which cross this segment
    If crossings > 0
         Follow the branch to the right, if this doesn't lead back to the 
         current intersection follow the branch to the left
    go to the next line segment

分岐をたどってもチェーンの最後に到達する前にその交差点に戻らない場合は、ループをスキップしたことを意味するため、他の分岐を選択する必要があります。

たとえば、このアルゴリズムを実行すると、

Start at segment A1-A2
No intersections, goto next
Segment A2-A3
Intersection A2-A3/A6-A5 choose right path and store the current intersection somewhere
Segment A6-A5
Intersection A6-A5/A4-A3 choose right path and store intersection
Segment A3-A4
A4-A5
A5-A6
Back at intersection A6-A5/A4-A3, go right again to be back on A4-A3
A3-A2
Back at intersection A2-A3/A6-A5, go right again
Finish
于 2010-06-04T04:42:37.673 に答える