Выпуклая оболочка над периодическими c граничными условиями - PullRequest
Новая
       94

Выпуклая оболочка над периодическими c граничными условиями

0 голосов
/ 30 апреля 2020

Я пытаюсь вычислить выпуклую оболочку, но мой набор точек увеличен из-за периодических c граничных условий. Я не могу найти другие работы или ссылки, которые занимались этой проблемой. Основная проблема заключается в том, что простое вычисление выпуклой оболочки не правильно отображает фактическую площадь, занимаемую набором точек, как показано ниже на рисунке.

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

(left) the original point set, (right) the point set repeated to reflect the periodic boundary conditions

Есть ли элегантный способ вычисления выпуклой оболочки над такими граничными условиями? Более конкретно, меня интересует любое множество точек, которое попадает в такую ​​выпуклую оболочку (то есть точки внутри нарисованных выпуклых оболочек справа). Любая помощь будет принята с благодарностью.

Код для создания графиков: 

# Initialize
import numpy as np 
import matplotlib.pyplot as plt
fig, ax = plt.subplots(1,2, figsize=(8,4))
xax = ax[0]
yax = ax[1]

# Sample multivariate Gaussians (2D) to represent a clustered data set
N = 500 
sigma = np.diag(0.005*np.ones(2))
mu = np.array([[0.6, 0.6], [0.1,0.1], [0.95,0.05]])

# Sample with periodic boundary conditions on [0,1]^2
x = np.concatenate((
    np.random.multivariate_normal(mu[0,:], sigma, N) % 1,
    np.random.multivariate_normal(mu[1,:], sigma, N) % 1,
    np.random.multivariate_normal(mu[2,:], sigma, N) % 1
))

# Visualize the periodic boundary conditions by repeating the point set for each quadrant
quadrants = np.array([[i,j] for i in [-1,0,1] for j in [-1,0,1]])
y = x.copy()
for delta in quadrants:
    tempx = x + delta 
    y = np.concatenate((y, tempx)) if (np.sum(delta**2) != 0) else y 
    # Plot in distinct colors
    yax.plot(tempx[:,0], tempx[:,1], linestyle='none', marker='o', markersize=2)

# Plot the original point set
xax.plot(x[:,0], x[:,1], linestyle='none', marker='o', markersize=2)
plt.show()
...