Нахождение точки внутри фигуры (нестандартные решения)

Всем привет!
Мне нужно узнать принадлежит ли точка данной фигуре, заданной через координаты вершин. Про четное/нечетное пересечение луча из этой точки со сторонами этой фигуры я знаю, но к сожалению для сложных фигур и большого количества точек, это очень медленный способ.

Я решил разбить объём на ячейки(для других нужд) и мне пришло в голову, что можно смотреть позицию точки относительно тех сторон, что попали в эту ячейку, тем самым очень сильно уменьшая объём работы. Способ через луч в таком случае представляется проблематичным, так как нужно найти вершины новой фигуры полученной отсечением ячейкой. А вот через нормали сторон, заключенных в этой ячейке, для выпуклой фигуры всё просто, если нормали сторон направленны наружу, а точка находится внутри фигуры, то скалярное произведение для всех нормалей и вектора полученного из этой точки и любой точки соответствующей стороны должен быть меньше 0.
А вот можно ли решить подобным образом для не выпуклой фигуры? Какие условия нужно ещё учесть?

0

Skaarj, Есть такая штука. Берем уравнение общее прямой. Ax+By+C. Так вот, все точки, лежащие на прямой, обращают это выражение в нуль. Лежащие по одну сторону дают один знак, по другую - другой. И для выпуклой фигуры все просто. Берете каждую сторону и ЛЮБУЮ другую вершину. Если знаки при подставлении вашей точки и вершины совпали - все Ок (для всех сторон надо проверять). Это избавляет от суеты с нормалями, хотя и имеет тот же самый смысл.
Для не выпуклых...Можно разбить на выпуклые (триангулировать, например) и работать уже с ними.
Хотя не исключено, что есть и более интересные подходы.

0

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

0

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

Ну а если попытаться ускорить его разбив фигуру на N горизонтальных "полос"? Каждая содержит все отрезки пересекающие ее. Двоичным поиском спрыгиваете на полосу - а там уже не так много отрезков.

Вторая оптимизация - внутри полосы..

0

Сообщение от Igor3D Ну а если попытаться ускорить его разбив фигуру на N горизонтальных "полос"? Каждая содержит все отрезки пересекающие ее. Двоичным поиском спрыгиваете на полосу - а там уже не так много отрезков. Вторая оптимизация - внутри полосы..

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

Мне пришёл в голову такой алгоритм.
Пробегаем по всем полигонам, находящимся в ячейке и проверяем по какую сторону лежит точка, пока не кончатся полигоны или пока скалярное произведение с соответствующей нормалью не даст >=0. Если скалярное произведение неотрицательное возможны три случая.
Нарисовал для наглядности

1) Точка лежит внутри не выпуклой фигуры.
2) Точка лежит снаружи не выпуклой фигуры.
3) Точка лежит снаружи выпуклой фигуры.
Прямоугольник - исследуемая ячейка, зеленая стрелка нормаль с которой скалярное произведение вектора NO будет >=0, красный отрезок соответственно проверяет на четность/нечетность пересечений.
Проверяется это всё тем же способом через четное/нечетное пересечение отрезка сторон фигуры. Причём второй точкой отрезка можно взять, например, середину стороны. По идее после выполнения одного из этих трех условий, можем точно сказать, что точка находится внутри/снаружи фигуры и тем самым прервать дальнейший поиск.
Вот алгоритм:


Сложность такого алгоритма в самом худшем случае o(2n), в самом лучшем o(n), если ячеек много и n << N(общее количество сторон в фигуре), то должно очень хорошо ускорить. Если сравнивать с методом через пересечение стороны(треугольника) и луча, то ещё неизвестно, что будет быстрее - в случае выпуклых фигур через скалярное произведение итераций будет столько же и они будут быстрее(меньше вычислений). Ну и не надо рассчитывать вершины новой фигуры, а это ещё надо хорошо обдумать как сделать - триангуляция, обход вершин и т.п. И операция эта будет явно не из быстрых, хоть и на предварительной стадии

0

Сообщение от Skaarj В моём случае полосы - параллелепипеды(ячейки) в них так же хранятся полигоны, которые она пересекает.

Это хорошо изученная тема: raytracer, точнее структуры данных для него. Делать его самому конечно очень полезно, узнаете массу нового. Но с чисто практической точки зрения - непрофессионально. Ищите готовые решения, open-sources.

