point-polygon 1.0: point inside polygon test for Common Lisp

point-polygon is a Common Lisp library to test if a point lies inside or outside a polygon in 2 dimensions coordinates.

Source code is released under a MIT License and hosted at git repository https://gitlab.com/janduja/point-polygon.git under branch 1.0.

A compressed zip package can be downloaded at http://janduja.com/point-polygon/point-polygon-1.0.tar.gz.

Contents:

  1. Installation
  2. Use
  3. Internals
  4. Tests and compatibility

Installation

The library has no dependencies and can be loaded directly or as an ASDF package. First, get the source code or unpack the zip file.

To load directly:

(load "point-polygon.lisp")
To load as an ASDF system, ensure that the library source is located in a directory looked by ASDF (ie. ~/common-lisp/point-polygon), then in your code:
(asdf:load-system :point-polygon)

Use

[Function] is-inside-or-border point polygon => is-inside
Tells if point is inside or in the border of polygon. point is expected to be a list of two values, the coodinate pair, while polygon is a list of coordinate pairs such that the first element is pairwise equal to the last element. A coordinate is expected to be a numeric float, but not necessarly. Returns T if the point lies inside the polygon, false otherwise.

The following example shows how to test if a point lies inside or outside a trapezoid:

(let ((trapezoid '((-23.24D0 11.87D0) (7.29D0 53.99D0) (29.48D0 32.14D0) (5.07D0 -50.99D0) (-23.24D0 11.87D0))))
  (is-inside-or-border '(27.90D0 52.76D0) trapezoid))

Internals

The test is implemented by the winding number algorithm.
Using the point to test as reference, traversing the polygon from the first element to the last one we track the number of windings around the point: if the value is zero the point lies outside, otherwise it lies inside.


Image: winding number tracking, source: Wikipedia. Author: Jim.belk. Released in the public domain.

In the code implementation, the computation of the winding number is tracked by quadrant movements: setting the point to test as origin of a Cartesian plane, traversing the polygon from a point to the next can be identified by an integer quadrant movement:

If a point of the polygon is the same as the point to test, we then know that the point lies in the border and we are done.
In the case of a traversing from a quadrant to the opposite, we need to calculate the abscissa projection of the point to the segment of the polygon. Then: The total sum is (four times) the winding number.
The abscissa projection involves an algebraic computation, so the result becomes less accurate as the point to test is closer to the border.
In the code the four quadrants are identified by the following trigonometric ranges: [0,pi/2) [pi/2,pi) [pi,3pi/4) [3pi/4,2pi).

Tests and compatibility

Tests are collected in file point-polygon-test.lisp under the test directory and have dependencies on lisp-unit and jsown.

To run the tests you have to position as current directory in the point-polygon/test, then launch your Common Lisp implementation and load the file point-polygon-test.lisp. A Unit Test report is printed on the standard output telling the run tests, the passed and failed assertions and the execution errors.

The tests run successfully with the following Common Lisp implementations and hardware configuration:

[uname]Debian 3.16.36-1+deb8u2 (2016-10-19) x86_64 GNU/Linux
[lscpu]CPU(s): 4
[/proc/cpuinfo]model name : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
[/proc/cpuinfo]cache size : 8192 KB
[/proc/cpuinfo]address sizes : 39 bits physical, 48 bits virtual
[lscpu]CPU MHz 3591.684
[/proc/meminfo]MemTotal: 11418128 kB


Last edited on: 04 Sep 2017
Author: Raffaele Arecchi
Contact the author of this document via email to: raffaele.arecchi {at} gmail {point} com.