LEDA Guide: Orientation and Sidedness

Algorithmic Solutions > LEDA > LEDA Guide > Geometry > Orientation and Sidedness

Orientation and Sidedness

The Orientation Function

The orientation function is probably the most useful geometric primitive.

Let p,q, and r be three points in the plane. The triple (p,q,r) has

positive orientation if p,q, and r form a counter-clockwise oriented triangle,
negative orientation if p,q, and r form clockwise oriented triangle,
zero orientation otherwise.

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.

Sidedness

Many 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 function

	int 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 polygon

We 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 region_of() function.

	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 circle

We 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

Complete Example for Orientation and Sidedness

Orientation and Sidedness

The Orientation Function

Sidedness

See also: