Найти точку в полигоне

Question

У меня есть простой двумерный многоугольник с вершинами 3..n. Мне нужно найти произвольную точку внутри (не на границе) этого многоугольника. Как его найти? Эта проблема тривиальна для выпуклых многоугольников: просто возьмите три смежные точки, которые не лежат на одной линии (поэтому они образуют треугольник). Середина этого треугольника гарантированно лежит внутри многоугольника. Но этот подход не работает для невыпуклых многоугольников.

class Point 
    { 
     public double X, Y; 
    } 

    Point GetPointInPolygon(Point[] polygon) 
    { 
     ..... 
    } 

Answer 1

Нарисуйте горизонтальную линию на некоторой ординате между крайними значениями (чтобы пересечь многоугольник). Вычислите все пересечения этой линии с контуром многоугольника. Это делается в простой петле на краях многоугольника, где вы обнаруживаете изменения стороны.

Вы найдете четное количество перекрестков. Отсортируйте их, увеличив абсцисс и выберите любую точку между четным и нечетным пересечением.

Для этого требуется время O (N), которое является оптимальным.

Как вы можете проверить, тест точка-в-полигоне сообщениями луч литья истинных.

Опечатка:

В худшем случае, может быть O (N) перекрестки и сортировка будет принимать O (N Log (N)) операций. На практике это редко встречается.

---

Примечание стороны:

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

Возможные расстояния смещения ограничены, но я понятия не имею, как эта граница может быть найдена. Это будет соответствовать «самым глубоким» точкам.