더 큰 폴리곤 내에서 구속 조건 내에서 크기를 조정할 수있는 크기를 최대화하는 폴리곤의 회전 및 위치를 찾고 싶습니다.큰 폴리곤에 새겨진 최대 면적 폴리곤 찾기
현재 아이디어는 스케일링 매개 변수를 극대화 할 위치와 회전 매개 변수를 최적화하기위한 scipy optimization routines을 사용하는 것입니다, 그리고 shapely 다각형이 포함 된 제약 조건을 추가 할 수 있습니다. 느리고 우아하지는 않은 것처럼 보입니다.
다른 아이디어?
이 문제는 NP 하드 일 수 있습니다. 주어진 후보 솔루션을 통해 최상의 솔루션이라고 확신 할 수는 없습니다. 증분 무작위 검색을 사용하려고 할 필요가있는 것 같습니다.
내부 다각형이 최대로 확장 된 경우 가장자리에 버텍스가있는 "내부 버텍스 - 외부 에지"또는 "외부 버텍스 - 내부 에지"가 4 쌍 이상 있습니다.
모든 4 개의 버텍스 에지 쌍을 살펴 보겠습니다. 모든 것에 대해 두 개의 참조 점 좌표에 대한 선형 방정식 시스템을 얻습니다. 그것이 하나의 해를 가진다면, 우리는 교차가 없음을 확인하고 OK라면 우리는 내부 다각형의 좌표와 크기를 기억합니다.
이것은 정확한 해결책이지만 느립니다. 반면에 scipy 최적화 루틴은 전역 최대 값이 아닌 로컬 최대 값을 찾는 경향이 있습니다.
이 간단한 다각형입니까? 면 수에 제한이 있습니까? –
예, 단순히 다각형입니다. 그들 중 일부는 100 대 정도의면을 가질 수 있습니다. – daedalus12
나는 비슷한 것을 시도하고 있습니다 - 당신이 scipy에서 어떤 루틴을 사용하고 있는지 말해 줄 수 있습니까? –