2

It might seem a bit odd that I am asking for python code to calculate the area of a polygon with a list of (x,y) coordinates given that there have been solutions offered in stackoverflow in the past. However, I have found that all the solutions provided are sensitive to the order of the list of (x,y) coordinates given. For example, with the code below to find an area of a polygon:

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                             for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])


coordinates1 = [(0.5,0.5), (1.5,0.5), (0.5,1.5), (1.5,1.5)]
coordinates2 = [(0.5,0.5), (1.5,0.5), (1.5,1.5), (0.5,1.5)]

print "coordinates1", area(coordinates1)
print "coordinates2", area(coordinates2)

This returns

coordinates1 0.0
coordinates2 1.0  #This is the correct area

For the same set of coordinates but with a different order. How would I correct this in order to get the area of the non-intersecting full polygon with a list of random (x,y) coordinates that I want to make into a non-intersecting polygon?

EDIT: I realise now that there can be multiple non-intersecting polygons from a set of coodinates. Basically I am using scipy.spatial.Voronoi to create Voronoi cells and I wish to calculate the area of the cells once I've fed the coordinates to the scipy Voronoi function - unfortunately the function doesn't always output the coordinates in the order that will allow me to calculate the correct area.

piccolo
  • 2,093
  • 3
  • 24
  • 56
  • 1
    You, you are looking for the [convex hull](https://en.wikipedia.org/wiki/Convex_hull)? – tobias_k Jan 21 '16 at 13:51
  • Thanks for yout comment @tobias_k I have included an edit which explains my problem a bit better. I am reading your link to see whether the convex hull is the accurate description for my problem. – piccolo Jan 21 '16 at 14:29
  • hi @tobias_k is there anyway I can resort my list to get the required area? – piccolo Jan 21 '16 at 16:11

2 Answers2

5

Several non-intersecting polygons can be created from a random list of coordinates (depending on its order), and each polygon will have a different area, so it is essential that you specify the order of the coordinates to build the polygon (see attached picture for an example). This two polygons have the same coordinates but different area

  • Or maybe OP is looking or the convex hull, i.e. without any of the "dents". – tobias_k Jan 21 '16 at 14:02
  • @tobias_k Basically I am making Voronoi cells out of a set of coordinates. Unfortunately, the scipy Voronoi function doesn't output the coordinates in the correct order. – piccolo Jan 21 '16 at 14:21
  • Hi @BlackAdder I've included an EDIT in my original post which explains the problem a bit better. – piccolo Jan 21 '16 at 14:31
2

The Voronoi cells are convex, so that the polygon is unambiguously defined.

You can compute the convex hull of the points, but as there are no reflex vertices to be removed, the procedure is simpler.

1) sort the points by increasing abscissa; in case of ties, sort on ordinates (this is a lexicographical ordering);

2) consider the straight line from the first point to the last and split the point sequence in a left and a right subsequence (with respect to the line);

3) the requested polygon is the concatenation of the left subsequence and the right one, reversed.

enter image description here

  • Hi @Yves if I resort my list according to your procedure can I then use the code in the OP to calculate the desired area of the polygon? – piccolo Jan 21 '16 at 16:02
  • I meant resort my list according to step1 of your procedure. – piccolo Jan 21 '16 at 16:14
  • @user2443944: of course, this formula works with all polygons. But you need the three steps. –  Jan 21 '16 at 16:14
  • Okay just to make sure - If I resort my list by increasing abscissa then can I use the code in the OP to get the desired polygon area for the Voronoi cells case? – piccolo Jan 21 '16 at 16:16
  • @user2443944: NO. You need the three steps. –  Jan 21 '16 at 16:18