4

Im using Shapely library to deal with polygons. It has class called Polygon which gets an ordered set of coordinates and turns them into a polygon.
The problem is that I got set of unordered coordinates. I want polygon which wraps all of the points.

I have been looking into Shapley documentation, but I can't find any information about how to do it

Is there an algorithm to order the points before sending them to Polygon? Or is there another method I can do that?

UdiM
  • 480
  • 3
  • 19
  • There can be many ways to build polygons from a set of points, so how would any algorithm be able to decide how to order them? – Thierry Lathuille Jul 21 '20 at 10:01
  • Is your polygon convex? In this case you can compute convex hull and pass that on. – ypnos Jul 21 '20 at 10:02
  • @ThierryLathuille You are right, I didn't mention that. I meant for a polygon which wraps the points – UdiM Jul 21 '20 at 10:04
  • 1
    That would be the convex hull, then. – Thierry Lathuille Jul 21 '20 at 10:04
  • 1
    In 2D you can sort the points by polar coordinates to find the order as [described here](https://stackoverflow.com/questions/10846431/ordering-shuffled-points-that-can-be-joined-to-form-a-polygon-in-python) – DarrylG Jul 21 '20 at 10:09

1 Answers1

7

You can create a convex hull around the points but it will not ignore the points that are inside the hull

example from https://shapely.readthedocs.io/en/latest/manual.html#object.convex_hull

MultiPoint([(0, 0), (1, 1)]).convex_hull
Hicham Zouarhi
  • 1,030
  • 1
  • 18
  • 28