@kzru_hunter

Здравствуйте. По этому вопросу в инете практически нет инфы, поэтому решил задать здесь. Нужен понятный простой алгоритм, который не сложно реализовать, и чтоб производительность алгоритма не была низкой. Есть некоторые идеи по этому вопросу, но пока их не до конца обработал. Одна из идей - это выпустить луч из проверяемой точки вдоль оси OZ и считать, сколько раз пересечёт луч поверхность многогранника, но проблема в том, что луч может пересечь ребро или вершину, принадлежащие нескольким граням, и вот тут не совсем понятно, как обрабатывать эту ситуацию. Для облегчения решения задачи можно спроецировать проверяемую точку и все грани многогранника на плоскость XOY, т.е. исключить из рассмотрения координату Z, и тогда пространственная задача превращается в задачу на плоскости, где возможно применить алгоритм трассировки луча на плоскости.

В инете есть статья "Алгоритмы локализации точки в трехмерном пространстве для генерации объекта при моделировании объекта методом частиц". Там приведён якобы трёхмерный алгоритм трассировки луча:

Тут не учитывается, что луч при пересечении ребер и вершин необязательно при этом входит/выходит из объекта.

0

@one man

Найти расстояние от точки до ближайшей к ней грани. Радиусом, равным этому расстоянию, построить эквидистантный многогранник. Потом два варианта: сравнить объёмы этих многогранников или сравнить суммы площадей граней. Для вычисления площади произвольного многоугольника есть формула, для вычисления объёма произвольного многогранника тоже, вроде бы, подходы имеются. Если площадь поверхности нового многогранника (или объём) меньше старого, то точка внутри, и наоборот.

0

@kzru_hunter

one man очень много вычислений будет
Если мы сразу найдём ближайшую к нашей точке грань, ребро или вершину, то сразу определим, находится ли точка внутри или снаружи: достаточно провести вектор от найденной вершины или любой точки найденной грани или ребра до проверяемой точки и вычислить скалярное произведение этого вектора с внешним нормальным вектором найденной грани, ребра или вершины. Точка будет принадлежать многограннику, если скалярное произведение будет <=0. Нормальные векторы граней должны иметь одну и ту же длину (например, 1), чтобы по ним можно было вычислить усредненные нормальные векторы для ребер и вершин.
Вот только думаю, что такой способ не совсем производительный, т.к. опять же по моему мнению нужно выполнять много вычислений:
1) Пройтись по всем граням: находить проекцию точки на плоскость грани, а потом ещё и проверять, лежит ли эта проекция внутри грани ( если не лежит, то не засчитывать эту грань). Если лежит, то вычислить расстояние до грани.
2) Пройтись по всем ребрам: находить проекцию точки на прямую ребра, а потом ещё и определить, лежит ли эта проекция на самом ребре. Если лежит, то вычислить расстояние до ребра.
3) Пройтись по всем вершинам, вычисляя расстояние до каждой вершины.

0

@one man

Нам надо заменить слово грань словом плоскость. Именно плоскость имелась в виду.

0

@kzru_hunter

???

0

@one man

Например, в плоском случае (когда многоугольник) это прямая, а не отрезок. Так понятнее?

0

@kzru_hunter

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

0

@one man

Да, засилье программистов даёт о себе знать.
Ты хоть русский язык когда-нибудь учил? О геометрии, понятно, спрашивать не приходиться.

Добавлено через 15 минут
Да, "не приходится".

0

@kzru_hunter

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

0

@kzru_hunter

На другом форуме был предложен следующий способ:

Тут видимо имеется ввиду, что нужно рассматривать проекции граней на плоскость X-0-Y и нужно учитывать пересечения только с гранями, лежащими правее от ребра.
Принцип тут такой же, как и для многоугольников: если луч проходил через вершину, то учитывались пересечения только с нижними ребрами. И тут также: если луч проходит через ребро (как мы знаем, ребро связано с 2-мя гранями), то учитываются пересечения только с правыми гранями.
Всё это хорошо до тех пор, пока луч не проходит через вершину (или вершина + ребро). Как эту ситуацию обрабатывать непонятно. Тогда я решил посмотреть на эту ситуацию иначе: стал считать, что луч одновременно проходит через несколько ребёр и попробовать для каждого такого ребра посчитать кол-во пересечений указанным способом. К сожалению, у меня для следующих ситуаций везде получилось четное число пересечений:
https://www.youtube.com/watch?v=WhpmPt9pHe8
Есть ещё статья "Алгоритм определения принадлежности точки многоугольнику общего вида или многограннику с треугольными граням Н.А. Тюкачев". Тяжело читается, но основная идея понятна: если луч проходит через вершину, то нужно проверить, лежит ли проекция луча (допустим, луч смотрит в направлении оси Z) на плоскость X-0-Y (точка) внутри спроецированного на плоскость X-0-Y контура, образованного из смежных с данной вершиной вершин. Если лежит внутри контура, то пересечение засчитывается. Если нет - не засчитывается. А если лежит на самом контуре, то нужно дополнительно проанализировать вершину, лежащую дальше и через которую тоже проходит луч. В статье не написано, как принимать решение о пересечении в данном случае, лишь указывает, что решение принимается также, как и в случае с многоугольниками. Как я понял, нужно оба контура объединить в один, и снова проверить, лежит ли точка внутри объединенного контура. Примерно также поступать и с ребрами. К сожалению, пока сомневаюсь, как именно нужно 100% обрабатывать такие ситуации, т.к. луч может сразу проходить через несколько вершин и ребёр. Прикрепил файл с 3д фигурками (Sketchup 2019), которые показывают, что может возникнуть на пути луча.

Вложения

Многогранник.rar (82.8 Кб, 3 просмотров)

0