An instance S of the parameterized data type subdivision<I> is a subdivision of the two-dimensional plane, i.e., an embedded planar graph with straight line edges (see also sections Planar Maps and Parameterized Planar Maps). With each node v of S is associated a point, called the position of v and with each face of S is associated an information from data type I , called the information type of S .
#include < LEDA/geo/subdivision.h >
|subdivision< I>||S(GRAPH< point,I> & G)||creates an instance S of type subdivision<I> and initializes it to
the subdivision represented by the parameterized directed graph G
The node entries of G
(of type point) define the positions of the
corresponding nodes of S. Every face f
of S is assigned the
information of one of its bounding edges in G
Precondition G represents a planar subdivision, i.e., a straight line embedded planar map.
|point||S.position(node v)||returns the position of node v .|
|const I&||S.inf(face f)||returns the information of face f .|
|face||S.locate_point(point p)||returns the face containing point p .|
|face||S.outer_face()||returns the outer face of S.|
Planar subdivisions are implemented by parameterized planar maps and an additional data structure for point location based on partially persistent search trees. Operations position and inf take constant time, a locate_point operation takes (expected) time O(log n) . Here n is the number of nodes. The space requirement is O(n + m) and the initialization time is O(n + m log m) , where m is the number of edges in the map.