Как найти ближайшие точки (образуя, таким образом, многоугольник), окружающие определенную точку? (См. Изображение)

8

Я работаю с игровым движком, и моя задача - добавить код для моделирования разрушения жестких сеток.

Сейчас я работаю только над тем, чтобы разбить куб.

Я использую алгоритм Вороного, чтобы создать (реалистичный) тресканный осколок, и я использую метод полуплоскости, чтобы сгенерировать ячейку Вороного.

найти ближайшие (обведенные красным) точки вокруг Вороного (фиолетовая точка)

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

Я получил это далеко.

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

Информация, которая у меня есть:

1) Плоские уравнения всех плоскостей (определяются нормированными нормальными векторами и их расстоянием от начала координат)

2) Точки пересечения (которые я рассчитал)

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

nilspin
источник
Нет ответа, но это интересная проблема!
Тим Холт

Ответы:

4

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

шаг 1: отрезки шаг 2: перпендикулярные биссектрисы

который вы затем пересекли, чтобы найти потенциальные вершины ячейки Вороного.

Теперь вы хотите исключить те, которые пересекают любую из «далеких» полуплоскостей, образованных биссектрисами.

Два совпадающих пересечения, одно несопоставимое

Я покрасил «отдаленные» полуплоскости полупрозрачным синим для ясности.

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

Это фактически означает проверку, находится ли каждая точка на другой стороне каждой биссектрисы (относительно сайта Вороного) и отбрасывание тех, которые есть. (Остерегайтесь ошибок округления.)

Анко
источник
Этот ответ был очень полезен. Чтобы проверить, лежат ли обе точки на одной стороне плоскости, я заменил векторы в уравнениях плоскости и высмотрел их знаки. Если оба были положительными / отрицательными, то они на одной стороне. Иначе они на противоположной стороне. Это работает! Мой код, кажется, производит правильные вершины для осколков Вороного!
Нильспин
Какую программу вы использовали для создания этих изображений в вашем ответе?
Нильспин
@nilspin Inkscape .
Анко
3

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

В качестве оптимизации выполните итерацию от ближайших ребер до самых дальних. Я думаю, что вы можете даже фильтровать вершины при создании слайсов.

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

Тени под дождем
источник