Сообщение от Skaarj Мне пришёл в голову такой алгоритм. Пробегаем по всем полигонам, находящимся в ячейке и проверяем по какую сторону лежит точка, пока не кончатся полигоны или пока скалярное произведение с соответствующей нормалью не даст >=0. Если скалярное произведение неотрицательное возможны три случая. Нарисовал для наглядности

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

Сообщение от Skaarj Индекс исследуемой ячейки, в которую попала точка находится в одну операцию.

Именно поэтому я понял что Вы "городите велосипед". Должен быть спуск по дереву, это быстрый log, но все же не 1 операция

0

Сообщение от Igor3D Ну поверьте - проскочить здесь не удастся. Никуда Вы не денетесь, придется проверять все полигоны на пути луча. Думаю Вы сами найдете "опровержение" предложенного. Обычно это бывает через неск дней.

Так я все полигоны и проверяю. Поэтому сложность o(n) минимум - либо точка лежит внутри многоугольника, исходя из того что точка лежит по внутреннею сторону всех полигонов и тогда итоговая сложность o(n), либо на k-ом полигоне выясняется, что точка лежит по наружную сторону этого полигона(плоскости). И тогда смотрится количество пересечений отрезка со всеми(!то есть n) полигонами. В этом случае итоговая сложность o(k+n), где k <= n.

Ячейки можно рассматривать как некий массив некоторых подмножеств, где переход к элементу происходит всегда за o(1). И очень сильно уменьшает объём проверяемых полигонов. Способ с лучом и пересечением работает же? Здесь то же самое, просто фигура, рассматриваемая в данной ячейке, не факт, что образует замкнутую фигуру. Поэтому проверка на четность/нечетность пересечений не является достаточной, так как не понятно по какую сторону от этой поверхности находится исследуемый "объём", поэтому предварительно рассматривается позиционирование точки относительно полигона.

Сделаю и так и через bsp(тут придётся поразбираться), результаты постараюсь привести
зы Кстати, ячейки в которые не попало ни одного полигона можно считать 100% попаданием в объём(или 100% не попаданием), если предварительно их обработать. Что для однородных фигур, очень хорошее подспорье. Например сфера вписанная в куб из 20х20х20 ячеек будет пересекать своим объёмом собой ~4200 ячеек из них ~3000 ячеек будут полностью лежать в ней. То есть всего в ~1200 ячейках из 8000 надо будет искать попадание. В остальных со сложностью o(1) будет известно попадание/непопадание. Ну, конечно, нужна серьёзная предобработка. В случае с деревом сложность всегда будет o(log(n)).

0

Внешняя/внутренняя неприменимо, т.к. полигон может находиться в ноде, но не перекрывать искомую точку. Поэтому надо искать пересечение луча с тр-ком, см Moeller-Tumborn и все такое.

Если Вы строите "просто делить кубик" (вместо дерева), то это конечно проще, но возникают серьезеые проблемы с объемом данных. Напр для неск объектов придется делать "кубик для каждого", а если объект рассредоточен.. Словом, рано или поздно все эти проблемы достанут и переделывать придется. Возьмите сразу нормальное BVH/BSP, пока Вы теряете время.

0

Сообщение от Igor3D Внешняя/внутренняя неприменимо, т.к. полигон может находиться в ноде, но не перекрывать искомую точку. Поэтому надо искать пересечение луча с тр-ком, см Moeller-Tumborn и все такое.

Покажите, пожалуйста, на конкретном примере(2d). Честно говоря не могу понять про какой нод идёт речь - это ячейка имеется ввиду? Если многоугольник выпуклый, то условия внутр/внешн достаточное(это по-моему очевидно). В случаях не выпуклого это условие то же может выполниться, если точка лежит в выпуклом многоугольнике образованном из не выпуклого путём продолжения его сторон до новых точек пересечения. Точка А будет проверена через 4 итерации. Во втором случае точка B будет лежать в "положительной" полуплоскости образованной прямой 23, здесь придётся дополнительно проверить пересечение с остальными сторонами. Очевидно, что отрезок проведенный из B в любую точку отрезка 23 (кроме вершин) будет пересекать один единственный раз стороны многоугольника и это будет сторона 12

Сообщение от Igor3D Если Вы строите "просто делить кубик" (вместо дерева), то это конечно проще, но возникают серьезеые проблемы с объемом данных. Напр для неск объектов придется делать "кубик для каждого", а если объект рассредоточен.. Словом, рано или поздно все эти проблемы достанут и переделывать придется. Возьмите сразу нормальное BVH/BSP, пока Вы теряете время.

