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.


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

A type that holds an x-monotone curve in the plane.

A type that holds the position of a vertex in the plane. The type of the end points of X_monotone_curve_2 curves.

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.


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.

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.

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.

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.

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.

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.

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.

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.

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

Arr_polyline_traits<Kernel, Container>
Arr_leda_polyline_traits<Kernel, Container>

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