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.


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.

	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

See also:

Data Types for 2D Geometry

Data Types for 3-D Geometry

Writing Kernel Independent Code


Advanced Data types for 2-D geometry

Geometry Algorithms


Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH