algorithm - 任意の2Dポリゴンへのラインクリッピング

Question

与えられた多角形を横切るのに十分な長さの線分を取得した場合、それは凹多角形または凸多角形である可能性があります。ポリゴンに含まれているすべての交差するライトセグメントをどのように見つけましたか？

ターゲット領域がポリゴンではなく、陰関数またはスプラインカーブの場合、どのように実行しますか？

ありがとう！

Answer 1

特に曲線（ベジエとスプライン）の場合、問題に対する簡単な解決策は実際にはありません。ポリゴンクリッピングの複雑さに加えて、クリップされた曲線を再構築するというかなりの課題があります（クリッピング結果を「平坦化された」線近似だけでなく、ベジエとスプラインとして残したい場合）。

最近、ポリゴンクリッピングライブラリ「Clipper」のベータアップデート*をリリースしました。これは、ラインポリゴンとラインラインクリッピングを実行します（ラインもカーブにすることができます）。ただし、メインライブラリはDelphi、C ++、C＃で記述されていますが、新しいベータコードはこれまでのところDelphiでのみ作成されているため、役に立たない場合があります。それでも、コードを見ると、「単純な」解決策がないと私が述べている理由がわかります。

• 2011年7月15日編集：この「更新」はこのベータリリースを超えることはなく、単に「概念実証」になりました。現在は古いバージョンのClipperライブラリに基づいており、保守と拡張を行うには大幅な書き直しが必要になります。（ある段階で再検討するかもしれませんが、現在はコアライブラリをさらに改善するつもりです。）それでも、この「概念実証」Delphiコードはここからダウンロードできます。

Answer 2

• ステップ1：すべての交点を任意の順序で見つけます。ポリゴンの場合、赤い線と各セグメントの線の交点を見つける必要があります。2つの線形方程式のシステムを解くだけです。ソリューションがポリゴンセグメントの制限に制限されている場合は、交点があります。
• ステップ2：見つかったポイントを赤い線上の位置で並べ替えます。あなたは最初と最後の点が外側のものであることを知っています。「アウターネス」は、アウター-インナー-アウターなどの各ポイントで反転します。2つの隣接する外側の点の間に、内側の線分（緑）があります。編集：真ではありません...ポイント＃0、セグメント＃0から開始します-＃1は内側、次は外側、次は再び内側というように続きます。

領域がポリゴンではなく、何らかの陰関数によって与えられている場合、その関数が赤い線と等しい場所を見つける必要があります（もちろん、アプローチは関数によって異なります）。