2
저는이 겉으로보기에는 간단한 문제로 꽤 오랫동안 고심하고 있습니다. 나는 일련의 점들 (나는 convex hull로 단순화시켰다)을 받았고, 나의 임무는 그들 모두를 포함하고있는 사각형 (반드시 축 정렬은 아님)을 찾고, 여분의 공간이 없다는 것이다. 포인트 주위에 꼭 끼워야 함) 가능한 최대 둘레를가집니다. 최소한의 것을 찾는데 아무 문제가 없었습니다. 그러나 이것은 균열이 더 힘들다고 판명되었습니다. 최소 경계 사각형을 검색 할 때 직사각형의 변의 하나가 항상 선체의 변 중 하나와 정렬된다는 가정을 사용할 수 있었지만 여기서는 그러한 경우가 없습니다. 나는 고통스러운 명백한 것을 놓치고 있습니까? 내가 지금까지 올 수있는 유일한 방법은 직사각형의면에 투영하고 함수를 최대화하기 위해 삼각 함수를 사용할 수 있다면 대칭 쌍의 점을 테스트하는 것입니다.하지만 방금 계산을 잃어 버렸습니다.점 집합에 대한 최대 둘레 경계 사각형
미리 감사드립니다.
사용한 알고리즘에 대한 링크를 게시 할 수 있습니까? 최소 경계 사각형을 45도 회전시키고 점 –
(min (x), max (y)), (max (x), min (y))에 맞게 확장 할 수 있다고 생각합니다. – BLUEPIXY