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

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

Post by Marc Sokolows » Mon, 28 Aug 1995 04:00:00



        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)

Post by Bill Lorense » Tue, 29 Aug 1995 04:00:00



>    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
                1 River Road
                Bldg KW Room C215
                Schenectady, NY 12345
        Office: (518) 387-6744 or 8*833-3874
        Fax:    (518) 387-6560 or 8*833-6560


 
 
 

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

2. ATM 4.0--how well does it work?

3. Set of balls (or even better blobs) enclosing a 3d set of points

4. creating class not registered failed error

5. Who's going to Macworld?

6. Spheres or blobs (POV) inside a volume defined by 3d points

7. Fill polygon with points on sphere

8. Regular Grids on Spheres / Sphere Tilings / Equal distribution of points on a sphere

9. Single pass bounding sphere of set of points

10. smallest sphere enclosing a set of points