나는 C++에서 외판원 문제를 해결하기 위해 노력하고 비 볼록 다각형

Question

에 대한 대표적인 평균 인테리어 포인트 찾기,하지만 난 poylgons 세트 대신 점 세트 사이의 최단 거리를 통과해야합니다. 그렇게하기 위해, 나는 대표적인 "중간"내부 점으로 각 다각형을 표현하려고 노력하고 있는데, 그래서이 평균 내부 점에서 TSP를 할 수 있습니다.

단순히 산술 평균점이기 때문에 볼록한 다각형에서 내부 내부 점을 쉽게 찾을 수 있지만 (볼록 다각형의 경우 항상 내부에 놓이기 때문에)이 방법은 오목한 다각형에서는 작동하지 않으므로 그것은 다각형의 내부 일 필요는 없습니다.

도움말? 감사합니다. . :-)

Answer 1

:

1. 삼각 폴리곤 (주문 N 로그 (N))로 큰 지역과
2. 픽업 삼각형 (말) (순서 N)는
3. 그 삼각형의 무게 중심에 당신의 점을 지정 . 나는이보다 나에게 더 의미는 "대표"지점에 대한 또 다른 정의는 없다고 생각 다각형 외부 (CONST) (잠재적으로)

전체가 아닌 볼록 다각형의 진정한 무게 중심이기 때문에 .

Answer 2

하나의 아이디어는 각각의 다각형의 컨벡스 헐 (convex hull)을 구성하고, 볼록 선체의 중심을 사용하는 것이다. 고무 밴드로 폴리곤을 감싸는 것과 같은 아이디어를 이해하려면 관심 지점을 찾는 데 사용할 수있는 봉투를 제공하십시오. CGAL을 사용하여 계산할 수 있어야한다고 생각합니다. 그러나 모든 다각형에 대해 이렇게하면 슈퍼 패스트가 될 수 없습니다. 삼각 측량을 만들면 원래의 다각형의 가장 가까운 내부 점을 볼록한 선체의 중심점으로 추가 단계로 효율적으로 찾을 수 있습니다.

btw 볼록한 다각형의 점 중심을 찾는 올바른 방법은 Chebyshev 중심을 찾는 것입니다. 이것은 CGAL을 사용하여 선형 시스템을 해결하는 것에 해당합니다. 볼록 다각형의 Chebyshev 중심을 찾는 선형 프로그래밍 문제는 Boyd book에 잘 정의되어 있습니다.

에 대해 어떻게