c++algorithmcomputational-geometryenvelope

Which algorithm or idea to find the convex envelope of a set of curves?

Let's define a curve as set of 2D points which can be computed to arbitrary precision. For instance, this is a curve:

enter image description here

A set of N intersecting curves is given (N can be arbitrarily large), like in the following image:

enter image description here

How to find the perimeter of the connected area (a bounding box is given if necessary) which is delimited by the set of curves; or, given the example above, the red curve? Note that the perimeter can be concave and it has no obvious parametrization.

enter image description here

Additional notes:

Solution

  • If the curves are given in order, you can find the pairwise intersections between successive curves. Depending on their nature, an analytical or numerical solution will do.

    Then a first approximation of the envelope is the polyline through these points.

    Another approximation can be obtained by drawing the common tangent to successive curves, and by intersecting those tangents pairwise. The common tangent problem is more difficult, anyway.

    If the equations of the curves are known in terms of a single parameter, you can find the envelope curve by solving a differential equation, obtained by eliminating the parameter between the implicit equation of the curve and this equation differentiated wrt the parameter. You can integrate this equation numerically.