Вот здесь я как раз готов пожертвовать памятью в угоду скорости, а объект у меня будет один. Но за совет спасибо, буду разбираться с bsp.

0

Сообщение от Skaarj Покажите, пожалуйста, на конкретном примере(2d).

Я не о том говорю. Ну нашли Вы пересечение луча с одним полигоном, и что? Даже в простейшем случае это всего лишь "передняя стенка", нужно еще найти "заднюю" и убедиться что искомая точка лежит между передней и задней. А если 3D объект concave (невыпуклый), то передних и задних может быть сколько угодно. Поэтому остается топать и топать по лучу пока расстояние до следующего пересечения не превысит расстояние до искомой.

Рассмотрение concave полигонов в 3D лишено смысла. Они могут храниться в данных модели (впрочем достаточно редко), но для рендера они обязательно разбиваются на тр-ки. Максимум 4-угольник может рендериться напрямую, но даже это проблематично, большинство raytracer'ов работают только с тр-ками.

И не стоит полагаться на корректный "wind order" (так называют порядок вертексов в полигоне) - да, считается хорошим тоном его соблюдать, но он отнюдь не гарантируется.

Сообщение от Skaarj потому что фигура в ячейке по сути является пересечение двух объёмов и нужно найти новые вершины этой фигуры(для меня это нетривиально)

Если есть желание - расскажите чего хотите добиться, обычно внутри/снаружи решается схемой построения

0

Сообщение от Igor3D Я не о том говорю. Ну нашли Вы пересечение луча с одним полигоном, и что? Даже в простейшем случае это всего лишь "передняя стенка", нужно еще найти "заднюю" и убедиться что искомая точка лежит между передней и задней. А если 3D объект concave (невыпуклый), то передних и задних может быть сколько угодно. Поэтому остается топать и топать по лучу пока расстояние до следующего пересечения не превысит расстояние до искомой.

Почему с одним? Я ищу пересечение луча(отрезка) со всеми полигонами, но только в этой ячейке. Полигоны у меня заданы треугольниками, поэтому о не выпуклости и не идёт речи. Не выпуклая может быть фигура образованная этими полигонами.

Сообщение от Igor3D Рассмотрение concave полигонов в 3D лишено смысла. Они могут храниться в данных модели (впрочем достаточно редко), но для рендера они обязательно разбиваются на тр-ки. Максимум 4-угольник может рендериться напрямую, но даже это проблематично, большинство raytracer'ов работают только с тр-ками. И не стоит полагаться на корректный "wind order" (так называют порядок вертексов в полигоне) - да, считается хорошим тоном его соблюдать, но он отнюдь не гарантируется.

Полигоны у меня заданы треугольниками, поэтому они всегда выгнуты Насчёт порядка подачи вершин..можно конечно устроить упорядочивание на всякий случай, но судя по тому что модели нормально рендерятся c glCullFace(GL_BACK) то нормали полигонов смотрят в нужную сторону.

Сообщение от Igor3D Если есть желание - расскажите чего хотите добиться, обычно внутри/снаружи решается схемой построения

Нужно смоделировать некоторые процессы в теле, для удобства загрузки используется формат *.obj от него мне нужны только вершины и их порядок, ну и нормали вершин для реалистичного рендеринга, хотя они присутствуют далеко не везде, поэтому проще будет самому рассчитать их. Возможно расширю под другие форматы, чтобы легко было импортировать объекты "нужной формы". Будет использоваться метод Монте-Карло, поэтому предполагаемое количество точек может быть очень большим(зависит от точности). Поэтому нужно максимально упростить проверку точки на принадлежность этой фигуре, можно путём всяких предварительных расчётов. Раскидывание объёмов по бинарному дереву выглядит очень привлекательно. Осталось понять как выбирать отсекающие плоскости.

0

Сообщение от Skaarj Почему с одним? Я ищу пересечение луча(отрезка) со всеми полигонами, но только в этой ячейке.

Ну в этой ячейке (ноде) аж 1 полигон, что дальше?

Сообщение от Skaarj Нужно смоделировать некоторые процессы в теле, для удобства загрузки используется формат *.obj от него мне нужны только вершины и их порядок, ну и нормали вершин для реалистичного рендеринга, хотя они присутствуют далеко не везде, поэтому проще будет самому рассчитать их. Возможно расширю под другие форматы, чтобы легко было импортировать объекты "нужной формы". Будет использоваться метод Монте-Карло, поэтому предполагаемое количество точек может быть очень большим(зависит от точности). Поэтому нужно максимально упростить проверку точки на принадлежность этой фигуре, можно путём всяких предварительных расчётов. Раскидывание объёмов по бинарному дереву выглядит очень привлекательно. Осталось понять как выбирать отсекающие плоскости.

