CGAL at TAU - FAQ
Planar Maps and Arrangements of CGAL
- Is the outer CCB of a face of a Planar map a SIMPLE polygon?
- Polygon Boolean Operations: What's complicated and how can I use arrangements to compute them?
- How can I accelerate work with planar maps and arrangements?
- How can I add information to a vertex, a halfedge or a face?
Mind that you might get a non simple polygon even if the outer CCB represents one due to numerical errors, if you are using an inexact number type.
For proper intersections, that is intersections of the interiors of polygons, one can use our polygon intersection demo program on CGAL's demo page.
Take a look at the source files. The "engine" can be easily changed to perform union as well. The implementation uses CGAL arrangements, but the interface was built so that you only need to know of CGAL::Polygon_2 in order to use it.
Work is in progress for a package of Map Overlays. A derivative of this package will be Boolean Operations of planar maps and this will cover all possible cases.
Planar Maps in CGAL.
Before the specific tips, it should be reminded that compiling programs with debug flags turned off and with optimization flags significantly reduces running time.
- The default point location strategy (i.e. using trapezoidal decomposition) is the fastest one when queries are concerned. However, since it has to build a search structure it might slow down the incremental building process of the map. If it is known in advance that there will not be many point location or vertical ray shoot queries use another point location strategy (such as the walk or simple strategies) which does not slow down the building process (no search structure is being built).
Prior knowledge of the combinatorial structure of the map can
be used to accelerate insertion time. The specialized insertion
functions, i.e insert_in_face_interior,
insert_from_vertex or insert_at_vertices should be used
according to this information. The insert function performs point
location queries and then calls one of the other update functions
and therefore takes more time. The function
insert_in_face_interior even takes constant time. The other
two are linear in the worst case, but should be much faster most of
Insertion of a polygon, which is represented by a list of segments along its boundary, into an empty planar map should be done in the following way. First, some segment should be inserted using insert_in_face_interior with the unbounded face. Then a segment with a common end point can be inserted using insert_from_vertex and so on with the rest of the segments but last. The last segment can be inserted using insert_at_vertices since both it endpoints are represented as vertices of the map and are known in advanced.
- If the user has LEDA installed it is recommended to use the specialized traits classes Pm_leda_segment_exact_traits or Arr_leda_polyline_traits. These traits classes are much faster since they are specialized for LEDA's rational geometric kernel. Note that these traits classes are models of PlanarMapTraits_2 since they model its refinement, the ArrangementTraits_2 concept.
a DCEL template parameter.
You just have to supply your version of the DCEL. Your DCEL should be a
model of the appropriate concept, be it
Planar_map_2 extends the class
Take a look at the
pages for Topological Maps. The section you want to
look for is Topological Map with Additional Information under
You can find this example at
Example 10 for planar maps shows the same idea applied to planar
maps. Find it at
"<CGAL>" here refers to the installation directory of CGAL on your machine.