점의 STL 벡터로 저장된 볼록 다각형이 있습니다 (다소 차이가 있음). 나는 tessellate을 정말로 빨리, 바람직하게는 꽤 균등하게 크기가있는 조각으로, 그리고 "슬리버"없이 만들고 싶습니다.C++ 2D 테셀레이션 라이브러리?
저는 이것을 사용하여 일부 오브젝트를 작은 조각으로 분해합니다. 누구든지 폴리곤을 테셀레이션 할 수있는 멋진 라이브러리를 알고 있습니까 (작은 폴리곤 또는 삼각형의 메쉬로 분할).
나는 온라인에서 이미 발견 한 몇 가지를 살펴 봤지만 컴파일 할 수조차 없다. 이러한 학업 유형은 사용의 편의를별로 고려하지 않습니다.
CGAL에는이 문제를 해결하는 패키지가 있습니다. 아마도 가장 좋은 방법은 2D Polygon Partitioning 패키지를 사용하는 것입니다. 예를 들어 당신이 (뿐만 아니라, 비 볼록 다각형 작동) 다각형의 Y-모노톤 파티션을 생성 할 수 있으며,이 같은 것을 얻을 것이다 :
y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif
실행 해 시간이 O (N 로그입니다 엔).
이 작은 예제 코드 임의의 다각형을 생성하고 그것을 분할 인 사용 편의성 측면에서은 (this manual example 기준) :
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를 설치하려면 미리 컴파일 된 라이브러리를 얻으려면 this page에 모든 플랫폼에 대한 설치 안내서가 있습니다. 설치가 가장 간단한 것은 아니지만 가장 많이 사용되는 강력한 계산 기하 라이브러리를 얻을 수 있으며 cgal mailing list은 질문에 대한 답변에 매우 유용합니다 ...
나는 실제로 전에 cgal을 시도하고 있었다 .... 그것은 지옥처럼 추악하다. 그 typedef를보세요! 아마 나는 그것을 또 한번 시도 할 것이다. 파티셔닝 저는 이미 생각했습니다. 테셀레이션은 용어가 섞여 있지 않는 한 조금 다릅니다. 나는 볼록한 크기의 polies가 아닌 정밀한 mesh를 원합니다; 그 중 2 개는 실제로 매우 끔찍해 보입니다. 슬라이 버가 너무 많습니다. – mpen
"당신은 메시의 품질에 대해 걱정하지 않습니다"라고 썼다. 그래서 나는이 파티셔닝이 당신이 찾고있는 것이라고 생각했다. 삼각형의 품질과 크기를 제어 할 수 있도록 다각형을 삼각형으로 만들고 싶습니까? 이것이 당신의 질문 인 경우에 당신은이 cgal 패키지를 들여다 볼 수 있습니다 : http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Mesh_2/Chapter_main.html –
Err ... 미안 해요, 품질에 의해, 나는 모든 각도가 적어도 어느 정도는 존재하거나 모든 구획에 걸쳐 완전히 일정한 크기를 갖는 것에 대해 까다롭지는 않습니다. 그러나 그것은 일종의 메쉬를 만들어야합니다. 나는 그것을 분명히해야했다. 마지막 링크는 내가 원하는 것보다 훨씬 좋아 보입니다. 감사! – mpen
원하는 입력 및 출력에 대해 좀 더 자세히 설명합니다. 도움이 될 수 있습니다.
예를 들어, 삼각형으로 다각형을 가져 오려고하는 경우 삼각형 팬이 작동 할 수 있습니다. 다각형을 작은 조각으로 자르려고한다면 어떤 종류의 행진 사각형을 구현할 수 있습니다.
좋아, 나는 나쁜 가정을했다. 나는 행진하는 사각형이 행진하는 큐브에 더 가깝다고 생각했다. 그것이 완전히 다른 것이었고, 나는 전혀 의미하지 않았습니다. : |
질문에 직접 대답하기 위해, 나는 당신이 찾고있는 것을하는 간단한 라이브러리를 모른다. 나는 CGAL의 유용성에 동의한다.
내가 생각했던 알고리즘은 기본적으로 선이 그리드 인 선으로 다각형을 분할하는 것이므로 대부분 사각형을 얻습니다. 다각형 선 교차점이 있다면 구현이 간단합니다. 이 문제를 제기하는 또 다른 방법은 2 차원 다각형을 함수처럼 취급하고 점의 격자를 겹쳐서 표시하는 것입니다. 그런 다음 큐브를 행진하는 것과 비슷한 작업을 수행하십시오. 모든 4 점이 다각형에 있으면 쿼드를, 3은 삼각형을 만들고 2는 사각형을 만듭니다. 아마도 과장 될 수 있습니다. 약간 불규칙한 모양의 폴리곤을 원한다면 격자 점의 위치를 임의로 지정할 수 있습니다.
반면에 catmull-clark 스타일 하위 분할을 수행 할 수는 있지만 스무딩을 생략하십시오. 알고리즘은 기본적으로 중심점과 각 모서리의 중간 점에 점을 추가합니다. 그런 다음 원래 다각형의 각 모서리에 대해 모서리, 모서리, 다음 모서리 중간 점 및 중심점 이전에 모서리 중간 점을 연결하는 새로운 작은 다각형을 만듭니다.이렇게하면 공간이 바뀌고 입력 된 다각형과 비슷한 각도를 갖게됩니다.
많은 옵션이 있으며 브레인 스토밍 솔루션이 마음에 들지만 아직까지 어떤 용도로 사용할 것인지 잘 모릅니다. 파괴적인 메쉬를 만드는 것입니까? 더 작은 요소가 필요한 메쉬 처리를하고 있습니까? Gouraud 음영 유물을 피하려고? 사전 프로세스 또는 실시간으로 실행되는이 프로그램입니까? 정확성은 얼마나 중요합니까? 더 많은 정보를 얻으면 더 좋은 제안을 얻을 수 있습니다.
글쎄, 내가 말했듯이, 나는 작은 조각으로 모양을 폭발시키고있다. 나는 비트가 완전히 균등하게 크기가 중요하지 않다고 생각하지만, 비트는 길쭉한 삼각형이 아니라 여전히 비트가되어야합니다. 행진하는 사각형이 어떻게 관련이 있는지 보지 못합니다. 비트 맵을 폴리곤으로 바꾸는 것이 본질적으로 중요하지 않습니까? – mpen
파괴 가능 메쉬, 예. 나는 그것을 언급했다. 실시간으로 완료 될 것입니다. 그러나 모든 프레임이 아닐지도 모릅니다 :) 그것은 게임을위한 것입니다 ... 두 개의 오브젝트가 충돌 할 때, 나는 그들을 폭발시키고 싶습니다. 고맙습니다. 감사합니다. – mpen
앱에 GCAL 전체를 빌드하지 않으려면 구현하기가 더 쉽습니다. 위의 댓글에서 언급 balint.miklos으로
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
는 Shewchuk의 triangle 패키지는 매우 좋다. 나는 그것을 여러 번 사용했다. 그것은 프로젝트에 멋지게 통합되며 triangle++ C++ 인터페이스가 있습니다. 슬리버를 피하려면 삼각형에 (내부) 슈타이너 점을 추가하여 고품질 메쉬 (일반적으로 제약 된 적합 델라 네이 삼각 측량)를 생성하도록 허용하십시오.
볼록한 다각형이 있고 품질에 너무 신경 쓰지 않는다면 이것은 매우 간단합니다. 바로 ear clipping입니다. 걱정하지 마세요. 볼록 다각형의 경우 O (n^2)가 아닙니다. 이 작업을 순진하게 수행하는 경우 (즉, 귀를 찾으면 귀를 자른다) 삼각형 팬을 얻게되며, 이는 슬라이 버를 피하려는 경우 약간의 드래그입니다. 삼각 측량을 향상시킬 수있는 두 사소한 휴리스틱
귀 클리핑을 기반으로 한보다 견고한 삼각 측량기를 원하시면 FIST을 확인하십시오.
귀에 잘리는 것을 알고 있지만, 지적한대로 좋은 결과를 내지 못합니다. 하지만 고마워요 :) – mpen
나는이 동일한 문제를 조사하기 시작했으며 보로 노이 테셀레이션을 고려 중입니다. 원래의 다각형은 보로 노이 셀의 중심이 될 세미 무작위 포인트의 산란을 가져 오며,보다 균등하게 분포 된 셀은 더 규칙적인 크기의 셀이지만 완벽한 그리드에 있으면 안됩니다. 그렇지 않으면 내부 다각형 모두 똑같이 보일 것이다. 따라서 가장 먼저해야 할 일은 셀 중심점을 생성 할 수 있도록하는 것입니다. 소스 중심점의 경계 상자에 셀 중심점을 생성하고 내부/외부 테스트를 너무 힘들어서는 안됩니다.
보로 나이 가장자리는이 그림의 점선이며, 델루 네이 삼각 측량의 보완 물입니다. 모든 날카로운 삼각형 포인트 둔화 될 : http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm
다음 단계는 보로 노이 다각형을 만드는 :
부스트는 일부 보로 노이 기능이 있습니다. Voro ++ http://math.lbl.gov/voro++/은 3D 지향이지만 대략 2D 구조가 작동하지만 2D 보로 노이를 지향하는 소프트웨어보다 훨씬 느릴 것을 제안합니다. 무작위 학문 홈페이지 고아 프로젝트보다 훨씬 좋은 것으로 보이는 다른 패키지는 https://github.com/aewallin/openvoronoi입니다.
OpenCV가 이러한 라인을 따라 뭔가를 수행하는 데 사용 된 것처럼 보이지만 더 이상 사용되지 않습니다 (그러나 c-api는 여전히 작동합니까?).cv :: distTransform은 여전히 유지되지만 픽셀에서 작동하고 정점 및 가장자리 다각형 데이터 구조가 아닌 픽셀 출력을 생성하지만 사용자가 아닌 경우 내 필요에 충분할 수 있습니다.
더 자세히 알게되면이 내용을 업데이트하겠습니다.
이 3D 또는 2D입니까? – GManNickG
@Gman : 2D ----- – mpen