Сетка с отверстиями: точки внутри / снаружи 3-D замкнутый контур

Question

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

(замкнутый контур - зеленая кривая).

Я хочу пометить только точки внутри этого контура, но, как вы можете видеть желтым цветом, на поверхности есть отверстия и "неровности", которые затрудняют эту маркировку.Я решил, что хочу пометить только те точки, которые расположены на «внешней» поверхности, то есть не заходя внутрь отверстий или ниже выступов (которые в конце концов являются просто еще одним типом отверстий).

На данный момент у меня возникли вопросы вместо идей:

• Как определить, находится ли точка внутри или снаружи замкнутого контура?

однажды решил проблему точек внутри / снаружи:

• Как взять только эти точки внутри замкнутого контура, но расположенные на внешней поверхности?

Спасибо за любые предложения!

Answer 1

Я наконец нашел решение:

1. Чтобы определить, находится ли точка внутри / снаружи контура:

   • Я спроецировал каждую точку сетки, а также контур, на плоскость z = 0, тем самым уменьшив размерность задачи (с 3-х до 2-х)
   • Я построил многоугольник (2-D), соответствующий моему контуру. Затем я применил тест «Точка в многоугольнике», используя приведение лучей , см. Википедию

2. Чтобы взять только точки на «внешней» поверхности: я взял нормаль среднего контура и затем сравнил ее с нормалью каждой точки, уже помеченной как внутри контура (предыдущий шаг). Если угол (normal_vertex, normal_contour)> порог (в моем случае 60º), тогда я обозначил вершину как вне контура.

На данный момент алгоритм работает как положено. Спасибо, Miguel

Answer 2

Это можно сделать, начиная с точки, находящейся в области (внутри контура), итеративно расширяя область до точек, связанных с уже найденными точками, и останавливается, если соединение пересекает контур или имеет какое-либо геометрическое свойство.Геометрические тесты могут быть:

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