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

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