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?

Answer 1

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.)

Answer 2

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