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

Question

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

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

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

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

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

Answer 1

Хорошее предложение Lloyd's algorithm. Однако свойство «сохранение соседей», о котором вы просите, неясно.

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

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

тогда алгоритм Ллойда будет делать ,

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

Answer 2

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

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

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

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

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

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

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