Test if a Point lies inside a Polygon (from CGA FAQ)

The CGA FAQ describes an algorithm to test if a point lies within a polygon. Roughly speaking, you start from the point and travel north. If you cross an odd number of sides, it means that you were within the polygon when you started and vice versa.

Test if a point lies inside or outside a polygon

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: http://code.google.com/p/curve-project/source/browse/trunk/lab/cgafaq/cgafaq.h The function cgafaq::point_in_polygon takes a point and a polygon and returns whether or not the point lies inside the polygon. This is a direct translation of the code from the FAQ.

Disclaimer: This post and the code provided are not endorsed by any of the contributors to the CGA FAQ.

Orientation of Polygons (from CGA FAQ)

The orientation of a polygon tells us if the vertices are ordered clockwise or counter-clockwise as we move along the perimeter. This is determined by calculating the polygon’s signed area which is positive for counter-clockwise orientation and negative for clockwise orientation. A quicker algorithm is to determine the signed area of the triangle formed by the lowest right most vertex and it’s immediate neighbors.

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: http://code.google.com/p/curve-project/source/browse/trunk/lab/cgafaq/cgafaq.h The function cgafaq::orientation has two overloads. The first computes orientation for three vertices and the second calculates the orientation of a polygon.

Disclaimer: This post and the code provided are not endorsed by any of the contributors to the CGA FAQ.

Distance of a Point from a Line (from CGA FAQ)

The distance of a point from a line is the length of a perpendicular drawn from the point to the line. Here are the possibilities:

  • Perpendicular meets on the line segment
  • Perpendicular meets on a forward/backward extension of the line segment

Distance of a point from a line

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: http://code.google.com/p/curve-project/source/browse/trunk/lab/cgafaq/cgafaq.h The function cgafaq::distance_from_line takes the start and end points of the line and the point from which distance is to be calculated. r and s are output parameters calculated as described in the FAQ.

Note that if distance is not important and only a perpendicular needs to be generated then there is a simpler way to construct one.

Disclaimer: This post and the code provided are not endorsed by any of the contributors to the CGA FAQ.

Intersection of Line Segments (from CGA FAQ)


Intersection of two line segments
involves the following cases:

  • Segments are parallel
  • Segments are collinear/coincident
  • One segment intersects the extension of the other
  • Extension of one segment intersects the extension of the other
  • Segments intersect each other.

Intersection of Two Line Segments

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: http://code.google.com/p/curve-project/source/browse/trunk/lab/cgafaq/cgafaq.h The function cgafaq::intersect takes 4 points — the start and end points of each of the lines. r and s are output parameters calculated as described in the FAQ.

Disclaimer: This post and the code provided are not endorsed by any of the contributors to the CGA FAQ.