Процедурная генерация поверхности с помощью нескольких точек
Дано: трёхмерный мир, где нужно сгенерировать плоскую (с толщиной в одну единицу) фигуру произвольной формы. Точек может быть любое количество, но не меньше трёх. Между этими точками заполнить пространство всех ячеек, которые находятся внутри отрезка между всеми точками.
Пример на картинке выше.
Красные ячейки - точки. Оранжевые - пространство, которое нужно заполнить между точками (касание красной линией тоже считается) . Я пишу код на языке программирование java, но пример, или подсказку можно дать псевдокодом, или натолкнуть на мысль, как это можно реализовать. Заранее спасибо!
Ответы (1 шт):
Все точки спроектируем на плоскость XY. В ней построим какую-нибудь триангуляцию множества точек или многоугольника. В качестве примера посмотрите триангуляцию Делоне. Из триангуляции выделим все треугольники. Задача сведена к заполнению одного треугольника.
Через три точки теперь уже в трёхмерном пространстве проходит единственная плоскость. Для любой точки пространства можно вычислить находится ли эта точка выше плоскости, на плоскости или ниже плоскости. Единичный кубик пересекается плоскостью если часть его вершин над плоскостью, часть под ней. Начиная с любой вершины треугольника можно поиском в ширину определить все кубики, которые пересекают плоскость треугольника. В поиск в ширину нужно добавить условие что проекция кубика на XY пересекается с проекцией треугольника.
Время работы алгоритма NlogN + K, где N - число точек, K количество кубиков, которые попадут в результат.
P.S. Если вы знакомы с вычислительной геометрией и алгоритмами на графах, то вам моё объяснение не скажет ничего нового. Если нет, вам туго придётся.