Есть такая вещь "convex decomposition", довольно мерзкая - и точность не очень, и считаться может долго. Но она позволяет 1 раз (на фазе предрасчета) разбить concave объект на серию convex, а там уже все просто и с объемом и с заполнением.

А вообще запрягайте raytracer, и чем раньше, тем лучше

0

Сообщение от Igor3D Ну в этой ячейке (ноде) аж 1 полигон, что дальше?

Если в ноде один полигон, это значит что у нас ровная поверхность, поэтому через нормаль однозначно определяется, где внутренняя часть фигуры, где наружная и соответсвтенно легко высчитывается куда падает точка.

0

Сообщение от Skaarj Если в ноде один полигон, это значит что у нас ровная поверхность, поэтому через нормаль однозначно определяется, где внутренняя часть фигуры, где наружная и соответсвтенно легко высчитывается куда падает точка.

Наконец-то понял Ну это практически расчет на 1 несложную модель. А возни все равно хватает...

1

Думаю, принципиально точный алгоритм не ускорить, но если надо решать эту задачу практически, то можно для фигур иметь "габарит" - для каждой координаты определить интервал занятый фигурой. И соответственно первым шагом проверять попадание в интервал. Как правило, пространство вне фигуры много больше самой фигуры, и практически это ускорит алгоритмы типа рендеринга.

0

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

Ну в общем изначально я так и собирался делать - узнаешь минимальные/максимальные координаты фигуры, помещаешь её в этот параллелепипед и потом его разбиваешь на n ячеек с помещением полигонов в каждую. Вопрос изначально был как проверять в этих интервалах(ячейках), ведь там скорее всего будет незамкнутая фигура, а значит пересечение луча не определит внутри/снаружи точка. Ну с этим в общем то разобрались
А вот разбиение "габарита" на ячейки поменьше оказалось не такой уж и простой задачей как я задумывал изначально - нахождение вершины полигона в ячейке/интервале является достаточным, но не необходимым условием. Вот тут как раз и помогло двоичное разбиение пространства, а вот самое интересное это проиндексировать листья этого дерева так чтобы его можно было свести к структуре cell[ind_x][ind_y][ind_z] ради чего это всё и замышлялось собственно

0

Сообщение от Skaarj Мне нужно узнать принадлежит ли точка данной фигуре, заданной через координаты вершин

Давным-давно (еще был в ходу старый добрый gwBasic) один мой студент решил аналогичную задачу следующим образом: он залил определенным цветом всю фигуру (как сейчас помню, это был разносторонний треугольник), а потом проверил, какой цвет возвращает ТОЧКА с заданными координатами. Если цвет совпадал с цветом заливки - точка внутри фигуры, если не совпадал - вне фигуры...

1

Сообщение от Skaarj Вот тут как раз и помогло двоичное разбиение пространства, а вот самое интересное это проиндексировать листья этого дерева так чтобы его можно было свести к структуре cell[ind_x][ind_y][ind_z] ради чего это всё и замышлялось собственно

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

Поиск определяет какой из 2 кубов (или оба) пересек луч и повторяет это рекурсивно пока не обнаружен "лист" (нод содержащий полигоны а не дочерние кубы). Если оба куба пересечены, то спуск продолжается по первому, а второй помещается на стек.

Вот собственно и все в помощь велосипедисту

0

Сообщение от VSI Давным-давно (еще был в ходу старый добрый gwBasic) один мой студент решил аналогичную задачу следующим образом: он залил определенным цветом всю фигуру (как сейчас помню, это был разносторонний треугольник), а потом проверил, какой цвет возвращает ТОЧКА с заданными координатами. Если цвет совпадал с цветом заливки - точка внутри фигуры, если не совпадал - вне фигуры...

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

Сообщение от Igor3D Поиск определяет какой из 2 кубов (или оба) пересек луч и повторяет это рекурсивно пока не обнаружен "лист" (нод содержащий полигоны а не дочерние кубы). Если оба куба пересечены, то спуск продолжается по первому, а второй помещается на стек.

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

0

Сообщение от Skaarj параллелепипеда

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

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

0