Project: Polygon Triangulation
LINK:http://www.mpi-inf.mpg.de/~kettner/courses/lib_design_03/proj/polygon_triang.htmlDesign the interface between data structures that represent simple polygons and generic algorithms that triangulate simple polygons.
The Standard Template Library (STL) [Austern98, SGI-STL] contains several examples of a similar interface design: Iterators are the interface between sequences of items in container classes and generic algorithms on sequences. However, they (usually) do not modify the container. Among the container classes some modifying functions, e.g.,
insert
or remove
, describe a standardized interface for modifying the container classes and can be used for generic algorithms on container classes. This project is expected to design a generic interface in the same spirit for triangulating polygons. We start with a set of data structures that can represent a simple polygon, and with a set of algorithms that can triangulate it. We suggest to use the Computational Geometry Algorithms Library (CGAL)
std::list
of 2D points. CGAL::Polygon_2
. CGAL::Polyhedron_3
. CGAL::Triangulation_2
one can end up in the situation to triangulate a polygonal hole in the triangulation structure. All these representations would be for simple polygons without holes. An optional extension would be to extend this project to polygons with holes as they can be represented with:
std::list
of std::list
's of 2D points, where the first list is the outer boundary of the polygon and all succeeding lists are the inner boundaries of holes in the polygon, one list per hole. CGAL::Planar_map_2
can contain faces with holes. CGAL::Nef_polyhedron_2
can contain faces with holes. Examples of algorithms that triangulate polygons are:
Clearly iterators can be used in examining the input polygon. The new part will be the modifying part of the algorithms; where do we create and store the result triangles:
The goal of the project is to design the interface and to realize some of the data structures and algorithms, possibly based on the already existing CGAL implementations. The task includes:
Prerequisites
This project requires interest in geometry or graphics and some knowledge of geometric algorithms. Since CGAL will be covered later in the course, it might be necessary to learn about CGAL prior to that.
References
[Austern98]
Mathew H. Austern.
Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.
[SGI-STL]
Silicon Graphics Computer Systems, Inc.
Standard Template Library Programmer's Guide.
http://www.sgi.com/tech/stl/.
[Fabri99]
Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr.
On the Design of CGAL, the Computational Geometry Algorithms Library. Software -- Practice and Experience, submitted 1999, to appear. (also available as technical report)
[deBerg00]
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.
Computational Geometry: Algorithms and Applications. Springer, 2nd edition, 2000.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.