ポリゴンの自己交差のテストの数値精度

Question

ポリゴンの自己交差のテストを実装しました。パフォーマンスはそれほど重要ではないので、私はちょうどブルートフォースアプローチを使用し、お互いにすべてのセグメントをチェックします。行交差をテストするには、投稿された関数hereを使用します。これは仕事を静かにしています。詳細には、線交点テストの結果は、ポリゴン自体の頂点を交点として渡します。そしてここに私の問題が作用します。交点を計算するのはjavascriptと同じくらい正確で、交点と頂点を区別することができないため、このテストは失敗することがあります。これは間違ったテスト結果につながり、ポリゴン自体が交差していると言います。

どうすればこの問題を解決できますか？このテストの値を丸めると間違った結果につながることもありますか？どのように私はこの問題を適切に克服することができますか？

Answer 1

このような問題を完全に回避するために私が知っている唯一のオプションは、正確な数学ライブラリまたは正確な幾何学的述語のセットを使用することです。私はそのようなものがjavascriptに存在すると仮定しますが、サーバー側で行うほうが現実的かもしれません。

CGAL（言語に関係なく）は、philosophy pageとそのFAQでこの問題の詳細な説明があります。