Discrete Convex Hull

Question

In python, given m random points in an n x n grid, how do I calculate a (roughly) convex hull where the hull can only be created using the points on the discrete grid rather than a continuous point?

modules like scipy.spatial only give continuous convex hulls, where the lines connecting vertices are purely algebraic, but I want approximately a convex hull where the boundary is discrete.

Paul Panzer Paul Panzer · Accepted Answer · 2018-06-12T05:55:55

You can still use qhull + some post processing:

import numpy as np
from scipy.spatial import ConvexHull

# https://stackoverflow.com/a/47705495/7207392
def connect2(ends):
    d0, d1 = np.diff(ends, axis=0)[0]
    if np.abs(d0) > np.abs(d1): 
        return np.c_[np.arange(ends[0, 0], ends[1,0] + np.sign(d0), np.sign(d0), dtype=np.int32),
                     np.full(np.abs(d0)+1, ends[0, 1]) if d1==0 else
                     np.arange(ends[0, 1] * np.abs(d0) + np.abs(d0)//2,
                               ends[0, 1] * np.abs(d0) + np.abs(d0)//2 + (np.abs(d0)+1) * d1, d1, dtype=np.int32) // np.abs(d0)]
    else:
        return np.c_[np.full(np.abs(d1)+1, ends[0, 0]) if d0==0 else
np.arange(ends[0, 0] * np.abs(d1) + np.abs(d1)//2,
                               ends[0, 0] * np.abs(d1) + np.abs(d1)//2 + (np.abs(d1)+1) * d0, d0, dtype=np.int32) // np.abs(d1),
                     np.arange(ends[0, 1], ends[1,1] + np.sign(d1), np.sign(d1), dtype=np.int32)]

def dch(points):
    ch = ConvexHull(points)
    n = len(ch.vertices)
    return np.concatenate([connect2(points[ch.vertices[[i, (i+1)%n]]])[:-1] for i in range(n)], axis=0)

points = np.argwhere(np.random.random((24, 24)) < 0.03)
import pylab
pylab.plot(*dch(points).T, 'bo')
pylab.plot(*points.T, 'rd')
pylab.show()

Discrete Convex Hull

2 Answers