Algorithmic Solutions > LEDA > LEDA Guide > Geometry > Orientation and Sidedness
Orientation and SidednessThe Orientation FunctionThe orientation function is probably the most useful geometric primitive. Let
The function int orientation(POINT p, POINT q, POINT r)computes the orientation of the triple (p,q,r) . It returns +1 in
the case of positive, -1 in the case of negative, and 0 in the case of zero
orientation.
There are also predicates to test the orientation: bool left_turn(p,q,r); //corresponds to positive orientation bool right_turn(p,q,r); //corresponds to negative orientation bool collinear(p,q,r); //corresponds to zero orientation Notice that there is also an orientation function for four points in the three-dimensional space. SidednessMany geometric objects, such as lines and circles in the plane, or planes and spheres in three-dimensional space, partition the ambient space into two parts. We designate one of the parts as positive and one as negative. The functionint O.side_of(x);where O is a geometric object and x is a point
in ambient space, returns a positive number (zero, a negative number, respectively)
if x lies in the positive part (lies on O , lies in the negative
part, respectively). Examples are
int l.side_of(x); //l is line int C.side_of(x); //C is circle int P.side_of(x); //P is polygonWe use the orientation function for points to define the positive part as follows: The positive part is the region to the left of the object (positive orientation). In the two-dimensional plane two points defining a line and three points defining a circle impose a sense of direction on the line or circle, respectively, in the natural way. Circles, spheres, triangles, simplices, simple polygons, and many other
geometric objects partition the ambient space into a bounded and an unbounded
region. Since there is no standard convention that connects boundedness
and unboundedness with positive and negative, respectively, we use an
enumeration for the outcome of the enum region_kind {BOUNDED_REGION, ON_REGION, UNBOUNDED_REGION }; region_kind O.region_of(x); //generic form region_kind C.region_of(x); //C is a circleWe have the following predicates for the outcome bool O.inside(x); //x in bounded region bool O.on_boundary(x); //x on boundary bool O.outside(x); //x in unbounded region |
See also:Writing Kernel Independent Code |