포인트가 점 집합에 의해 생성 된 볼록 선체에 있는지 확인

포인트 집합에서 볼록 선체를 계산해야합니다. 포인트포인트가 점 집합에 의해 생성 된 볼록 선체에 있는지 확인

치수 세트의 10 ~ 30D

크기는 보통 2 ~ 10

작은 내가해야하는 작업이 포인트가로 구성 볼록 선체 내부에 있는지 여부를 판단하는 것입니다 일반적으로 포인트 세트.

가 수행하는 몇 가지 알고리즘 무엇입니까, 아니면 내가 사용할 수있는 기존의 라이브러리가

2016-08-15 Alaya

점이 내부에 있는지 확인하기 위해 볼록 선체를 만들 필요가 없습니다. 범위의 모든 계수를 사용하여 점 집합의 선형 결합을 취함으로써 그 점을 생성 할 수 있는지 알아보기 위해 선형 프로그래밍 문제를 해결하십시오. – mcdowella

2 차원에서 convex hull은 다음과 같이 나타낼 수 있습니다. 다각형과 일부 [알고리즘] (https://en.wikipedia.org/wiki/Quickhull)이 알려져 있기 때문에 더 높은 차원의 적절한 데이터 구조에서 어떻게 볼록 선체를 표현할 지 불분명합니다. 원하는 표현을 분명히하십시오. – Codor

mcdowella가 옳다. 귀하의 경우 전체 convex hull을 피하기를 원한다. (시간 복잡도는 D와 지수 함수 적으로 증가한다.) 다른 이유로 볼록 선체를 제작해야하는 경우 [CGAL] (http://doc.cgal.org/latest/Convex_hull_d/index.html)을 사용할 수 있습니다. – geoalgo

참고 : 알고리즘의 원시 스케치가 필요 revision.It 출력 잘못된 결과 (아래 설명 참조) 할 수 있습니다

다음은 가능한 여러 가지 해결책 중 하나입니다.

당신의 공간의 D - 차원, 당신의 점의 N - 수를합시다. 다음 알고리즘을 사용할 수 있습니다 :

공간의 각 좌표 평면에 대한 투영 볼록 선체를 계산해야합니다. 당신은 D 볼록 선체를 얻을 것입니다. 이 단계의 복잡도는 D * N * log N

입니다. 그런 다음 각 투영 점이 각각의 적절한 볼록 선체 안에 있는지 테스트해야합니다. 이 단계의 복잡도는 (고유의 알고리즘을 사용하여) 위해 D * N이다

전체 실행 복잡성 = D * N * 로그인 참고

N.이 알고리즘의 기본적인 아이디어가이 다음과 평면 볼록 선체 컴퓨팅 졸이다 포인트의 위치 테스트.

P. 물론, 볼록한 선체가 선분 또는 정점 일 수있는 퇴화 된 사례를 얻을 수 있습니다. 그러나 이러한 경우는 용이하게 취급 될 수있다.

P.P.S. 이 알고리즘은 점이 convex hull 또는 경계에 있는지 만 확인할 수 있습니다.

출처

2016-08-17 14:50:27 LmTinyToon

제목이 볼록 선체 계산에 대해 묻는 것은 사실이지만 오도 된 것입니다. 질문은 포함/제외 만 필요한 것임을 분명히합니다. 이는 볼록 선체 자체를 계산하지 않고도 수행 할 수 있습니다. –

나는 당신에 동의합니다. 그러나 문제를 해결하는 그의 방법에 달려 있습니다. 물론, 저자는 위의 예제처럼 선형 프로그래밍을 사용하여이 작업을 해결하기 위해 볼록한 선체를 계산할 수 없습니다. 하지만 내 알고리즘을 쉽게 구현할 수 있다고 생각합니다. 참고 : 다차원 컨벡션 헐 (hull) 계산은 포함하지 않습니다. 보조 투영을 사용하여 점의 위치를 테스트합니다. – LmTinyToon

제발 나를 잘못하지 마세요. 나는 당신의 훌륭한 대답을 비판하지 않았습니다. 당신이 대답을 적었을 때의 제목이 오도 된 것이기 때문에 나는 (아마도 미래의 독자들에게) 의견을 덧붙이려고 생각했다. 자, upvote를 가져라. –

포인트가 점 집합에 의해 생성 된 볼록 선체에 있는지 확인

답변

관련 문제