Получение границы прямоугольника с помощью выпуклой оболочки (в python)

Question

Получение границы прямоугольника с помощью выпуклой оболочки (в python)

Я пытаюсь получить границу прямоугольника с помощью scipy.ConvexHull(), и это не удается сделать.

u=np.linspace(0, 4, 8)
v=np.linspace(5, 10, 8)
u,v=np.meshgrid(u,v)
u=u.flatten()
v=v.flatten()
points2D=np.vstack([u,v]).T


hull = ConvexHull(points2D)
convex_hull_plot_2d(hull)
boundaryList = hull.vertices
print boundaryList

Дает только четыре угла: [ 0 7 63 56]

Немного возмущая точки, используя опцию qhull_options="QJ Pp" следующим образом:

 hull = ConvexHull(points2D, qhull_options="QJ Pp")

Дает больше точек: [62 56 40 8 0 2 6 7 15 23 47 55 63], но все еще не полный набор границ.

Может ли кто-нибудь сказать мне, как это исправить?

1 2

python scipy convex-hull

1 ответ:

atru · Accepted Answer · 2018-02-03 01:30:33

Математическое Определение состояний выпуклой оболочки

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

Наименьшее выпуклое множество, содержащее прямоугольник, действительно является четырьмя углами, которые вы получаете.
Чтобы получить все точки На границе, вы можете использовать Delaunay триангуляция , а затем вычислить выпуклую оболочку из полученной сетки Делоне,
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay

u=np.linspace(0, 4, 8)
v=np.linspace(5, 10, 8)
u,v=np.meshgrid(u,v)
u=u.flatten()
v=v.flatten()
points2D=np.vstack([u,v]).T

tri = Delaunay(points2D)
plt.triplot(points2D[:,0], points2D[:,1], tri.simplices.copy())

boundary = (points2D[tri.convex_hull]).flatten()
bx = boundary[0:-2:2]
by = boundary[1:-1:2]

plt.plot(points2D[:,0], points2D[:,1], 'o')
plt.plot(bx, by, 'rs')

plt.xlim(-1,5)
plt.ylim(4,11)
plt.show()
Для создания корпуса после формирования триангуляции программа использует tri.convex_hull . Это возвращает вершины граней, образующих выпуклую оболочку для точек триангуляции. В вашем случае, 2D, это линии, и выход получается в виде набора соседних точек, составляющих каждую линию. Заметим, что такой подход считается неэффективным, так как он должен формировать триангуляцию в дополнение к выпуклой оболочке.
Оставшаяся часть программы извлекает значения x и соответствующие им значения y для каждой точки и строит их вместе с триангуляцией, приводящей к