27079

Distributing points over a surface within boundries

Question:

I'm interested in a way (algorithm) of distributing a predefined number of points over a 4 sided surface like a square.

The main issue is that each point has got to have a minimum and maximum proximity to each other (random between two predefined values). Basically the distance of any two points should not be closer than let's say 2, and a further than 3.

My code will be implemented in ruby (the points are locations, the surface is a map), but any ideas or snippets are definitely welcomed as all my ideas include a fair amount of brute force.

Answer1:

Try <a href="http://diwww.epfl.ch/w3lsp/publications/colour/prhsfcabp_93.html" rel="nofollow">this paper</a>. It has a nice, intuitive algorithm that does what you need.

<blockquote>

In our modelization, we adopted another model: we consider each center to be related to all its neighbours by a repulsive string.

At the beginning of the simulation, the centers are randomly distributed, as well as the strengths of the strings. We choose randomly to move one center; then we calculate the resulting force caused by all neighbours of the given center, and we calculate the displacement which is proportional and oriented in the sense of the resulting force.

After a certain number of iterations (which depends on the number of centers and the degree of initial randomness) the system becomes stable.

</blockquote>

In case it is not clear from the figures, this approach generates uniformly distributed points. You may use instead a force that is zero inside your bounds (between 2 and 3, for example) and non-zero otherwise (repulsive if the points are too close, attractive if too far).

This is my Python implementation (sorry, I don´t know ruby). Just import this and call uniform() to get a list of points.

import numpy as np from numpy.linalg import norm import pylab as pl # find the nearest neighbors (brute force) def neighbors(x, X, n=10): dX = X - x d = dX[:,0]**2 + dX[:,1]**2 idx = np.argsort(d) return X[idx[1:11]] # repulsion force, normalized to 1 when d == rmin def repulsion(neib, x, d, rmin): if d == 0: return np.array([1,-1]) return 2*(x - neib)*rmin/(d*(d + rmin)) def attraction(neib, x, d, rmax): return rmax*(neib - x)/(d**2) def uniform(n=25, rmin=0.1, rmax=0.15): # Generate randomly distributed points X = np.random.random_sample( (n, 2) ) # Constants # step is how much each point is allowed to move # set to a lower value when you have more points step = 1./50. # maxk is the maximum number of iterations # if step is too low, then maxk will need to increase maxk = 100 k = 0 # Force applied to the points F = np.zeros(X.shape) # Repeat for maxk iterations or until all forces are zero maxf = 1. while maxf > 0 and k < maxk: maxf = 0 for i in xrange(n): # Force calculation for the i-th point x = X[i] f = np.zeros(x.shape) # Interact with at most 10 neighbors Neib = neighbors(x, X, 10) # dmin is the distance to the nearest neighbor dmin = norm(Neib[0] - x) for neib in Neib: d = norm(neib - x) if d < rmin: # feel repulsion from points that are too near f += repulsion(neib, x, d, rmin) elif dmin > rmax: # feel attraction if there are no neighbors closer than rmax f += attraction(neib, x, d, rmax) # save all forces and the maximum force to normalize later F[i] = f if norm(f) <> 0: maxf = max(maxf, norm(f)) # update all positions using the forces if maxf > 0: X += (F/maxf)*step k += 1 if k == maxk: print "warning: iteration limit reached" return X

Answer2:

I presume that one of your brute force ideas includes just repeatedly generating points at random and checking to see if the constraints happen to be satisified.

Another way is to take a configuration that satisfies the constraints and repeatedly perturb a small part of it, chosen at random - for instance move a single point - to move to a randomly chosen nearby configuration. If you do this often enough you should move to a random configuration that is almost independent of the starting point. This could be justified under <a href="http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm</a> or <a href="http://en.wikipedia.org/wiki/Gibbs_sampling" rel="nofollow">http://en.wikipedia.org/wiki/Gibbs_sampling</a>.

Answer3:

I might try just doing it at random, then going through and dropping points that are to close to other points. You can compare the square of the distance to save some math time.

Or create cells with borders and place a point in each one. Less random, it depends on if this is a "just for looks thing" or not. But it could be very fast.

Answer4:

I made a compromise and ended up using the Poisson Disk Sampling method.

The result was fairly close to what I needed, especially with a lower number of tries (which also drastically reduces cost).

Recommend

  • Push Notification inside ScheduledAgent in Windows Phone 8
  • How to create %tab% in CMD
  • How to fix “refusing to merge unrelated histories” when uploading project to github?
  • GroupBy on multiple columns and apply moving function
  • how to display a image over a map with imshow?
  • React Native: Propagate Pan Responder event from view to inner scroll view
  • Webservice cannot be serialized because it does not have a parameterless constructor
  • Generic SQL builder .NET
  • ExtJS 3.3 Format.Util.Ext.util.Format.dateRenderer returning NaN
  • gcc suppress warning “too small to hold all values of”
  • Unit test the Automapper profiles
  • Linux rename files as dirname
  • move TRectangle with mouse (FMX, Win32)
  • R: Quanteda's textstat_simil function
  • aspnet core 2.2 External Authentication
  • Move the coupon field to the cart totals
  • Post method on Angular 5. No error but it doesn't work
  • Avoiding administrator access for SslStream.AuthenticateAsClient?
  • How do I get feedback about DSC execution on an Azure VM?
  • Make Friend the constructor of a template class
  • Extracting a date from string
  • Stateful processing in Beam - is state shared across window panes?
  • Get Element By Classname Script Not Working
  • Pass multiple lines of stdin input to interactive Java command line program, non-interactively
  • Salesforce API: How to identify a Case from an email reference code (“[Ref: … :Ref]”)?
  • Identify File Type in Java
  • Android NDK refer to external libraries in JNI
  • Enable CORS on Tomcat 8.0.30
  • How to get File path from pdfUri obtained from PDF chooser intent library, in onActivityResult call
  • internal javascript not works in angular2
  • Stop an element moving with padding on hover
  • Neo4j…how to get a visual representation of my data?
  • Python 3x- Compression Makes File Bigger :(
  • Using redis as an LRU cache for postgres
  • Bad automatic Triangulation with Mayavi for coloring a surface known only by its corner