Next: Sets of Intervals ( Up: Advanced Data Types for Previous: Point Sets and Delaunay Contents Index

Point Location in Triangulations ( POINT_LOCATOR )

Definition

An instance PS of data type POINT_LOCATOR is a data structure for efficient point location in triangulations.

There are three instantiations of POINT_LOCATOR: point_locator (floating point kernel), rat_point_locator (rational kernel) and real_point_locator (real kernel). The respective header file name corresponds to the type name (with ``.h'' appended).

#include < LEDA/geo/generic/POINT_LOCATOR.h >

Creation

POINT_LOCATOR PS(const GRAPH<POINT,int>& T)

creates a point locator for a triangulation T.

POINT_LOCATOR PS(const GRAPH<POINT,SEGMENT>& T)

creates a point locator for a constrained triangulation T.

POINT_LOCATOR PS(const graph& T, node_array<POINT>& p)

creates a point locator for a general triangulation T. Node positions have to be provided in node_array p.

Operations

edge PS.locate(POINT q) returns an edge e of PS that contains q or that borders the face that contains q. In the former case, a hull edge is returned if q lies on the boundary of the convex hull. In the latter case we have PS.orientation(e,q) > 0 except if all points of PS are collinear and q lies on the induced line. In this case target(e) is visible from q. The operation returns nil if PS is empty.

bool PS.check_locate(POINT q, edge e)

checks whether e could be the result of PS.locate(q).

Next: Sets of Intervals ( Up: Advanced Data Types for Previous: Point Sets and Delaunay Contents Index

POINT_LOCATOR	PS(const GRAPH<POINT,int>& T)
		creates a point locator for a triangulation T.
POINT_LOCATOR	PS(const GRAPH<POINT,SEGMENT>& T)
		creates a point locator for a constrained triangulation T.
POINT_LOCATOR	PS(const graph& T, node_array<POINT>& p)
		creates a point locator for a general triangulation T. Node positions have to be provided in node_array p.

edge	PS.locate(POINT q)	returns an edge e of PS that contains q or that borders the face that contains q. In the former case, a hull edge is returned if q lies on the boundary of the convex hull. In the latter case we have PS.orientation(e,q) > 0 except if all points of PS are collinear and q lies on the induced line. In this case target(e) is visible from q. The operation returns nil if PS is empty.
bool	PS.check_locate(POINT q, edge e)
		checks whether e could be the result of PS.locate(q).