sbj@psuhcx (Sanjay B. Joshi) (02/02/89)
I am looking for any references or pointers on the following problem: Given N points, how can they be distributed over a given bounded plane/surface such that the distribution is fairly uniform, and no two points are closer than a certain given amount. For example, given a L shaped polygon, how to distribute 50 points on it, such that no two points are less than delta distance from each other. thanks, sanjay.
skinner@saturn.ucsc.edu (Robert Skinner) (02/03/89)
In article <1169@psuhcx.psu.edu>, sbj@psuhcx (Sanjay B. Joshi) writes: > > Given N points, how can they be distributed over a given bounded plane/surface > such that the distribution is fairly uniform, and no two points are closer than > a certain given amount. > I have worked on a similar problem: how to generate variable density Poisson-disk distributions for planting patterns. I adapted something that Don Mitchell used for generating Poisson-disk distributions for ray tracing. He took a random input source around the value 1/16, sampled it 16 times the input resolution and dithered it down to one bit. The result was about 1 bit generated per image pixel. You can dither over a rectangle surrounding the surface, and accept points lying inside the surface. Pick a sample size so that the sample area times density is about 1/16. The point density is simply the number of points divided by the area of the surface. This generates nice patterns and isn't too expensive. (At least its not iterative.) I have used it on trianlges with variable density. Surprisingly, the points generated were clustered tightly around the high density areas. (Even more than the variable density would seem to indicate.) The correct number of points were generated, as measured by the integral of the density. References: Don Mitchell, "Generating Antialiased Images at Low Sampling Densities", Computer Graphics, v 21, # 4, p 65-72, 1987. R. W. Floyd, L. Steinberg, "An Adaptive Algorithm for Spatial Greyscale", Society for Information Display Symposium Digest, p 36-37, 1975. good luck, Robert Skinner skinner@saturn.ucsc.edu