Finding edges of a non self-intersecting polygon from given vertices

Question

I have the vertices of a non-self-intersecting polygon in 2-D where the x-coordinate is centred longitude and y-coordinate is centred latitude. I want to find the edges of the polygon.

I can plot the vertices and see which vertices are neighbouring and see the edges. But my question is how can I get these edges.

For example, I am considering the sample data:

> data1
    vertices       lon      lat
       5         1.133179 1.027886
       4         1.094459 1.013952
       2         1.055672 1.000000
       1         1.000000 1.028578
       3         1.038712 1.042541
       6         1.116241 1.070438

Sample Plot of the points is

enter image description here

I want to have an array like this

>edges 
      ind1 ind2
[1,]    5    6
[2,]    1    3
[3,]    3    6
[4,]    1    2
[5,]    2    4
[6,]    4    5

I am interested about this kind of shape of the polygon (with minimum area) enter image description here

I got this array by using a function ashape of the R-package alphahull. But in this function Euclidean distance is used to find distance between points, which not applicable in my case (since I am considering data on (lon, lat), we can use distHaversine distance function in the package geosphere). And this function giving unsatisfactory result in case if the polygon has large number vertices and have complex shape. This polygon may or may not be convex.

Now all I want is to build an algorithm to find the edges of the non-intersecting polygon with minimum area.

Any help in this direction will be gratefully appreciated.

Even if they are same using 'ashape' function for finding the edges is not giving the satisfactory result for large data set. — Janak
@janak by large you mean size or point count or point density? polygon is convex or concave? if concave what is the constraint or rule for shape (with more points there is higher number of possible polygons so you need to specify some conditions to select the right one)? — Spektre
@Spektre Here by large I meant the polygon has large number vertices. This polygon may or may not be convex. I edited my question. — Janak

agentp agentp · Accepted Answer · 2014-11-21T19:30:22

Algorithm for finding all possible polygons:

generate the convex hull . Note that any non intersecting polygon must traverse its convex hull in order.
Start with any point on the convex hull Generate a list of paths from that point to each interior point, and to the next adjacent point on the convex hull
recursively extend each path to each remaining interior point as well as to that first free point on the convex hull
for each segment added to a path reject the path if it self intersects

I'm not going to post the code, but here are all 67 possible polygons for a random set of 8 points. As one can imagine the set of results blows up quickly with the number of points (eg. n=12 -> ~10000 polygons.. )

enter image description here

here are the polygons with min and max perimeters.

enter image description here

Finding edges of a non self-intersecting polygon from given vertices

2 Answers