교차하지 않는 두 개의 다각형의 볼록한 선을 계산하는 scipy 방법이 있습니까? 나는 선체가 교차하지 않는 지점 P1과 P2와 볼록 선체 CH (P1)과 CH (P2)의 2 세트를 가지고 있습니다. 나는 P1과 P2에서 점들의 합집합 (union of points)의 볼록 (convex) 선체를 찾고 싶다. scipy에 메소드가 빌드되어 있습니까?scipy에서 두 개의 교차하지 않는 다각형의 볼록한 선분 계산
Scipy의 convex hull 구현에 대한 문서는 here입니다. 두 개의 점 배열을 결합하여 합집합을 얻으십시오. 이 집합을 convex hull 알고리즘에 공급합니다.
각 다각형의 모든 점은 다각형의 볼록한 선체 안에 있습니다. 차례로 두 다각형의 볼록 선체는 전체적으로 큰 볼록 선체 안에 포함됩니다. 따라서 각 폴리곤의 모든 점은 더 큰 볼록 선체 안에 있습니다. 즉, 폴리곤 점의 완전한 결합에도 유효합니다.
그러나 하나의 점의 합집합을 메서드에 전달하면 복잡도는 nlogn이지만 유니온의 convex hull은 선형 시간으로 결정될 수 있습니다. –
문제를 해결하기 위해 [선형 알고리즘] (http://cs.smith.edu/~orourke/books/compgeom.html)이 존재하는 것이 맞습니다. 그러나 이것은 SciPy에서 구현되지 않은 매우 구체적인 최적화입니다. 문제를 선형 적으로 해결해야합니까? 방대한 양의 점들이 없으면 훨씬 더 빠르지 않을 것입니다. – Arthelais
내 과제 중 하나에 필요합니다. 이것은 과제의 주요 부분이 아닙니다. 나는 그걸로 살 수 있다고 생각해. 단지 알고리즘 nlogn을 만들지 않습니다. –
특정 프로그래밍 라이브러리 또는 언어에 대한 코딩 질문 및 질문은 CS.SE에서 주제와 관련이 없지만 스택 오버플로에 대해 질문 할 수 있습니다. 우리의 [help/on-topic]을보십시오. CS.SE는 개념, 알고리즘 및 과학에 대한 질문입니다. –