8

私はアプリケーションに取り組んでいます。ユーザーが描いた2つの重なり合う任意の形状を組み合わせることができる必要があります。これは、2つの形状に対するユニオン操作になります。結果として得られる形状は、2つの重なり合う形状のシルエットになります。

形状は、時計回りに一連のポイントとして保存されます。

理想的には、ポイント（x、y）の2つの配列を取り、結果の形状の1つの配列を返すアルゴリズムが必要です。

私はスイープラインアルゴリズムに言及しているポリゴンのブール演算に関するウィキペディアを読んでいますが、これと私の目標をリンクさせることはできません。残念ながら、私は数学者ではありません。

私はActionScript3でアプリケーションを開発していますが、C＃、Javaに精通しており、CとC++を選択できます。

4

6 に答える 6

5

ブール演算を正しく実装することは簡単ではありません。幸いなことに、この機能を既に実装しているライブラリがあります。

どの言語を使用していますか? C++ の場合は、Computational Geometry Algorithms LibraryであるCGALをご覧ください。

于 2010-01-26T14:48:47.053 に答える
3

点 (A と B) の 2 つのリストが与えられた場合
- [1] A の各線は B の線と交差する
か -.- [2] (それ以上の) 線が交差しない場合、重複はありません
-.- [3] (A) の線が B の線と交差する場合
-.-.- [4] 交点を出力に追加する
-.-.- [5] A からの次の線が B と交差する
-.-.-. - [6] そうでない場合は、これを出力に追加します (B の中にあります) goto 5
-.-.-.- [7] そうであれば、交差を出力に追加し、リスト A と B を切り替えます goto 2

2 つの線分の交点も参照してください。申し訳ありませんがコードを書くつもりはありません:)

于 2010-01-26T15:07:04.677 に答える
3

GPCも参照してください。

于 2010-01-27T10:54:22.123 に答える
2

このアルゴリズムはうまくいきますか?

于 2010-01-26T15:10:04.560 に答える
1

javascript api もあるようです。

https://github.com/bjornharrtell/jsts/

jts 標準を実装しているようで、いくつかの異なる実装があります。

http://tsusiatsoftware.net/jts/jts-links.html#ports

それらのすべてがユニオンなどを実行できる必要があります。

http://tsusiatsoftware.net/jts/JTSUser/contents.html

しかし、csg.js は最も印象的なプロジェクト IMO です

https://github.com/evanw/csg.js

于 2012-02-05T22:59:22.687 に答える
1

どうですか：

  1. 2 つの形状の一番左の点をピックします。そのシェイプ A を呼び出して、現在のシェイプにします。
  2. 現在の形状に沿って時計回りに次のポイントまで巻き、1 つまたは複数の線が交差するかどうかを確認します。
    • 交差する線がある場合は、最初の交点を見つけて、それを新しい形状に追加します。他の形状に沿って巻きに切り替えます。
    • 交差する線がない場合は、形状 A の次のポイントに移動し、それを新しい形状のポイントとして追加します。現在の形状に沿って巻き続けます。
  3. 手順 2 を繰り返します。

交点を探しながら、現在の形状に沿って曲がり続けると、思いどおりになるはずです。凹型にも対応できると思います...

基本が機能するようになったら、追加できる最適化がたくさんあると確信しています。

于 2010-01-26T17:22:13.243 に答える