вычислять пересечение между двумя сегментами симметричным способом.

Question

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

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

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

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

Есть ли лучший способ? Я что-то упускаю?

Answer 1

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

Кроме того, я полагаю, что при сравнении с intersection(A',B')intersection(B",A") следует понимать, что A' «координаты s являются идентичными representationally к 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 для замены сегмента координаты на месте, если это возможно, чтобы произвести заказ.)