Оценка соотношения сторон выпуклой оболочки

Question

Каков наилучший способ приблизить соотношение сторон выпуклой оболочки в Python? Я уже пытался сделать это, подгоняя вершины выпуклой оболочки эллипсом и принимая соотношение полу- и большой оси. Результаты не являются удовлетворительными, поэтому я сейчас пытаюсь вывести соотношение сторон непосредственно из выпуклой оболочки. Любые идеи или решения будут высоко ценится.

Приветствия

Answer 1

Обычно вы находите собственные векторы ковариационной матрицы облака точек.Соотношение сторон - это отношение самого большого к наименьшему собственному значению.

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

import matplotlib.pyplot as plt
import numpy as np

# Random data
num = 100
xy = np.random.random((2,num)) + 0.01 * np.arange(num)

eigvals, eigvecs = np.linalg.eig(np.cov(xy))

fig, (ax1, ax2) = plt.subplots(nrows=2)
x,y = xy
center = xy.mean(axis=-1)
for ax in [ax1, ax2]:
    ax.plot(x,y, 'ro')
    ax.axis('equal')

for val, vec in zip(eigvals, eigvecs.T):
    val *= 2
    x,y = np.vstack((center + val * vec, center, center - val * vec)).T
    ax2.plot(x,y, 'b-', lw=3)

plt.show()