Search code examples
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

  • A starting point of the red curve can be given
  • I am interested in efficient ideas to build up a generic algorithm however...
  • I am coding in C++ and I can use any opensource library to help with this
  • I do not know if this problem has a name or if there is a ready-made solution, in case please let me know and I will edit the title and the tags.

Additional notes:

  • The solution is unique as in the region of interest there is only a single connected area which is free from any curve, but of course I can only compute a finite number of curves.
  • The curves are originally parametrized (and then affine transformations are applied), so I can add as many point as I want. I can compute distances, lengths and go along with them. Intersections are also feasible. Basically any geometric operation that can be built up from point coordinates is acceptable.
  • I have found that a similar problem is encountered when "cutting" gears eg. https://scialert.net/fulltext/?doi=jas.2014.362.367, but still I do not see how to solve it in a decently efficient way.
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.