Making polygon shapefile from unsorted point shapefile?

I have a point Shapefile with unsorted feature ID's (FID). I want to convert the same point file into polygon Shapefile by using python gdal/ogr. I got the help from link1 and link2. I'm able to make polygon shapefile successfully but because of my unsorted point Shapefile the output of polygon shapefile is irregular (not as expected). Expected polygon shapefile is ring/polygon/box around points .

. Is there any way to sort point shapes as right to left or left to right before making polygon Shapefile?

• The definition of a polygon asserts that the vertex list is ordered. Randomly organized points can't be reliably sorted to form polygons. You can generate a convex hull, or it's sibling, a concave hull, but points within the polygon will be dropped. Aug 16, 2019 at 10:38
• Ya convex hull drops the intermediate points. But I want to do more precisely. Aug 16, 2019 at 10:46
• Right. So you have an impossible task, or at least an NP-Complete one. Aug 16, 2019 at 10:50

My idea is to order point coordinates by its longitude and latitude in this way:

1. Sort by longitude, in for loop iterate over the coordinates while longitude ascends;
2. Then iterate while latitude descends;
3. etc...

Then merge lists with coordinates and create polygon.

Not pretend this is the most elegant solution, maybe you send your data so I will test my idea

• Your idea is good but I had more than one lakh random points. How I can sort ? Aug 16, 2019 at 9:33
• stackoverflow.com/a/37111840/8129993 answer about sorting coordinates. My idea is to create lists first (with ascending\descending longitude\latitude) and sort coordinates inside
– Jane
Aug 16, 2019 at 9:40
• I have tried, The sorting of coordinates is good for the points in a path but my points are around the box. Aug 16, 2019 at 10:05