Топология, масштабирование

Question

Скажем, есть двухмерная плоскость (квадрат) с некоторыми точками внутри.

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

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

Другими словами,Я хочу увеличить масштаб в области с богатой точкой и уменьшить в пустых областях.

PS: есть ли общее решение для пространств с более высокой размерностью?Есть ли прямое или только итеративное решение?

Answer 1

Хорошее предложение - алгоритм Ллойда . Однако запрошенное вами свойство «сохранение соседей» неясно.

Однако, если вы спрашиваете следующее:

Учитывая граф (V, E), где V состоит в точках [0,1] ^ 2 и Е сегменты, а не два сегмента внутреннее пересечение (т. е. у нас есть планарный график ) перемещайте точки как можно более равномерно, сохраняя планарная собственность

тогда подойдет алгоритм Ллойда.

Кроме: Обобщения заключаются не в том, в чем заключаются точки пространства, а в том, какую плотность вы запрашиваете для точек (например, вам могут потребоваться гауссовы меры на R ^ n).

Answer 2

Вот эскиз возможной стратегии.

К исходному набору P точек добавьте несколько точек от границы квадрата (как минимум, вершины квадрата). Точки должны быть равномерно выбраны от границы, и, если изначально существует n точек, должно быть, по крайней мере, n дополнительных точек, отобранных от границы. Назовите этот расширенный набор Q.

Затем выполните Триангуляцию Делоне из Q. Мы будем использовать ребра из этой триангуляции на следующем шаге.

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

Вы можете решить эту проблему минимизации, решив матричное выражение, так что это «прямое решение».

Решение проблемы наименьших квадратов будет стремиться к выравниванию длин ребер. Таким образом, маленькие края станут больше, а большие края станут меньше. Это даст более равномерное распределение ваших очков при сохранении их топологии.

Это легко обобщается на более высокие измерения.