0

I am in the situation that I have $n$ boundary points of a polygon in the plane.

Then, there is an explicit formula the so-called Shoelace formula to compute the area of the polygon

Fastest way to Shoelace formula

The nice property is that the boundary points do not have to be ordered.

However, I am wondering if there also exists a similar simple algorithmtic way to compute the perimeter of the polygon just from the set of (possibly unordered) boundary points?

Sascha
  • 133
  • 5
  • Isn't the perimeter just the sum of the lengths of the line segments? – Cory Kramer Aug 25 '21 at 14:14
  • sure but if I give you just the boundary points without telling you which one is connected to which, I am not sure how one would do it then... – Sascha Aug 25 '21 at 14:15
  • 2
    In that case the polygon is underspecified. You *must* specify the order or you have not given the polygon a topology. Unless you want to define the area and perimeter of the "convex hull" of the polygon, for example. – Cory Kramer Aug 25 '21 at 14:16
  • @CoryKramer yes, we are indeed then talking about the convex hull – Sascha Aug 25 '21 at 14:17
  • In that case [Graham scan](https://en.wikipedia.org/wiki/Graham_scan) is a fairly popular convex hull algorithm, and pretty simple to code. Once you have the convex hull, then you just sum the lengths of the edges. – Cory Kramer Aug 25 '21 at 14:17
  • 1
    Then grab Scipy for computing the convex hull: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html – AKX Aug 25 '21 at 14:18

0 Answers0