ポリゴンをブラシでドラッグしてベクトル画像を編集する

Question

目的は、ブラシのMinkowski sumとマウスのパスを作成して、ポリゴン様のペイントブラシのように画面上でマウスをドラッグすることで簡単なベクトル画像の編集を行うことです。新しいポリゴンは、以前に存在していた異なる色のポリゴンから差し引かれ、同じ色の既存のポリゴンとマージされます。

各マウスの動きをマウスの前の位置から現在の位置まで線分として取り、その線分のミンコフスキーの合計を計算してから、Weiler–Atherton clipping algorithmを使用して、そのミンコフスキーの合計を含むように既存のポリゴンを更新します。

Weiler-Athertonがマウスの動きごとに実行すると、UI遅延が発生する可能性が高いため、最新のマウスの動きに追いつく時間がかかる別のスレッドにそのステップを入れるか、描画が終了するまですべてのWeiler-Atherton計算を保存してから、保存時に一括操作として実行します。これにより、非常に多数の重なり合ったポリゴンが蓄積され、UIをすべてレンダリングするのに必要な時間だけUIが遅れることがあります。

質問：上記の計画は、Inkscapeや他の深刻なベクターグラフィックス編集ソフトウェアがこの操作を実行する方法ですか？それはアルゴリズムのトリッキーさとその計算上の複雑さの両方で狂った計画のようです。専門家は何をしますか？

もう1つのオプション：単純なラスタ操作を使用してペイントし、最後のステップとしてラスタをベクタイメージに変換します。ラスタからベクトルへの変換は、Weiler-Athertonよりも難解ではないようであり、最終出力の品質は低下する可能性がありますが、それがより良い選択肢になりますか？

Answer 1

ユーザーがマウスボタンと描画を押している間に、すべてのマウス移動線セグメントを覚えていると同時に、ブラシ*ラインのMinkowskiを画面解像度ビットマップに合わせてレンダリングすることができます。

ユーザーがボタンを離すまで、画面のペイントにビットマップを使用できます。その時点で、すべての線分ミンコフスキー和の和集合を計算し、結果の図形を図面に追加することができます。

非常に多くの形の和集合を同時に計算するには、ある種の掃引線アルゴリズムが最適です。あなたはO（N log N）または線形時間で仕事をすることができなければなりません。これは顕著な遅延を引き起こさないでしょう。

Answer 2

IMO Weiler-Athertonのボトルネックは、ブルートフォースによって適用されたときにO（N²）演算を必要とする交差点の検出です。残りの処理は、O（N）またはO（NI）に限定されるべき頂点と交差点との間のリンクの再編成であり、NIは交差点の数を表す。

このような場合、おそらくグリッドやバウンディングボックスの階層を使って交差の検索を高速化できます。 （補助的なビットマップレンダリングを使用するには、グリッディングはMattの考え方と同じです。）

実際に10億のエッジを持たない限り、私は実行時間を恐れることはありません。

Answer 3

これを行うには、専門的なベクトルグラフィックスソフトウェアのように任意のブラシの形状（ブラシの形状が速度やスタイラスの圧力に反応するなどの機能を含む）が必要です。

私は、「Ahn、Kim、Lim - 2D曲面オブジェクトの一般的な掃引境界」で説明した方法で実験していました。プロの描画アプリケーションから期待される多くのケース、特に、ブラシの形状が掃除中に動的である可能性がある詳細を処理するようです。目的の解像度の境界曲線を適応的に生成します。 2d曲線の可変幅オフセット。など。

あなたが一般的な方法を必要としない場合は、この方法を簡素化することができそうです。しかし、ここで参考にしたいと思います。

---

PS：私はここの回答に含める非paywalledリンクを探していたと、これは思い付いた - Looking for an efficient algorithm to find the boundary of a swept 2d shape。あなたがしようとしているものと非常によく似ています:)。