팬더는 ** 도트 ** 쌍에 가입하는 모든 줄을 찾고 반복없이 주어진 ** 줄 **과 교차하지 않을 수 있습니까?

Question

점의 제대로 정의 목록 및 라인의 목록을 감안할 때

:

팬더가 점의 쌍에 가입하고 주어진 라인의 교차하지 않는 모든 라인을 찾을 수 반복하지 않고?

현재 이미지에서 볼 수 있듯이 Im은 솔루션에 도달하지만 프로세스에서 반복해야하며 반복을 통해 모든 것이 고통스럽게 느려집니다. 이미지에서

, 도트 목록 촛대 것 그려진 컬러 도트 및 라인 목록이다. 원하는 결과는 검은 색 선입니다. 질문은 가능하면 이론적 솔루션, 또는 개념 확인을 목적으로 또는 반복보다 다른 방법은 없지만

, 여기에 케이스에 도움, 임 현재 사용하는 코드입니다 : http://pastebin.com/4DiKVy26

Answer 1

팬더를 알지 못합니다.하지만 당신이하려는 일을 볼 수 있습니다. 그렇습니다. 더 빨리 할 수 ​​있습니다. 검은 선을 부르겠습니다 희망에 따라 선명하게 될 것입니다. 귀하의 알고리즘에서 m 도트와 n 라인을 사용하면 모든 m (m-1)/2 광선을 찾은 다음 2n 비교를 수행하여이를 필터링합니다. m * (m-1) * n => 크기의 3 차 입력의. 이 입력을 2 차 방정식으로 만드는 방법이 있습니다.

당신이 raycasting의 형태에 의해 해결 될 수있는 기술을하는지 (이것은 2 차원에 있기 때문에 간단하지만) : 빛과 같은 점을 생각; 원본 도트는 대상이 선의 그림자에 있지 않으면 광선을 대상 도트에만 캐스팅 할 수 있습니다. 그래서 우리는 점으로 시작하고 당신이 밝힐 수있는 선과 점의 목록 위로 오른쪽으로 이동하십시오. 우리가 선을 지나갈 때 그림자의 확장 된 영역이있을 것입니다. 그러나 어떤 x 값이라도 y 값이 그림자에 있는지를 알기 위해서는 그림자 가장자리의 2 그 래디 언트 만 알 필요가 있습니다. 각 줄이 올바르게 진행되면 그림자의 그라디언트를 업데이트하십시오. 우리가 각 점을 통과 할 때 우리는 그것이 그림자 바깥에 있는지 확인합니다. 만약 그렇다면 우리에게는 광선이 있습니다. 각 점에 대해이 과정을 반복하면 작업이 완료됩니다. 이것은 대략 m * (m-1)/2 + m * n 계산으로 잘 수행됩니다.