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

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