Convex hull area in Python?

Question

I have a set of points A. I get the convex hull CH_A of A.

Then, I have extra points, point set B. I add B into A and get a bigger point set. I obtain the convex hull CH_AB of this bigger set containing both A and B.

I want to quantify how much I have to pay to add B into set A. I am thinking about using an additional area to quantify this cost.

Say CH_A has an area of Area_A, then CH_AB has an area of Area_AB. Then, I want to calculate the marginal cost as

(Area_AB - Area_A) / Area_A

How may I get the area of the convex hull in Python?

score 32 · Answer 1 · edited Feb 17 '20 at 13:05

You could just use the ConvexHull class from scipy.spatial. It will not only give you the hull's area, but it will compute the hull for you as well. But if you do use it, BEWARE! In 2D, the attribute you want to use is not area, it is volume, because the former will actually give you the hull's perimeter.

That's because the attributes are named after their values in 3D, where area will indeed be the hull's area, and volume, well, its volume. For 2D hulls, the names are the same, but what they actually contain is not quite what it says on the tin. Worse, the documentation does not warn you about this.

(You can easily check this with trivial examples such as an isosceles right triangle of length 1 on its legs: the perimeter should be 2+sqrt(2), or about 3.414213562, and the area should be 0.5.)

score 18 · Accepted Answer · edited May 23 '17 at 12:24

18

Convex hull is simply a convex polygon so you can easily try {this} or {this} to find area of 2D polygon.

Something like the following (our version):

def PolyArea2D(pts):
    lines = np.hstack([pts,np.roll(pts,-1,axis=0)])
    area = 0.5*abs(sum(x1*y2-x2*y1 for x1,y1,x2,y2 in lines))
    return area

in which pts is array of polygon's vertices i.e., a (nx2) array.

Full usage:

import numpy as np

def PolyArea2D(pts):
    lines = np.hstack([pts,np.roll(pts,-1,axis=0)])
    area = 0.5*abs(sum(x1*y2-x2*y1 for x1,y1,x2,y2 in lines))
    return area

pts = [[0,0],[1,0],[1,1],[0,1]]
print PolyArea2D(pts)    

pts = [[0,0],[1,0],[0,1]]
print PolyArea2D(pts)    

pts = [[0,0],[1,0],[0.5,0.5]] 
print PolyArea2D(pts)    

>>>
1.0
0.5
0.25

edited May 23 '17 at 12:24

Community

1
1

answered Nov 09 '13 at 11:37

Developer

8,258
8
49
58

2

nice and clear answer. One issue though: the function name starts with an uppercase! :-) – Juh_ Jun 02 '14 at 10:49
If I give add a point that's inside the bigger polygon, the answer would change. Say, `pts = [[0,0],[1,0],[1,1],[0,1]] print PolyArea2D(pts) #1.0` but `pts = [[0,0],[1,0],[1,1],[0,1],[0.5,0.5]] print PolyArea2D(pts) #0.75` – Abhishek Reddy Jun 03 '16 at 12:50
I see this algorithm computing the area of a polygon given its vertices, but where does it compute the complex hull? – Pere Mar 26 '19 at 21:46

Convex hull area in Python?

2 Answers2

Linked