[comp.graphics] distributing points on a surface

sbj@psuhcx (Sanjay B. Joshi) (01/27/89)

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.


sanjay.

cjp@antique.UUCP (Charles Poirier) (02/01/89)

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..."

rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (02/02/89)

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.

You might considering using an automatic mesh generator for Finite Element
methods to do this.  You would need only to generate the nodes and not the
elements.  There are a number of approaches described in various
journals, and if you're interested I could send you a reference list.  A
good starting paper is,

Title:    Automatic Finite-Element Mesh generation from Geometric models - 
          A point-based approach.
Authors:  Y. T. Lee, A. De Pennington and N. K. Shaw
Journal:  ACM Transactions on Graphics, Vol. 3, No. 4, Oct. 1984, pp 287-311.

Planar polygons that are made up of straight line edges are relatively easy
to mesh, while curved portions of the boundary are slightly more complex.

Enjoy.

							-- Vallury Prabhakar