Search code examples
algorithmgeometrygraph-algorithmcomputational-geometry

Algorithm for creating a specific geometric structure

I observed some applications create a geometric structure apparently by just having a set of touch points. Like this example:

Sample example

I wonder which algorithms can possibly help me to recreate such geometric structures?

UPDATE

In 3D printing, sometimes a support structure is needed:

Support tags in 3D print SE site

The need for support is due to collapse of some 3D object regions, i.e. overhangs, while printing. Support structure is supposed to connect overhangs either to print floor or to 3D object itself. The geometric structure shown in the screenshot above is actually a sample support structure.

Solution

  • I am not a specialist in that matter and I may be missing important issues. So here is what I would naively do.

    The triangles having a external normal pointing downward will reveal the overhangs. When projected vertically and merged by common edges, they define polygonal regions of the base plane. You first have to build those projected polygons, find their intersections, and order the intersections by Z. (You might also want to consider the facing polygons to take the surface thickness into account).

    Now for every intersection polygon, you draw verticals to the one just below. The projections of the verticals might be sampled from a regular grid or elsehow, to tune the density. You might also consider sampling those pillars from the basement continuously to the upper surface, possibly stopping some of them earlier.

    The key ingredient in this procedure is a good polygon intersection algorithm.