C++ 2D 테셀레이션 라이브러리?
https://stackoverflow.com/questions/1418831
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
점의 STL 벡터(다소간)로 저장된 일부 볼록 다각형이 있습니다.나는하고 싶다 테셀레이션 매우 빠르게, 바람직하게는 상당히 균일한 크기의 조각으로, "조각" 없이.
나는 그것을 사용하여 일부 물체를 작은 조각으로 분해할 것입니다.다각형을 테셀레이션하는(더 작은 볼록 다각형이나 삼각형의 메시로 분할하는) 멋진 라이브러리를 아는 사람이 있습니까?
이미 온라인에서 찾은 몇 가지를 살펴봤지만 컴파일할 수도 없습니다.이러한 학문적 유형은 사용 편의성을 크게 고려하지 않습니다.
해결책
cgal 이 문제를 해결하기위한 패키지가 있습니다. 최선은 아마도 사용하는 것입니다 2D 다각형 파티셔닝 패키지. 예를 들어, 다각형의 y- 모노톤 파티션 (비 정교회 다각형의 작업)을 생성 할 수 있으며 다음과 같은 것을 얻을 수 있습니다.
달리기 시간은 O (n log n)입니다.
사용 용이성 측면에서 이것은 임의의 다각형을 생성하고 파티셔닝하는 작은 예제 코드입니다. 이 설명서 예):
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2> Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator;
int main( )
{
Polygon_2 polygon;
Polygon_list partition_polys;
CGAL::random_polygon_2(50, std::back_inserter(polygon),
Point_generator(100));
CGAL::y_monotone_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
// at this point partition_polys contains the partition of the input polygons
return 0;
}
CGAL을 설치하려면 Windows에있는 경우 설치 프로그램을 사용하여 사전 컴파일 된 라이브러리를 얻을 수 있으며 모든 플랫폼의 모든 플랫폼에 대한 설치 안내서가 있습니다. 이 페이지. 설치하는 것이 가장 간단하지는 않지만 가장 많이 사용되고 강력한 계산 지오메트리 라이브러리가 있습니다. CGAL 메일 링리스트 질문에 대답하는 데 매우 도움이됩니다 ...
다른 팁
poly2tri 2D Delaunay 삼각 측량을위한 정말 멋진 경량 C ++ 라이브러리처럼 보입니다.
GCAL 전체를 앱에 구축하고 싶지 않다면 구현하기가 더 간단 할 것입니다.
http://www.flipcode.com/archives/efficient_polygon_triangulation.shtml
저는 방금 동일한 문제를 조사하기 시작했으며 보로노이 테셀레이션을 고려하고 있습니다.원래 다각형은 보로노이 셀의 중심이 될 반무작위 점의 산란을 얻게 되며, 균일하게 분포할수록 셀의 크기가 더 규칙적으로 지정되지만 완벽한 그리드에 있어서는 안 됩니다. 그렇지 않으면 내부 다각형이 모두 똑같이 보일 것입니다.따라서 가장 먼저 해야 할 일은 셀 중심점을 생성할 수 있어야 한다는 것입니다. 소스 다각형의 경계 상자 위에 이를 생성하고 내부/외부 테스트를 수행하는 것은 그리 어렵지 않습니다.
보로노이 모서리는 이 그림의 점선이며 들로네 삼각분할의 보완 요소입니다.모든 날카로운 삼각형 점이 무뎌집니다.
Boost에는 몇 가지 보로노이 기능이 있습니다.http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm
다음 단계는 보로노이 다각형을 만드는 것입니다.보로++ http://math.lbl.gov/voro++/ 3D 지향이지만 대략 2D 구조가 작동하지만 2D 보로노이 지향 소프트웨어보다 훨씬 느릴 것이라고 다른 곳에서 제안되었습니다.임의의 학술 홈페이지 고아 프로젝트보다 훨씬 좋아 보이는 다른 패키지는 다음과 같습니다. https://github.com/aewallin/openvoronoi.
OpenCV는 이러한 라인에 따라 작업을 지원하는 데 사용된 것처럼 보이지만 더 이상 사용되지 않습니다(그러나 c-api는 여전히 작동합니까?).cv::distTransform은 여전히 유지되지만 픽셀에서 작동하고 꼭지점 및 가장자리 다각형 데이터 구조가 아닌 픽셀 출력을 생성하지만 귀하의 요구가 아니라면 내 요구에 충분할 수 있습니다.
자세한 내용을 알게 되면 이를 업데이트하겠습니다.
원하는 입력 및 출력에 대해 좀 더 자세히 설명하면 도움이 될 수 있습니다.
예를 들어, 단지 다각형을 삼각형으로 만들려는 경우 삼각형 팬이 작동할 것입니다.다각형을 작은 조각으로 자르려는 경우 일종의 행진 사각형을 구현할 수 있습니다.
좋아, 나는 잘못된 가정을 세웠다. 나는 행진하는 사각형이 행진하는 큐브와 더 비슷할 것이라고 생각했다.알고 보니 꽤 다른 내용이었는데 제가 의도한 바가 전혀 아니네요..:|
어쨌든 귀하의 질문에 직접적으로 대답하기 위해 귀하가 찾고 있는 것을 수행하는 간단한 라이브러리가 있는지 모르겠습니다.CGAL의 유용성에 동의합니다.
제가 생각한 알고리즘은 기본적으로 다각형을 선으로 분할하는 것이었습니다. 여기서 선은 그리드이므로 대부분 쿼드를 얻습니다.다각형-선 교차점이 있는 경우 구현은 간단합니다.이 문제를 제기하는 또 다른 방법은 2D 다각형을 함수처럼 처리하고 점 그리드를 오버레이하는 것입니다.그런 다음 행진 큐브와 비슷한 작업을 수행합니다.4개의 점이 모두 다각형에 있으면 쿼드를 만들고, 3개가 있으면 삼각형을 만들고, 2개가 있으면 직사각형을 만듭니다.아마도 과잉 일 것입니다.약간 불규칙해 보이는 다각형을 원한다면 그리드 점의 위치를 무작위로 지정할 수 있습니다.
반면에 catmull-clark 스타일 세분화를 수행할 수 있지만 스무딩은 생략할 수 있습니다.알고리즘은 기본적으로 중심과 각 모서리의 중간점에 점을 추가하는 것입니다.그런 다음 원래 다각형의 각 모서리에 대해 모서리 이전의 가장자리 중간점, 모서리, 다음 가장자리 중간점 및 중심을 연결하는 더 작은 새 다각형을 만듭니다.이렇게 하면 공간이 타일링되고 입력 다각형과 유사한 각도를 갖게 됩니다.
그래서 옵션이 많고 저는 브레인스토밍 솔루션을 좋아하지만 이것을 무엇에 사용할 계획인지는 아직 모르겠습니다.파괴 가능한 메시를 만들기 위한 것인가요?더 작은 요소가 필요한 일종의 메시 처리를 수행하고 있습니까?Gouraud 셰이딩 아티팩트를 피하려고 하시나요?이것은 전처리 또는 실시간으로 실행되는 것입니까?정확성은 얼마나 중요합니까?더 많은 정보를 얻으면 더 나은 제안이 나올 것입니다.
