Получить точку внутри многоугольника

Question

У меня есть список точек, представляющих собой замкнутый путь для описания многоугольника. Как я могу получить точку, которая должна находиться внутри области многоугольника? Я не имею представления о случае вогнутого многоугольника, но среднее значение всех точек находится внутри многоугольника, когда дело доходит до выпуклого многоугольника.

Answer 1

https://mathoverflow.net/questions/56655/get-a-point-inside-a-polygon

ссылки на:

http://www.exaflop.org/docs/cgafaq/cga2.html#Subject%202.06:%20How%20do%20I%20find%20a%20single%20point%20inside%20a%20simple%20polygon

, что говорит, в частности:

Given a simple polygon, find some point inside it. Here is a method based on the proof that  
there exists an internal diagonal, in [O'Rourke, 13-14]. The idea is that the midpoint of    
a diagonal is interior to the polygon.

1. Identify a convex vertex v; let its adjacent vertices be a and b.
2. For each other vertex q do:
2a. If q is inside avb, compute distance to v (orthogonal to ab).
2b. Save point q if distance is a new min.
3. If no point is inside, return midpoint of ab, or centroid of avb.
4. Else if some point inside, qv is internal: return its midpoint.

Answer 2

1. Выберите первые 3 последовательных точки из многоугольника
2. Проверьте, находится ли средняя точка между первой и третьей точкой внутри многоугольника
3. Если да, то вы нашли свою точку
4. Если нет: отбросить первую точку, добавить следующую точку и перейти к 2.

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

Для шага 2. ищите SO, на это много раз отвечали.