Определить принадлежность точки замкнутой 3D области

Здравствуйте. Как определить находится ли точка внутри замкнутой односвязной 3D области? Поверхность задана треугольными площадками с внешней нормалью.
Была идея интегрировать потенциальную функцию (r - центр треугольника, p - исследуемая точка)

Предполагалось, что снаружи интеграл равен нулю.
Но, видимо, погрешность все же велика (r по площадке в реальности меняется) - определить принадлежность точки, если она очень близко к поверхности, как минимум, не получилось. Либо я не так делаю.
Что можете посоветовать?

0

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

1

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

0

Какая там может быть потеря точности на пересечениях, если использовать double или extended? Там только линейные операции. Скорее, где-то в реализации ошиблись. У меня схожий алгоритм работает без сбоев.

Добавлено через 4 минуты
На интегрировании, кстати, ошибка накопления гораздо быстрее и больше набегает.

0

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

0

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

Добавлено через 1 минуту
И ещё учесть прохождение по граням и вершинам, тоже рассматривая их как особые случаи. Это всё решается.

0

Сообщение от AndrSlav находится ли точка внутри

Пускаете из этой точки луч в любом направлении и считаете, сколько треугольников он пересёк. Если нечётное количество, то точка внутри.

Например, пускаем луч параллельно оси X.
Для каждого треугольника сначала находим пересечение с плоскостью z = z₀. Если это отрезок, то ищем его пересечение с лучом. Если луч проходит через конец отрезка, то учитываем только если у другого конца отрезка координата Y выше.

Я мог не учесть какую-то ситуацию (сложно в голове всё представить). Так что тестируйте.

1

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

Добавлено через 10 минут
Способ с пересечением лучом сложней в реализации, поскольку там нужно учитывать пересечения на ребрах треугольников, чтобы считать их однократно. Это легко осуществляется если треугольная сетка имеет топологическую информацию, типа "крылатых ребер", обеспечивающую простой переход между соседними треугольниками - с треугольника на ребро и обратно.
А способ приведенный мною выше, мне кажется надежнее, но там есть свои нюансы типа усреднения нормалей, если есть несколько одинаковых ближайших точек и т.д.

1

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

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

0

Сообщение от AndrSlav Здесь будет значительно больше вычислений

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

Сообщение от AndrSlav А если на ребро попадает, то можно проверять расстояние между добавленными и новыми точками.

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

0