Вычислить преобразование расстояния со знаком произвольного многоугольника

Как бы вы вычислили функцию расстояния со знаком для многоугольника, описанного произвольным набором точек. Многоугольник может быть вогнутым или выпуклым. Предположим, что точки хранятся в std::vector с обмоткой против часовой стрелки.

Схема многоугольника

Обновить

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

Может ли кто-нибудь придумать эффективный способ сделать это?

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


c++ computational-geometry c++11
person Jacques Nel    schedule 23.01.2017    source источник
comment
Я бы использовал математику.   -  person deW1    schedule 23.01.2017
comment
что вы сделали, на данный момент?   -  person max66    schedule 23.01.2017
comment
До сих пор я играл с использованием операций над множествами для создания параметрического SDF из разных сегментов линии. Конструктивная твердотельная геометрия кажется хорошей отправной точкой. en.wikipedia.org/wiki/Constructive_solid_geometry Проблема в том, что вы получаете кучу кусочные уравнения из min max операций. Может быть, я мог бы описать границу как плавно интерполированный безье или что-то в этом роде.   -  person Jacques Nel    schedule 23.01.2017
comment
Другой вариант — использовать базисные функции для аппроксимации кривой. Может быть, что-то вроде 2D ряда Тейлора, но тогда я получу звон на острых углах из-за феномена Гиббса. Для этой части проекта острые черты не обязательны.   -  person Jacques Nel    schedule 23.01.2017
comment
Это не очень хорошая идея по двум причинам. 1. Потому что знаковая функция, независимо от того, как вы ее оцениваете, должна включать 2N степеней свободы многоугольника и неизбежно потребует O(N) вычислительного времени. 2. Потому что поиск смены знаков потребует оценки знаковой функции в нескольких местах (минимум 2, но возможно и намного больше), каким бы ни был алгоритм поиска. Таким образом, общая стоимость может превышать O(N.M) для M сегментов.   -  person Yves Daoust    schedule 24.01.2017
comment
да. Моя идея в корне ошибочна. Я собираюсь попытаться включить его в свою систему уровня детализации. Я также добавлю, что я вокселизирую планету с помощью 2D-версии Adaptive Dual Contouring of Hermite Data. frankpetterson.com/publications/dualcontour/dualcontour.pdf. На первом этапе используются плитки с высотами, рассчитанными с помощью грубого моделирования тектонических плит в планетарном масштабе.   -  person Jacques Nel    schedule 24.01.2017
comment
Плитки расположены радиально к центру планеты. Я предвижу использование от 256 до 1024 таких радиальных тайлов.   -  person Jacques Nel    schedule 24.01.2017

Ответы (2)


arrow_upward
1
arrow_downward

Плохая новость: в худшем случае отрезок может пересечь многоугольник в N точках, и это может произойти для всех M отрезков. Таким образом, в худшем случае неизбежно исчерпывающее сравнение сегментов и сторон. Это говорит в пользу метода грубой силы.

К счастью, известны чувствительные к выходу решения для проблемы пересечения N отрезков линии с использованием метода развертки. Сложность можно снизить до O((N+K) log N) или O(N log N + K), где K — количество найденных пересечений.

person Yves Daoust    schedule 24.01.2017

arrow_upward
0
arrow_downward

Сначала поверните все точки так, чтобы линия была параллельна оси x. Затем переведите так, чтобы линия была осью x. Потом в качестве теста интегрировать. Площадь под прямой x0y0 x1y1 вычислить довольно просто. Вы можете суммировать все выражения, чтобы получить неопределенный интеграл или площадь со знаком, которая не должна зависеть от оси (поскольку точки под кривой вычитаются). Теперь, чтобы ответить на конкретный вопрос, выполните сортировку по x, чтобы вы могли найти значение точки при заданном x. Поэтому создайте два «события», начало раздела и конец раздела с указателем или ссылкой на начальное событие. Затем, чтобы получить преобразование расстояния в любой точке, мы вычисляем все события, пересекающие интересующий x. Если вам нужны кусочные функции для каждого интервала событий, это на самом деле немного проще, так как вы можете пройти через очередь от начала до конца.

person Malcolm McLean    schedule 23.01.2017