## Filling a set of 3d points with spheres (or better, blobs)

### Filling a set of 3d points with spheres (or better, blobs)

Hi,

Is there an algorithm, probably based on some linear programming,
that can give me an approximation of the volume defined by a set of 3d
points (more or less representing a 2d cover such as skin of a human...)
which can be an alpha shape, with spheres or blobs? I figure this would have
to be an approximation, probably similar to the backpack filling problem,
which is NP-complete but that does have linear programming variants that do
not give a perfect solution...

Marc
--
"Error #132: Cannot exit from Windows, try the door"
Edouard Shtrutsrup, "Jokes only programmers can understand"
Marc Sokolowski

### Filling a set of 3d points with spheres (or better, blobs)

>    Hi,

>    Is there an algorithm, probably based on some linear programming,
>that can give me an approximation of the volume defined by a set of 3d
>points (more or less representing a 2d cover such as skin of a human...)
>which can be an alpha shape, with spheres or blobs? I figure this would have
>to be an approximation, probably similar to the backpack filling problem,
>which is NP-complete but that does have linear programming variants that do
>not give a perfect solution...

Edouard Shtrutsrup, "Jokes only programmers can understand"

>Marc Sokolowski

The following paper describes the use of the divergence theorem to calculate
volume from points if you have a surface normal at each point:

D. Eberly, J. Lancaster, A. Alyassin, "On gray scale image
measurements, II. Surface area and volume",  CVGIP: Graphical
Models and Image Processing, vol. 53, no. 6, pp. 550-562, 1991.

--
Bill Lorensen
US Mail:GE Corporate Research and Development
Bldg KW Room C215
Office: (518) 387-6744 or 8*833-3874
Fax:    (518) 387-6560 or 8*833-6560

Hi,

Is there an algorithm, probably based on some linear programming,
that can give me an approximation of the volume defined by a set of 3d
points (more or less representing a 2d cover such as skin of a human...)
which can be an alpha shape, with spheres or blobs? I figure this would have
to be an approximation, probably similar to the backpack filling problem,
which is NP-complete but that does have linear programming variants that do
not give a perfect solution...

Marc
--
"Error #132: Cannot exit from Windows, try the door"
Edouard Shtrutsrup, "Jokes only programmers can understand"
Marc Sokolowski