Topology, scaling

Say there is a 2D plane (square) with some points inside it.

How to move all the points in such a way that they fill the plane as evenly as possible but every point maintains its neighbors?

In other words, I want the points to be as far from each other as possible but their locality (topology) should be preserved and they should lay in the square.

In other words, I want to kind of zoom-in in the rich-point-populated area and zoo开发者_C百科m out in the empty areas.

PS: is there a general solution for higher-dimension spaces? Is there a direct solution or only iterative one?

A good suggestion is Lloyd's algorithm. However, the "neighbor preserving" property you're asking for is not clear.

However, if what you're asking is the following:

Given a graph (V, E) where V consists in points of [0,1]^2 and E are segments, and no two segments' interior intersect (ie. we have a planar graph) move the points as evenly as possible, preserving the planar property

then Lloyd's algorithm will do.

Aside: Generalizations are not in term of what space points lie in, but what density you request for the points (you may want Gaussian measures on R^n for instance).

Here's a sketch of a possible strategy.

To your original set P of points, add some points from the boundary of the square (at a minimum, the vertices of the square). The points should be evenly sampled from the boundary, and if there are originally n points, there should be at least √n additional points sampled from the boundary. Call this augmented set Q.

Then do a Delaunay Triangulation of Q. We'll use the edges from this triangulation in the next step.

Now do a least squares minimization to find the position of the points in P (keeping the points in Q-P fixed) that minimizes the sum of squares of edge lengths.

You can solve this minimization problem by solving a matrix expression, so this is a 'direct solution'.

The solution of the least squares problem will tend to equalize the lengths of the edges. So small edges will become larger and large edges will become smaller. This will have the effect of more uniformly distributing your points while preserving their topology.

This generalizes easily to higher dimensions.