Как обнаружить самопересечения в пространственном пути в Python? - PullRequest
Новая
       15

Как обнаружить самопересечения в пространственном пути в Python?

0 голосов
/ 04 мая 2018

Допустим, у меня есть путь в многомерном пространстве, заданный массивом точек вдоль пути. Например. 

p[0] = [  0,  0,  0,   0,...]
p[1] = [  0,  0,  0,0.01,...]

и т.д.

Какой эффективный алгоритм для обнаружения, если путь имеет какие-либо самопересечения? Вполне возможно, что путь пересекается в точке между точками, которые я сохранил.

Например, в 2D: 

p[0] = [  0,   0]
p[1] = [  1,   0]
p[2] = [  1,   1]
p[3] = [0.5,-0.5]

Этот путь не имеет идентичных точек, но имеет самопересечение.

Edit:

В настоящее время я проверяю, попадают ли какие-либо точки в цилиндры, созданные в каждой паре точек.

Вот код, с которым я играл: 

import numpy as np

def pairs(l):
    for i in range(0,len(l),2):
        yield (i,l[i:i+2])

def in_cyl(h0,h1,tol,p):
    # efficient cylinder test from https://www.flipcode.com/archives/Fast_Point-In-Cylinder_Test.shtml
    l = np.linalg.norm(h0-h1)
    dx = h1-h0
    for point in p:
        pdx = point-h0
        dot = np.dot(pdx,dx)
        if dot < 0 or dot > l**2:
            # outside end caps
            continue
        else:
            # point lies within end caps. Find dist from point to cyl axis
            dsq = np.dot(pdx,pdx) - dot**2/l**2
            if (dsq > tol**2):
                # outside cyl
                continue
            else:
                # inside cyl
                return True
    return False

def self_intersect(p,tol):
    for i,(h0,h1) in pairs(p):
        if in_cyl(h0,h1,tol,np.vstack([p[:i],p[i+2:]])):
            return True
    return False

# 50-dimensional test. Intersections should be very rare
dim = 50
test_points = np.random.randn(2500,(50))
print(self_intersect(test_points,0.1))

На моей машине это довольно медленно. 

%timeit self_intersect(np.random.randn(2000,(10)),0.1)
10 s ± 94.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
...