SweepLineTraits_2

Definition

A model of the concept SweepLineTraits_2 aggregates the geometric types and primitive operations used by the Sweep_line_2<CurveInputIterator,SweepLineTraits_2> data structure.

Types

The geometric types defined below must have a default constructor, copy constructor, and assignment operator.

SweepLineTraits_2::X_monotone_curve_2
	A type that holds an $$x-monotone curve in the plane.
SweepLineTraits_2::Point_2
	A type that holds the position of a vertex in the plane. The type of the end points of X_monotone_curve_2 curves.
SweepLineTraits_2::Curve_2
	A type that holds a general curve in the plane. Its endpoints must be of type Point_2. Curves of type either X_monotone_curve_2 or Curve_2 can be inserted into a Planar_map_with_intersections_2<Dcel,Traits> object.

Operations

Comparison_result	tr.compare_x ( Point_2 p0, Point_2 p1)
		compares the x-coordinates of $$p0 and $$p1. Returns LARGER if $$x(p0) > x(p1); SMALLER if $$x(p0) < x(p1); EQUAL otherwise.
Comparison_result	tr.compare_xy ( Point_2 p0, Point_2 p1)
		compares the two points $$p0 and $$p1 lexigoraphically. First the $$x-coordinates are compared. In case of a tie, the $$y-coordinates are compared. Returns LARGER if $$x(p1) > x(p2), or if $$x(p1) = x(p2) and $$y(p1) > y(p2); SMALLER if $$x(p1) < x(p2), or if $$x(p1) = x(p2) and $$y(p1) < y(p2); EQUAL otherwise.
bool	tr.curve_is_vertical ( X_monotone_curve_2 cv)
		returns true if cv is a vertical segment, false otherwise.
bool	tr.point_in_x_range ( X_monotone_curve_2 cv, Point_2 pnt)
		returns true if pnt is in the $$x range of cv, false otherwise.
Comparison_result	tr.curves_compare_y_at_x ( X_monotone_curve_2 cv1, X_monotone_curve_2 cv2, Point_2 pnt)
		compares the $$y-coordinate of $$cv1 and $$cv2 at the $$x-coordinate of $$pnt. Returns LARGER if $$cv1(x(q)) > cv2(x(q)); SMALLER if $$cv1(x(q)) < cv2(x(q)); EQUAL otherwise. Precondition: $$cv1 and $$cv2 are defined at $$pnt's $$x-coordinate. Precondition: $$cv1 or $$cv2 contain $$pnt.
Comparison_result	tr.curves_compare_y_at_x_right ( X_monotone_curve_2 cv1, X_monotone_curve_2 cv2, Point_2 pnt)
		compares the $$y-coordinate of $$cv1 and $$cv2 immediately to the right of the $$x-coordinate of $$pnt. Precondition: $$cv1 and $$cv2 meet at $$pnt $$x-coordinate. Precondition: $$cv1 and $$cv2 are defined to the right of $$pnt's $$x-coordinate.
Comparison_result	tr.curve_compare_y_at_x ( Point_2 pnt, X_monotone_curve_2 cv)
		compares the $$y-coordinates of $$pnt and the vertical projection of $$pnt on $$cv. Returns SMALLER if $$y(p) < cv(x(p)); LARGER if $$y(p) > cv(x(p)); EQUAL otherwise (p is on the curve). Precondition: $$cv is defined at $$pnt's $$x-coordinate.
bool	tr.curve_equal ( X_monotone_curve_2 cv1, X_monotone_curve_2 cv2)
		returns true if cv1 and cv2 have the same graph, false otherwise.
bool	tr.point_equal ( Point_2 p1, Point_2 p2)
		returns true if p1 is the same as p2, false otherwise.
bool	tr.curves_overlap ( X_monotone_curve_2 cv1, X_monotone_curve_2 cv2)
		returns true if cv1 and cv2 overlap in a one-dimensional subcurve (i.e., non countable and non infinite number of points), false. otherwise.
Point_2	tr.curve_source ( X_monotone_curve_2 cv)
		returns the source of cv.
Point_2	tr.curve_target ( X_monotone_curve_2 cv)
		returns the target of cv.
template<class OutputIterator>
OutputIterator	tr.make_x_monotone ( Curve_2 cv, OutputIterator res)
		cuts cv into $$x-monotone subcurves and stores them in a sequence starting at res. The order in which they are stored defines their order in the hierarchy tree. Returns past-the-end iterator of the sequence.
void	tr.curve_split ( X_monotone_curve_2 cv, X_monotone_curve_2& c1, X_monotone_curve_2& c2, Point_2 split_pt)
		splits $$cv at split_pt into two curves, and assigns them to c1 and c2 respectively. Precondition: split_pt is on cv but is not one of its endpoint.
bool	tr.nearest_intersection_to_right ( X_monotone_curve_2 c1, X_monotone_curve_2 c2, Point_2 pt, Point_2& p1, Point_2& p2)
		finds the nearest intersection point (or points) of c1 and c2 lexicographically to the right of pt not including pt itself, (with one exception explained below). If the intersection of c1 and c2 is an X_monotone_curve_2, that is, they overlap at infinitely many points, then if the right endpoint and the left endpoint of the overlapping subcurve are strictly to the right of pt, they are returned through the two point references p1 and p2 respectively. If pt is between the overlapping-subcurve endpoints, or pt is its left endpoint, pt and the right endpoint of the subcurve are returned through p1 and p2 respectively. If the intersection of the two curves is a point to the right of pt, it is returned through p1 and p2. Returns true if c1 and c2 do intersect to the right of pt, false otherwise.

Has Models

Note that the concept ArrangementTraits_2 is a refinement of the concept SweepLineTraits_2 so each model of the former is a model of the latter.

See Also

CGAL::Sweep_line_2