ポリゴンブーロップ（クリッピング）アルゴリズムに渡すポリゴンのセットを表すポイントセットがあります。結果が得られたら、ブーロップが新しく作成したポイントを知りたいです。これらは、ポリゴン エッジの交差によるものです。したがって、A が操作前のポイントセットであり、B が操作後のポイントセットである場合、どのポイントが B にあり、A にはないかを知りたいです。
適切な比較が定義された通常のセット型 (C++ std::set など) を使用して差を付ける必要がありますか、それとも四分木を実装してから差を付けるのが最善でしょうか? 違いを提供するオープンソースの四分木の実装は存在しますか? 私は四分木をグーグルで検索しましたが、ほとんどは私の要件に関係のない最近傍の問題に関連しているようです。
1 回の操作で最大 1000 ポイントを獲得できます。
ありがとうございました！