3 ms·

If you have the points in order, you can do it using the rotating calipers method [1] in O(n). In the case from the article, you would have to remove the interi

If you have the points in order, you can do it using the rotating calipers method [1] in O(n). In the case from the article, you would have to remove the interior lines, but I guess this could also be done in O(n) as the points on interior lines are the points appearing more than once [2]. [1] https://en.wikipedia.org/wiki/Rotating_calipers https://en.wikipedia.org/wiki/Rotating_calipers [2] At least almost, the first and last point of interior lines are also part of the outer line.

piotrjaw 4y ago
Indeed, but the convex hull approach also works for multiple sets of points, in any order. As for [2], in the article the data is separated into 16 polygons, so the interior lines are actually shared between polygons. It's still possible to union the polygons, but it takes more time than calculating the convex hull.