Равномерное заполнение площади многогранника

[Andrey_Kireew]

Здравствуйте!
Эта тема уже неоднократно поднималась на разных форумов, но к большому сожалею для себя, приемлемого для себя решения я не нашел, а хотелось бы.

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

Мне же важны скорость, простота и надёжность алгоритма. Равномерность заполнения на втором плане. Тут видимо нужен прямой алгоритм. Лично у меня есть 2 идеи по этому поводу: 1 - разделить площадь многогранника на заданное число частей равной площади, и в центрах выделенных областей расположить точки. Но тут вопрос - как правильно поделить площадь, чтобы алгоритм хорошо работал на произвольных фигурах.
2 - использовать фронтальный алгоритм триангуляции, отделяющий на каждом шаге от многогранника треугольники примерно одинаковой площади. Такой алгоритм я даже реализовал, но он оказался очень сложным. Сколько я его не улучшаю, всё равно иногда даёт сбои. Вообще он не очень мне нравится.

Может у кого есть идеи как быстро и просто можно "разбросать" точки по фигуре?

[atlakatl]

Andrey_Kireew
В общем случае многогранник одними вершинами не задашь. Нужны ещё рёбра. А совсем в общем - ещё и грани придётся конкретизировать.
Ну а когда у нас все грани обозначены, то раскидать по ним точки не сложно. К примеру, вписываем каждую грань в прямоугольник, подсчитываем соотношение площадей - и относительно конкретного прямоугольника, и относительно общей площади многогранника - и включаем Монте-Карло по прямоугольникам, - чтоб пропорционально.
А вот описать многогранник и найти форму его граней работа нудная и ручная.

[Andrey_Kireew]

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

[atlakatl]

Andrey_Kireew в сообщении #1240448 писал(а):

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

Вписываем многоугольник в прямоугольник, який заштриховываем равномерной сеткой. Что в область фигуры попало, то образует именно "более-менее равномерное заполнение".
Сетка мелкая, но программируется на раз.

[Andrey_Kireew]

Как тогда быть со строго заданным числом точек? Масштаб сетки менять не вариант, там сразу по несколько точек будет вылетать, особенно на большой сетке. Получится итеративный алгоритм без гарантии сходимости.

[atlakatl]

Andrey_Kireew в сообщении #1240452 писал(а):

Как тогда быть со строго заданным числом точек?

Сначала находим площадь фигуры. Подбираем под неё шаг сетки: $h=\sqrt{S/N}$, где N - число точек. Вписываем в прямоугольник, заштриховываем. Считаем точки в фигуре. Их число чуть не совпадает с N. Для воспроизводимости задаёмся алгоритмом коррекции до N. Скажем, выкидываем каждую 200-ю точку или добавляем между каждыми 200-й и 201-й точками ещё одну. В общей куче это особо равномерности не повредит.

Andrey_Kireew в сообщении #1240452 писал(а):

сразу по несколько точек будет вылетать, особенно на большой сетке

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

[Евгений Машеров]

Andrey_Kireew в сообщении #1240448 писал(а):

Но Монте-Карло мне всё равно не подойдёт, так как нужно чтобы результат для конкретной фигуры точно воспроизводился, а не менялся от случая к случаю случайным образом.

Монтекарльте, задавая всякий раз начальные установки ГПСЧ (seed) одинаковыми. Или лучше разными, но однозначно определяемыми фигурой.

[ИСН]

Алгоритм Ллойда же, нет? Должен быть побыстрее, чем электростатика, потому что там все со всеми, а тут это самое.

[grizzly]

atlakatl в сообщении #1240444 писал(а):

В общем случае многогранник одними вершинами не задашь. Нужны ещё рёбра.

Andrey_Kireew в сообщении #1240448 писал(а):

Извиняюсь за не точность, дело в том, что у меня многоугольник а не многогранник.

И что теперь, рёбра (стороны) не нужны? Невыпуклый многоугольник одними вершинами тоже не задать.

[Sender]

grizzly в сообщении #1240488 писал(а):

И что теперь, рёбра (стороны) не нужны? Невыпуклый многоугольник одними вершинами тоже не задать.

В принципе, достаточно знать порядок следования вершин.

[Andrey_Kireew]

ИСН в сообщении #1240486 писал(а):

Алгоритм Ллойда же, нет? Должен быть побыстрее, чем электростатика, потому что там все со всеми, а тут это самое.

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

-- 14.08.2017, 12:49 --

grizzly в сообщении #1240488 писал(а):

И что теперь, рёбра (стороны) не нужны? Невыпуклый многоугольник одними вершинами тоже не задать.

Координаты вершин у меня задаются в порядке обхода границы. Так и задаётся любой многоугольник.

[atlakatl]

Andrey_Kireew

Andrey_Kireew в сообщении #1240443 писал(а):

более - менее равномерно заполнить его площадь

Andrey_Kireew в сообщении #1240491 писал(а):

без нарушения структуры сетки

Вы уж определитесь: "более-менее" или "идеальная структура".
Если первое, то чем плохо выбрасывание/добавление точек по строгому и повторяемому алгоритму?

[Andrey_Kireew]

atlakatl в сообщении #1240493 писал(а):

Andrey_KireewВы уж определитесь: "более-менее" или "идеальная структура".
Если первое, то чем плохо выбрасывание/добавление точек по строгому и повторяемому алгоритму?

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