Как равномерно заполнить объем выпуклой оболочки, заданной списком трехмерных точек?

У меня есть выпуклый корпус, заданный списком трехмерных точек, сгенерированных scipy.spatial.ConvexHull.

Я хочу, чтобы весь этот объем был равномерно заполнен трехмерными точками каким-то эффективным образом.

Если бы у меня был быстрый способ узнать, находится ли точка внутри или вне выпуклой оболочки, я мог бы векторизовать, просматривая каждый воксель в некотором разрешении и возвращая его центр, если он «внутри», или ничего не возвращая для этого вокселя, если он « вне".

Пример:

для 2d точек, как в примере ConvexHull от scipy,

пример scipy

Я хотел бы вычислить список точек, равномерно расположенных внутри красной линии.

Как это можно сделать достаточно эффективно?


python numpy scipy convex-hull
person Gulzar    schedule 23.11.2019    source источник
comment
У вас есть доступ к самому объекту ConvexHull или только к вершинам?   -  person Paul Panzer    schedule 23.11.2019
comment
@Paul Panzer, у меня есть доступ.   -  person Gulzar    schedule 23.11.2019
comment
Затем вы можете использовать атрибут .equations, который содержит нормали поверхности для проверки входа/выхода. мне кажется, что вы должны указать точки, которые хотите проверить, в однородных координатах или, говоря простым языком, добавить 1 к координатам каждой точки. Затем перемножьте матрицу и проверьте столбцы результата. Все положительные столбцы указывают на внутреннюю точку. Одной отрицательной координаты достаточно, чтобы вывести вас наружу, неотрицательный, но не строго положительный столбец означает, что вы находитесь где-то на поверхности.   -  person Paul Panzer    schedule 23.11.2019
comment
Или, может быть, наоборот, т.е. отрицательное там, где я сказал положительное, и наоборот.   -  person Paul Panzer    schedule 23.11.2019
comment
@PaulPanzer Не могли бы вы показать код? Я не совсем понимаю, что вы имеете в виду   -  person Gulzar    schedule 24.11.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

введите здесь описание изображения

import numpy as np
from scipy import spatial

## set up example ##
# create sample points
np.random.seed(17)
samples = np.random.uniform(-5,5,(100,2))
# pick convex subset
outline = samples[(samples**2).sum(1)<4]
outline = spatial.ConvexHull(outline)
# choose tolerance for detection of boundary points
eps = 1e-9

## classify ##
outside = ([email protected]_[samples, np.ones(len(samples))].T > eps).any(0)
inside = ([email protected]_[samples, np.ones(len(samples))].T < -eps).all(0)
boundary = ~(outside|inside)

## plot ##
import pylab
closed = np.tile(outline.points[outline.vertices],(2,1))
closed = closed[:len(closed)//2+1]
pylab.plot(*closed.T,'b')
pylab.plot(*samples[outside].T,'og')
pylab.plot(*samples[inside].T,'or')
pylab.plot(*samples[boundary].T,'oy')
pylab.show()
person Paul Panzer    schedule 24.11.2019
comment
Спасибо вам за это! К сожалению, мы все еще используем python 2.7... есть ли быстрая замена @? - person Gulzar; 24.11.2019
comment
@Gulzar есть matmul и dot. - person Paul Panzer; 24.11.2019
comment
не могли бы вы объяснить использование .c_ здесь? Я нашел эту часть неясной, хотя в итоге она сработала для меня. - person Gulzar; 25.11.2019
comment
@Gulzar c_ — укладчик столбцов; здесь он добавляет столбец единиц в конце samples - person Paul Panzer; 27.11.2019
comment
оно работает! Однако... Я заметил, что он проверяет каждую точку, каждое уравнение. Интересно, есть ли более быстрый способ. Один из них, о котором я могу думать, — это пройти измерение (скажем, x) и найти первую и последнюю точки в корпусе. остальные находятся внутри без необходимости проверки. поиск можно сделать o(nlogn). Есть ли еще более быстрый способ, может быть, какой-нибудь умный симплексный метод? - person Gulzar; 27.11.2019
comment
@ Гульзар, я не знаю. Возможно, вы могли бы начать с грубой сетки и рекурсивно разрезать каждый куб, который не полностью входит или не полностью выходит, на 8 равных подкубов. - person Paul Panzer; 27.11.2019