CODEWITHSUNDEEP
algorithmgeometryhtml5-canvasgraph-algorithm
Kamil
Kamil

Reputation: 1641

How to effectively distribute points on plane

I have a plane (screen) with its width and height (monitor resolution, not square). And I'd like to distribute points on that plane with the (approximately) same distance from each other.

For example:

Is there any algorithm for this?

Thank you for your time!

EDIT: same distance from each other and from plane border

EDIT2: I compute centers of mass for groups of objects on which behavior I simulate on plane.

Upvotes: 3

Views: 3019

Answers (4)

Kamil
Kamil

Reputation: 1641

First of all, thanks to everybody for suggestions which helped me to define my problem better and to find best solution to my problem.

Now I am using Centroidal Voronoi tessellation which according to Wikipedia: "In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation or Voronoi diagrams. A Voronoi tessellation is called centroidal when the generating point of each Voronoi cell is also its mean (center of mass). It can be viewed as an optimal partition corresponding to an optimal distribution of generators."

Its very fast and there is implementation in D3js library for javascript which I am using.

Upvotes: 0

nbonneel
nbonneel

Reputation: 3326

Depending on the precision you want:

  • You can get a stochasticaly correct answer by Poisson disk sampling. Specifically, a Poisson disk sampling is a random sampling such that no points are closer than a specified radius. Such thing can be efficiently (linear time) implemented in high dimension - e.g. : the c++ code from Robert Bridson : http://www.cs.ubc.ca/~rbridson/download/curlnoise.tar.gz implementing his paper http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

  • You can really optimize for the position of the points. This leads to Lloyd algorithms and similar optimization procedures : Compute the Voronoi diagram of an initial set of points, and move these points the the centroid of their Voronoi cell. This can also be done very efficiently, and can be sped up by using a Newton's method rather than a Lloyd iteration. Ultimately, if your domain is a square, you should obtain an hexagonal grid (which minimizes the function above).

If you only need approximate results, I'd suggest the first approach which should be much faster.

Upvotes: 3

जलजनक
जलजनक

Reputation: 3071

EDIT: Not for physics repulsion simulation.

Dividing a plane into rectangle is easier to process. For rectangles with even side-lengths you can't have a point in the center exactly. However equidistant property spread them apart nicely across screen.

Simple program in PHP to illustrate this:

<?php 
$x_min = 1; $x_max = 1366;

$y_min = 1; $y_max = 768;

$x_div_count = 5;
$y_div_count = 5;

$x_div_len = (integer)round(($x_min + $x_max) / $x_div_count);
$y_div_len = (integer)round(($y_min + $y_max) / $y_div_count);

$x_mid_offset = (integer)round($x_div_len /2);
$y_mid_offset = (integer)round($y_div_len /2); 

$x_offset = $x_mid_offset;
for ($idx =0; $idx < $x_div_count; $idx ++) {

    $y_offset = $y_mid_offset;
    for ($jdx =0; $jdx < $y_div_count; $jdx ++) {

        $points_dist[] = array ('x' => $x_offset, 'y' => $y_offset);

        $y_offset += $y_div_len;
    }
    $x_offset += $x_div_len;
}

var_dump(get_defined_vars());
?>

PS: If you can handle sub-pixel rendering then go with float point values. Such points are often to be blurry yet good overall effects.

Upvotes: 0

static_rtti
static_rtti

Reputation: 56292

If you have lots of points, the result is going to look like an hexagonal grid:

http://people.sc.fsu.edu/~jburkardt/m_src/hex_grid/hex_grid.html

Otherwise it gets more complicated. One algorithm that works very nicely (but is probably overkill), is to do a physics simulation where points are particles that repel each other. Check out this video that does the same on a sphere for an example.

Upvotes: 1

Related Questions