Path: utzoo!utgpu!watmath!clyde!att!homxb!antique!cjp
From: cjp@antique.UUCP (Charles Poirier)
Newsgroups: comp.graphics
Subject: Re: distributing points on a surface
Summary: Simulated Annealing
Message-ID: <2528@antique.UUCP>
Date: 1 Feb 89 00:05:53 GMT
References: <1163@psuhcx.psu.edu>
Reply-To: vax135!cjp (Charles Poirier)
Organization: AT&T Bell Labs, Holmdel, NJ
Lines: 33

In article <1163@psuhcx.psu.edu> sbj@psuhcx (Sanjay B. Joshi) writes:
>Does any body out there know of any algorithms capable of distributing a
>given number of points on a planar/curved surface in a uniform manner, where
>uniform could be defined such that no two points are closer than a given value.
>
>The planar/curved surface is bounded and non convex.
>
>For example, given 50 points how does one distribute them on an L shaped
>polygon, such that the distribution is fairly uniform.

If you are not in a great hurry, a Simulated Annealing formulation would
probably work well for a great variety of surfaces.  Basically like this:

    put all points randomly anywhere within the bounded surface
    for (T = hot; T > cold && ! quality_acceptable; T *= decay_constant)
	for N_iterations_at_temperature_T
	    do
		pick a random point to move
		pick a random direction and distance to move it along the surface
	    until you have a move that stays within the surface boundaries.
	    compute Q = improvement in global quality if that move were made.
	    if Q > 0, make that move (improvement)
	    else if rnd(0.0 to 1.0) < exp(Q/T) make that move (thermal motion)
	    else leave the point alone.

The parameters have to be hand-tuned to make it work well, and you'll 
need methods for a quick measure of "quality" (distance to nearest neighbor)
and for perturbing the point positions along the surface.

-- 
	Charles Poirier   (decvax,ucbvax,mcnc,attmail)!vax135!cjp

   "Docking complete...       Docking complete...       Docking complete..."