рассчитать пересечение между двумя отрезками симметричным способом

Question

При использовании обычных формул для расчета пересечения между двумя 2D-сегментами, например, здесь , если округлить результат до целого числа, вы получите несимметричные результаты.

То есть иногда из-за ошибок округления я получаю это intersection(A,B)!=intersection(B,A).

Лучшее решение - продолжать работать с поплавками и сравнивать результаты с определенной точностью. Однако я должен округлить результаты до целых чисел после вычисления пересечения, я не могу продолжать работать с плавающей точкой.

Мое лучшее решение до сих пор состояло в том, чтобы использовать некоторый полный порядок на сегментах в плоскости и иметь intersection, чтобы всегда сравнивать меньший сегмент с большим сегментом.

Есть ли лучший метод? Я что-то упустил?

Answer 1

Вы не хотите сравнивать длины сегментов.

Кроме того, я предполагаю, что при сравнении intersection(A',B') с intersection(B",A") подразумевается, что координаты A' равны в репрезентативном виде идентичны с A" (то же самое для B' и B"), иначе решения не существует.

При этом рассмотрим отрезки [PQ] и [RS], где P, Q, R и S - это точки на плоскости. Вы хотите пересечения отрезков:

• [PQ] [RS]
• [QP] [RS]
• [PQ] [SR]
• [QP] [SR]
• [RS] [PQ]
• [SR] [PQ]
• [RS] [QP]
• [SR] [QP]

... чтобы всегда возвращать одну и ту же пару координат.

Порядок, сначала из конечных точек на каждом сегменте, а затем самих сегментов (на основе конечной точки наименьшего каждого сегмента), является единственным решением, которое гарантирует воспроизводимые результаты. Сам порядок может быть вычислительно тривиальным, например, P<Q если P.x < Q.x || P.x == Q.x && P.y < Q.y, хотя ветвление может дорого обойтись, если иметь дело с миллионами сегментов (посмотрите, как можно использовать SIMD для замены координат сегмента на месте, если это возможно, для генерации порядка.)