How to circle multiple points on a map?

Question

Algorithms

There are many points. How to circle this set at the extreme points?
It is desirable that you can specify the maximum distance to a neighboring point.

This is the range I would like to have.


Is there a name for the algorithm?

Answer 1

Here is an algorithm for selecting the faces of a planar graph: https://e-maxx.ru/algo/facets
First you have to intersect segments with each other and get a graph: vertices - intersection points and ends of segments, edges - pieces of segments. Then select the outer and inner faces with the algorithm above.
Then you smooth them out. The outer edge is outward, the inner edge is inward. Here it is necessary to act somehow heuristically. For example, take any point on the contour, if two of its neighbors are close enough, then throw out the current point. If the inner face becomes small enough in area, discard it entirely.
Upd: Addition - you can only throw out points that are "concave" inside the polygon, such that deleting them will only make the outer part larger and the inner one smaller.
As a result, if you successfully select the boundaries in the algorithm above, you will get something like in your picture.