Polygon Sponsor
|
Segment Concept
The segment concept tag is segment_concept
To register a user defined type as a model of the segment
concept, specialize the geometry concept meta-function for that
type. In the example below CSegment is registered as a model of
the segment concept.
template <>
struct geometry_concept<CSegment>
{ typedef segment_concept type; };
The semantic of a segment is
that it has a low and high point. A
std::pair<Point, Point>,
boost::tuple<Point, Point> or boost::array<Point, 2> could all be made models of
segment by simply providing indirect access to their elements through
traits, however, these objects cannot be made a model of both segment
and rectangle in the same compilation unit, for obvious reason that
duplicate specialization of the geometry_concept struct is illegal, but
also because it would make overloading generic function by concept
ambiguous if a type modeled more than one concept.
Below is shown the default
segment traits. Specialization of these traits is required for
types that don't conform to the default behavior.
template <typename Segment>
struct segment_traits {
typedef typename Segment::coordinate_type coordinate_type;
typedef typename Segment::point_type point_type;
static inline point_type get(const Segment& segment, direction_1d dir) {
return segment.get(dir);
}
};
template <typename Segment>
struct segment_mutable_traits {
typedef typename segment_traits<Segment>::point_type point_type;
static inline void set(Segment& segment, direction_1d dir, const point_type& point) {
segment.set(dir, p);
}
static inline Segment construct(const point_type& low, const point_type& high) {
return Segment(low, high);
}
}; Functions
template
<typename Segment> point_type get(const Segment& segment, direction_1d dir) |
Returns the low or high endpoint of an object that models segment, depending on
the direction_1d value. |
template
<typename Segment, typename Point>
void set(Segment& segment, direction_1d dir,
const Point& point) |
Sets
the low or high endpoint of an object that models segment to an object
that models point, depending on the direction_1d value. |
template <typename Segment, typename Point1, typename Point2>
Segment construct(const Point1& low, const Point2& high) |
Constructs an object that is a model of segment given the two objects that are models of point. |
template <typename Segment1, typename Segment2> Segment1 copy_construct(const Segment2& segment) |
Copy constructs an object that models segment given another segment. |
template
<typename Segment1, typename Segment2>
Segment1& assign(Segment1& segment1,
const Segment2& segment2) |
Copies data from the second object that models segment into
the first object that models segment. |
template
<typename Segment1, typename Segment1>
bool equivalence(const Segment1& segment1,
const Segment1& segment2) |
Given two objects that model segment, compares and
returns true if their low and high values are respectively equal. |
template <typename Segment, typename Point>
int orientation(const Segment& segment,
const Point& point)
|
Implements
a robust orientation test of two objects that model segment and point.
Returns 0, if the point is collinear to the segment.
Returns 1, if the point lies to the left of the segment.
Returns -1, if the point lies to the right of the segment.
|
template <typename Segment1, typename Segment2>
int orientation(const Segment1& segment1,
const Segment2& segment2) |
Implements a robust orientation test of two objects
that model segment. Note: segments are treated as math.
vectors.
Returns 0, if segments are collinear.
Returns 1, if the second segment is CCW oriented to the first segment.
Returns -1, if the second segment is CW oriented to the first segment.
|
template <typename Segment, typename Point>
bool contains(const Segment& segment,
const Point& value, bool consider_touch)
|
Returns true if an object that models segment contains an object that models point, else false.
|
template <typename Segment1, typename Segment2>
bool contains(const Segment1& segment1,
const Segment2& segment2, bool consider_touch) |
Returns true if the first object contains the second one, else false. Both objects model segment.
|
template <typename Segment>
point_type low(const Segment& segment)
|
Returns the low endpoint of an object that models segment.
|
template <typename Segment>
point_type high(const Segment& segment) |
Returns the high endpoint of an object that models segment.
|
template <typename Segment>
point_type center(const Segment& segment) |
Returns the central point of an object that models segment.
|
template <typename Segment, typename Point> void low(Segment& segment, const Point& point) |
Sets the low endpoint of an object that models segment.
|
template <typename Segment, typename Point>
void high(Segment& segment, const Point& point) |
Sets the high endpoint of an object that models of segment.
|
template <typename Segment>
distance_type length(const Segment& segment)
|
Returns length of an object that models segment.
|
template
<typename Segment> Segment& scale_up(Segment& segment, unsigned_area_type factor) |
Multiplies x and y coordinates of both endpoints of an object that models segment by unsigned factor. |
template
<typename Segment>
Segment& scale_down(Segment& segment,
unsigned_area_type factor) |
Divides x and y coordinates of both endpoints of an object that models segment by unsigned factor. |
template
<typename Segment, typename Scale>
Segment& scale(Segment& segment, const Scale& sc) |
Calls
the scale member function of the scaling type on the low and high endpoint of
an object that models segment and updates the segment with the
scaled endpoints. |
template
<typename Segment, typename Transform> Segment& transform(Segment& segment, const Transform& tr) |
Calls the transform member function of transform type
on the low and high endpoints of an object that models segment and updates the segment with the transformed endpoints. |
template
<typename Segment>
Segment& move(Segment& segment, orientation_2d
coordinate_difference displacement) |
Adds displacement value to the x or y coordinates of both endpoints of an object
that models segment indicated by the orientation_2d. |
template
<Segment, Point>
Segment& convolve(Segment& segment, const Point& point) |
Convolves both endpoints of an object that models segment with an object that models a point.
|
template
<Segment, Point>
Segment& deconvolve(Segment& segment, const Point& point) |
Deconvolves both endpoints of an object that models segment with an object that models a point. |
template <typename Segment1, typename Segment2>
bool abuts(const Segment1& segment1,
const Segment2& segment2, direction_1d dir) |
Returns true if two objects that model segment abut, depending on the direction_1d value. |
template <typename Segment1, typename Segment2>
bool abuts(const Segment1& segment1,
const Segment2& segment2) |
Returns true if two objects that model segment abut: either the first one to the second one or vice versa. |
template <typename Segment1, typename Segment2>
bool intersects(const Segment1& segment1,
const Segment2& segment2,
bool consider_touch)
|
Returns true if two objects that model segment intersect, else false.
|
template
<typename Segment, typename Point> distance_type euclidean_distance(
const Segment& segment, const Point& point)
|
Returns distance from an object that models segment
to an object that models point.
|
template
<typename Segment1, typename Segment2> distance_type euclidean_distance(
const Segment1& segment1, const Segment2& segment2)
|
Returns distance between two objects that model segment.
|
Segment Data
The library provides a model of the segment concept declared template<typename T> segment_data, where
T is the coordinate type.
This data type is used internally when a segment is needed and
is available to the library user, who finds it convenient to use a
library segment data type instead of providing their own. The data
type is implemented to be convenient to use with the library traits. Members
geometry_type |
segment_concept |
coordinate_type |
T |
point_type |
point_data<T>
|
segment_data() |
Default constructor. |
segment_data(const point_type& low,
const point_type& high) |
Constructs a segment from the given endpoints. |
segment_data(const segment_data& that) |
Copy constructor. |
segment_data& operator=(const segment_data& that) |
Assignment operator. |
template
<typename Segment>
segment_data& operator=(const Segment& that)
const |
Assign from an object that is a model of segment. |
bool operator==(const segment_data& that) const |
Equality operator overload. |
bool operator!=(const segment_data& that) const |
Inequality operator overload. |
bool operator<(const segment_data& that) const |
Less operator overload. Compares low endpoints then high endpoints to break ties.
|
bool operator<=(const segment_data& that) const |
Less or equal operator overload. Compares low endpoints then high endpoints to break ties.
|
bool operator>(const segment_data& that) const |
Greater operator overload. Compares low endpoints then high endpoints to break ties.
|
bool operator>=(const segment_data& that) const |
Greater or equal operator overload. Compares low endpoints then high endpoints to break ties.
|
point_type get(direction_1d dir) const |
Retrieves the low/high endpoint considering direction value. |
point_type low() const |
Retrieves the low endpoint. |
point_type high() const |
Retrieves the high endpoint. |
void set(direction_1d dir, const point_type& point) |
Sets the endpoint in the given direction. |
segment_data& low(const point_type& point) |
Sets the low endpoint. |
segment_data& high(const point_type& point) |
Sets the high endpoint. |
Segment Utils
The library provides several algorithms for the manipulation of
sets of segment data. In particular, the generalize line segment
intersection algorithm used for polygon set operations is exposed
through several interfaces to allow it to be used with any
collection or sequence of objects that model the segment_concept.
Functions
template
<typename SegmentContainer,
typename SegmentIterator>
void intersect_segments(
SegmentContainer* result,
SegmentIterator first,
SegmentIterator last)
|
Accumulates
the result of splitting the segments in the iterator range at their
intersection points into the result container. Preconditions: segment
type used by all the input structures should model segment concept.Postconditions: no segments intersect except at their end
points. Useful to satisfy the precondition of voronoi diagram
construction.
Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
|
template
<typename Segment,
typename SegmentIterator>
void intersect_segments(
vector<pair<size_t, Segment>* result,
SegmentIterator first,
SegmentIterator last) |
Accumulates
the result of splitting the segments in the iterator range at their
intersection points into the result container. Preconditions: segment
type used by all the input structures should model segment concept.
Postconditions: no segments intersect except at their end points. The
index of the input segment is paired with each resultant segment that
was split to produce it to associate the result segments with the
inputs segments. Expected n log n runtime, worst case quadratic runtime
wrt. vertices + intersections. |
template
<typename Rectangle,
typename SegmentIterator>
void envelope_segments(
Rectangle* rect,
SegmentIterator first, SegmentIterator last)
|
Computes
the bounding rectangle of the iterator range of line segments.
Preconditions: segment type and rectangle type used by the input
structures should model segment concept and rectangle concept
respectively. Linear runtime. |
|