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, Nov 19 '14 at 08:21
@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, Nov 19 '14 at 08:56
@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, Nov 19 '14 at 09:06
If your polygon is always convex, you can use convex hull algorithm to find the edges. If your polygon could be concave, then there could be more than one solution, you need to have more criteria (e.g. the one with minimum area) to isolate the solution you want. — fang, Nov 19 '14 at 20:30
The polygons which I am dealing with, may be concave, convex or neither of two. I have a criteria that the polygon has minimum area. I edited the question. Thank you. — Janak, Nov 20 '14 at 02:57
I seem to recall you get "a" solution by finding the convex hull, and successively finding the convex hull of the remaining points and linking together the resulting set of convex "rings"-- this can be far from the minimum area however. (search on this site, I'm sure this has come up before ) I suspect to deterministically find the minimum area result in the general case you will actually need to scan through every possible ordering. — agentp, Nov 20 '14 at 21:50

score 1 · Accepted Answer · answered Nov 21 '14 at 19:30

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

score 0 · Answer 2 · edited May 23 '17 at 10:33

convert points from lon,lat to Cartesian x,y or x,y,z
- use spherical or ellipsoidal surface
- if the size is small enough you can project (x,y,z) to local surface plane to avoid 3D computing
- you can also use lon,lat as x,y but make sure there is no zero crossing (if is then offset that axis by some value until it isn't)
now there are many possible strategies
- you did not provide any rule for the shape
- so I assume 'minimal' perimeter/size/area and generic concave polygon
- you can not go directly to edge lines before you know where is inside and where is outside
- I would do this task like this: find polygon based on find holes in 2D point set
modification 1
- as you already have all the edge points (at least that is my impression)
- so you can make flag for each point from the above algorithm
- that will tell you where is inside or outside of polygon
- for example take 8 directions (N,NE,E,...) and encode which way is filled and which empty
- then on each edge start in the middle of empty direction
- and find 2 closest lines to it (in angular terms) that are not intersecting any previous line
- and if more available use the smallest ones
- gray means inside polygon
- make list of all such possible lines (2 per point)
- then search for connected loops
- beware this modification is not 100% error prone (I do not think that is for concave polygon even possible)
modification 2
- use complete polygon from bullet 2
- and try to match its edge points to your input edge points
- then use the edge lines as in original polygon but with your new points
- if some points are skipped then find closest edge line to it and divide it by this point
- this should be more safe and accurate then bullet 3.

simple approach

if the above is too much for you then
1. create list of all possible lines
2. sort them by size ascending
3. remove all 'long' lines that are intersecting any 'short' line
  - what is short or long depends on you
  - for example first third of lines can be the short ones and the last third the long ones
  - or make average size and what is < 0.6*avg_size or > 1.2*avg_size ...
  - or if you have N points then first 2N lines are short the rest is long (2 lines per point)
  - test all and select the best option for you ...
4. try to find joined lines
  - find only lines that are connected once (no more then 2 lines per point)
  - remove them from list into the final solution list
  - after this you will have list of possible lines and list of found lines
5. remove all lines from possible lines that intersect any line in found lines
  - this should remove any non relevant lines
6. try to find connections again
  - take first possible line if found connection move it to the solution list
  - and go to bullet 5.
  - if none found continue with next line ...
  - stop if none line left or none connection found.

@janak I think bullet 2 and bullet 4 are the safest you can do. Bullet 2 will allways find some solution but a bit aliased by the map resolution. Bullet 4 should find your desired polygon but never tried that one. In the last simple approach there can be problems that without some aditional heuristics it will give wrong answers especially for complex polygons — Spektre, Nov 19 '14 at 09:18
Though in the given sample I only posted a very simple polygon but generally polygons I am interested in has complex shape. — Janak, Nov 19 '14 at 09:31
@janak btw I forgot when you compute the map by edge points only then you have to flood fill the inside holes before using it (that algo was created for average point density ... (just that you know what is happening) also the points should cover some circle inside map so it will overlap if the points are too sparse ... — Spektre, Nov 19 '14 at 10:55

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

2 Answers2