[futurebasic] natural tilings

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : May 1999 : Group Archive : Group : All Groups

From: Laurent Siebenmann <Laurent.Siebenmann@...>
Date: Sun, 30 May 1999 04:25:17 +0200 (MET DST)

[apologies if this is a repeat from about a week ago]

Dear Robert Covington,

 > It would be nice to feed in a "point cloud" as it is
 > called in 3D vernacular in either 2D XY pts or 3D XYZ pts
 > and be able to have a routine that will mesh that into the
 > proper shape automatically.

This is probably subject of a lot of programming technology, 
so regard my suggestion below as naive and uninformed.

Consider a finite set of points in the plane (cloud). There is a very simple and
natural algorithm that leads not to a triangulation with the given
vertices but to a tiling of the plane with one convex polygonal tile
containing each given point in its interior.  The tile T for point P is
the set of all points that are nearer to P than to any other point in the
cloud.  Each face of the tile T is a segment in the line of points that 
lie equidistant between P and some other point Q of the cloud, and that 
suggests the algorithm.  From a tiling one can go on to a triangilation
with some extra vertices but maybe the tiling is what you really need...

T is called the Diriclet region of P for the given cloud of points.
Or the Voronoi region.  These ideas work in any dimension.


                                Larry Siebenmann