Personal tools
You are here: Home CGAL at TAU CGAL at TAU - FAQ
« March 2017 »
Log in

Forgot your password?


Planar Maps and Arrangements of CGAL

Is the outer CCB of a face of a Planar map a SIMPLE polygon?

The outer CCB of a face of a planar map is NOT necessarily a simple polygon. Consider the case where there are "inner antennas"; imagine a face represented by a simple polygon and a vertex v on the outer CCB of the face. Now connect a component that starts and ends at v and lies in the interior of the face (one edge incident at v suffices).

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.


Polygon Boolean Operations: What's complicated and how can I use arrangements to compute them?

The problem with boolean operations of polygons, in the general sense, is that the result might be a collection of things other than polygons. Unions can result with faces with holes and intersections can result with vertices or edges (e.g., two triangles sharing a vertex).

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.


How can I accelerate work with planar maps and arrangements.

The following answer is extracted from the reference pages for 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.

  1. 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).
  2. 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 the time.

    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.

  3. 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.

How can I add information to a vertex, a halfedge or a face?

The basic idea is to change the DCEL so that its vertex, halfedge and face types will contain the information you want.

Both CGAL::Planar_map_2 and CGAL::Arrangement_2 have 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 PlanarMapDcel_2 or ArrangementDcel_2.

The class Planar_map_2 extends the class Topological_map. Take a look at the manual pages for Topological Maps. The section you want to look for is Topological Map with Additional Information under Examples.

You can find this example at <CGAL>/examples/Topological_map/example2.C

Example 10 for planar maps shows the same idea applied to planar maps. Find it at <CGAL>/examples/Planar_map/example10.C

"<CGAL>" here refers to the installation directory of CGAL on your machine.

Document Actions