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

### See also:

Data Types for 2D Geometry

Data Types for 3-D Geometry

Writing Kernel Independent Code

Geometry

Advanced Data types for 2-D geometry

Geometry Algorithms

GeoWin

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH