Эффективное определение, находится ли точка внутри треугольника или на краю БЕЗ ДВОЙНОЙ ТОЧНОСТИ

Question

Как определить, находится ли точка внутри треугольника или на границе эффективно, если это возможно при постоянном времени. БЕЗ ДВОЙНОЙ ТОЧНОСТИ

Контекст:

• Самолет двумерный
• Треугольник установлен в соответствии с тремя парами координат Coord(int x, int y)
• Границы для координат: [-2 000 000, 2 000 000]
• Предполагается, что координаты треугольника являются действительными треугольными сетками
• Контрольная точка также является целым числом.

Визуальный пример: Ссылка на изображение

Пример формата:

Triangle a(Coord(50000,50000),Coord(-4000,2000), Coord(300000,150000));

                               // Point  Result
a.test_point( 60000,  45000)   // G      true
a.test_point( 289500, 145500)  // F      true
a.test_point( 292000, 146000)  // E      false
a.test_point(-292000,-146000)  //-E      false
a.test_point( 260000, 134000)  // D      true

Answer 1

Первое замечание: вы не можете избежать вычисления уравнений сторон в той или иной форме, что напрямую связано с классическим «тестом на ориентацию» (https://www.cs.cmu.edu/~quake/robust.html).

В вашем случае 64-битные целые числа позволят избежать переполнения. И если самые большие дельты не превышают 46340, 32 бита достаточно.

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

Точка находится внутри треугольника, когда три теста ориентации возвращают один и тот же знак. Он находится на контуре, когда один тест возвращает 0, а два других - внутреннее условие. Находится в вершине, когда два теста возвращают 0.

Вы также можете рассмотреть этот ответ https://stackoverflow.com/a/21510010/1196549,, хотя он должен быть адаптирован к целочисленной арифметике с теми же ограничениями, что и выше.

---

Также обратите внимание, что если у вас есть много точек для размещения в треугольной сетке, ответ будет совсем другим.

Answer 2

Любая точка внутри треугольника с вершинами (x1, y1), (x2, y2) и (x3, y3) может быть представлена ​​((αx1 + βx2 + γx3), (αy1 + βy2 + γy3)), так что

α + β + γ = 1;

Поскольку вы получили точку (x, y), вы получите еще два уравнения:

(αx1 + βx2 + γx3) = x

(αy1 + βy2 + γy3) = y

Вы должны проверить, существуют ли такие (α, β, γ). Если да, то точка лежит внутри треугольника, а не снаружи. Используйте любой стандартный метод, чтобы проверить это.

РЕДАКТИРОВАТЬ: Я предполагаю, что внутри треугольника вы также имеете в виду по периметру. Если вы хотите, чтобы он был исключительно внутри, то используйте аналогичную идею для строки и проверьте, есть ли у нее решение.