겹치지 않는 좌표를 생성하십시오.

Question

임의로 라인 요소를 배치하는 프로그램이 있습니다. 그러나, 나는이 선들이 서로 겹쳐 지거나 서로 교차하지 않도록하고 싶다. (선들은 전혀 접촉하지 않는다.)

이 작업을 수행하는 방법에 대한 예제를 찾는 방법은 일반적으로 루프를 사용하여 선 요소 수를 반복하고 좌표를 생성 한 다음 해당 루프 내에서 다른 좌표를 확인하여 좌표가 최소 거리에 있는지 확인합니다.

지금까지 경험 한 바에 따르면 루프를 사용하면 실제로 프로그램에 세금이 부과되고 자극을 표시 할 때 프레임이 떨어지는 경향이 있습니다.

또 다른 생각은 좌표 목록을 생성 한 다음 각 좌표의 거리를 계산하는 것입니다. 내가 가진 코드는 지금까지 다음과 같습니다 :

import numpy as np 
import scipy.spatial.distance 
import random 

length_line=12 
nLines = 1000 #the number of line elements that I want 

#Random coordinates for the lines. 500X500 pixels centred around 0 
xys = np.random.random([nEls,2])*500-250 

#Calculating the distance of the centre of the lines from each other 
dist = scipy.spatial.distance.pdist(xys) 

minDist = (length_line/2)+2 #the minimum distance that should not cause overlap 

print sys 

내가 여기에서 진행하는 방법을 아주 확실하지 않다 - 이상적으로는 설정 후 더 최소 거리가 좌표를 유지하는 프로그램을 싶습니다 minDist이고 아마도 다른 것으로없는 좌표를 대체 할 것입니다.

이것이 가능합니까? 고맙습니다. 나의 이해가 맞으면

Answer 1

, 당신은 세그먼트 부분적으로 서로 중복되지 않는 라인의을 생성하려면? (그러나 그들은 교차 할 수 있습니다, 맞죠?). 다음 제안에서 세그먼트와 선 사이의 이러한 구분은 필수적입니다.

접근 문제를 단순화이다 는 라인 (무한 길이)으로 세그먼트를 확대. 두 줄이 겹치지 않는지 확인하는 것은 간단합니다 (기본적으로 줄은 f (0) 및 그래디언트로 표시되는 1 차 함수입니다).

여기 2 차원 공간에 대한 추론을하지만, 3 차원 공간으로 확장 할 수 있습니다.

두 피하고 근처 당신은 F 오프 라운드 것, 중복 (0) 및 그라디언트 어느 정도의 (예를 들어, 하나 또는 두 자리 숫자 뒤에 소수점). 그것은 거리를 계산하는 것보다 빠릅니다.

마다

에서는 새로운 세그먼트를 생성하는 경우 :

1. 라인으로 확장 세그먼트 (계산 구배 F (0)).
2. 해당 그라디언트가있는 기존 선이 없는지 확인하십시오. 이 테스트는 대부분의 후보자를 제거해야합니다.
   • 빠른 방법은 키가 그라디언트이고 값이 f (0), 시작 및 끝점 인 해시 테이블을 구현하는 것입니다.
3. 후보가있는 경우 f (0)를 확인하십시오. 그러면 나머지 후보들도 대부분 제거됩니다.
4. 마지막으로 두 세그먼트가 겹치지 않는지 비교하십시오. 두 세그먼트가 같은 줄에 있다는 것을 이미 알고 있기 때문에 첫 번째 세그먼트 (y 차원)의 가장 높은 지점이 두 번째 세그먼트의 가장 낮은 지점보다 커서는 안됩니다 혹은 그 반대로도.