# Chapter 20
2D Planar Maps

Ester Ezra, Eyal Flato, Efi Fogel, Dan Halperin, Iddo Hanniel, Sariel Har-Peled, Shai Hirsch, Oren Nechushtan, and Ron Wein

### Introduction

Planar maps are embeddings of topological maps into the plane. A planar map subdivides the plane into vertices, edges, and faces. The vertices, edges, and faces of a subdivision are the embeddings of their topological map counterparts into the plane, such that (1) each vertex is embedded as a planar point, (2) each edge is embedded as a bounded x-monotone curve, and does not contain vertices in its interior, and (3) each face is a maximal connected region of the plane that does not contain edges and vertices in its interior.

- Planar_map_2<Dcel,Traits>

- PlanarMapPointLocation_2

- Pm_trapezoid_ric_point_location<Planar_map>

- Pm_naive_point_location<Planar_map>

- Pm_walk_along_a_line_point_location<Planar_map>

- PlanarMapDcel_2

- PlanarMapDcelVertex_2

- PlanarMapDcelHalfedge_2

- Pm_dcel<V,H,F>

- PlanarMapTraits_2

- Pm_segment_traits_2<Kernel>

- PlanarMapChangeNotification_2

- File_header

- Pm_file_scanner<Planar_map>

- Pm_file_writer<Planar_map>

- write_pm

- Pm_drawer<Planar_map, Window>

- draw_pm