고차원 볼록 선체 표현 (3+)

Question

2d에서 볼록 선체는 기본적으로 점 둘러보기로 표현됩니다. 이 표현이 2 차원 이상으로 떨어질 수 있습니다. 나는 곧 그들과 함께 일할 것이므로, "표준"이 무엇인지에 대해 미리 알고 싶습니다. 그렇게한다면, 선체가 다른 사람들에 의해 사용될 수 있습니다.

명확화 : 내가 언급 한 표준은 출력 형식 측면에서 프로그램에서 다른 것들에 대해 선체를 사용할 수 있도록했습니다.

Answer 1

점의 집합은 항상 선체를 완전히 지정하기에 충분하지만 점의 연결을 설정하면 실제로는 선체 알고리즘을 다시 실행해야하는 경우가 종종 있습니다.

EDIT : 가장자리 또는 얼굴 데이터가 필요한 경우 퀵hull과 같은 알고리즘 중에 이것을 무료로 얻을 수 있습니다. 나는 N 차원을 가정 할 것이다. 기본적으로 N 포인트로 정의 된 평면을 관련 법선 벡터와 함께 지속적으로 찾습니다. 법선 벡터에 의해 주어진 평면 옆에 여전히 점이 있다면, 가장 멀리 떨어진 점으로 정의 된 새로운 평면을 만들고 새로운 평면 집합의 잘못된면에서 임의의 점을 제거합니다. 이 평면은 (N-1) - 셀을 정의합니다 (3D에서 이들은면으로 2D에서 이들은 모서리입니다). 알고리즘의이 지점에서 선체의 가장 높은 차원 표현을 제공합니다. 알고리즘은 잘못된면에 점이있는 평면이 없을 때까지 계속됩니다. 최종 평면은 최종 선체의 (N-1) 셀을 정의하며, 정의 점은 정점입니다. N 포인트 이상으로 정의 될 수있는 비행기에 관한 문제가 있지만 그 중 하나를 처리 할 수있는 여러 가지 방법이 있습니다. http://www.qhull.org/은 많은 전략을 사용합니다. 가장 확실한 것은 Delaunay 삼각 측량을 사용하는 것입니다. 컨벡스 헐 알고리즘을 가지고 있다면 코드를 얻을 수 있습니다.)

2 차원에서 포인트 목록과 일부 가장자리가 있습니다. 원하면 투어를 주문할 수 있습니다. 모든 선체에 가장자리와 점이 모두 필요합니다.

3D에서는 점과 가장자리,면과 모서리 또는 점과면이 최소한으로 표현되어야합니다. 그러나 때때로이 세 가지를 모두 갖는 것이 효율적일 수 있습니다. 어쩌면 당신은 어쩌면 점, 어쩌면 둘 다가 만들어지는 가장자리의 측면에서 얼굴을 표현하기를 원할 것입니다. 그것은 기억과 시간 또는 접근성 사이의 절충안입니다.

당신은 더 높은 차원에서 똑같은 것을 가지고 있지만 셀 (3D +면)뿐만 아니라면, 모서리 및 점을 가지고 있습니다. 높은 차원을 사용하면 셀 데이터를 저장하는 데 필요한 공간이 상당히 커질 수 있으므로 점과 모서리를 모으는 것이 바람직 할 수 있습니다.이 패턴의 증거는 여기 http://en.wikipedia.org/wiki/Hypercube#Elements에서 볼 수 있습니다.

그런 다음 더 높은 차원의 셀이 표시되는 방법, 점, 가장자리,면, 낮은 차원의 셀, 높은 차원의 셀을 참조 할 수있는 방법을 선택할 수 있습니다. 문제는 서로 다른 차원의 셀 (얼굴과 가장자리 사이의 관계와 같이 더 높은 차원) 간의 모든 관계를 추적하는 것입니다. 또는 이러한 관계 유형의 수는 초 선형 적으로 증가 할 것이고, 표현 될 각 유형의 수 관계와 마찬가지로 추가 조합 자이다. 그래서 그것을 멀리 던져서 즉시 계산하십시오. 중간 크기의 문제에 대한 공간 및 시간 요구 사항이 중요해질 수 있습니다. 따라서 표현의 선택은 실제로하는 일에 달려 있습니다.

개인적으로 나는 보통 그들을 참조하는 가장자리가있는 점들의 모음을 사용합니다.

ND 형상 : 도움이 말한 내용 http://en.wikipedia.org/wiki/Polytope