Дискретный выпуклый корпус

Question

В python, учитывая m случайных точек в сетке nxn, как рассчитать (приблизительно) выпуклый корпус, в котором корпус может быть создан только с использованием точек на дискретной сетке, а не непрерывной точки?

модули, такие как scipy.spatial, дают только непрерывные выпуклые оболочки, где линии, соединяющие вершины, являются чисто алгебраическими, но я хочу приблизительно выпуклый корпус, где граница дискретна.

Answer 1

Вычислить обычную выпуклую оболочку и объединить вершины корпуса с цифровыми отрезками (например, алгоритм DDA).

http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull

https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)

Answer 2

Вы все еще можете использовать qhull + некоторую постобработку:

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