cl-geo

Overview

cl-geo is a set of geographic data structures and operations. Though it's not a full GIS system, it's a simple set of tools for GIS applications.

cl-geo is used by the En Route public transit trip planner, which powers En Route Spokane.

Warning

cl-geo is deprecated. The author does not anticpate enhancing this library very much in the future, because the amount of work required is non-trivial and other techniques are being used in place of this library to solve the same problems. (Particularly, En Route now relies on PostGIS for much of its geospatial heavy lifting.)

This library has known accuracy problems due to improper mathematical technique. These methods are not expected to be accurate:

• CONTAINS? (LINE-SEGMENT POINT)
• CONTAINS? (POLYGON POINT)
• INTERSECTION (LINE-SEGMENT LINE-SEGMENT)

Additionally, the AREA function on POLYGONs was so bad in practice that it had to be removed from 0.2.

Quick reference

(The following descriptions are intended for quick reference and feature overview. See the documentation embedded in the classes and functions for more detail.)

Data structures

• DISTANCE: abstract values of length, with mathematical operators defined on them, and conversions to and from many metric and US customary units of length.
• POINT: spherical-coordinate points (latitude & longitude), expressed in radians or degrees.
• LINE-SEGMENT: line segments on the Earth, with an operation to find the intersection of two segments.
• POLYGON: closed, non-self-intersecting polygons.

Functions

Generic functions apply to many combinations of different data structures, and include:

• (bounding-box object): given as an instance of RECTANGLES:RECTANGLE (of the spatial-trees library).
• (contains? containing-obj obj): returns whether containing-obj contains obj.
• (closest-point-on object point &optional precision): the point on the object closest to point.

Bearing (direction) calculations are included:

• (initial-bearing point1 point2): the bearing (in radians) you would take to head from point1 to point2.
• (final-bearing point1 point2): the bearing you would have after heading from point1 to point2.
• (describe-bearing radians): a symbolic representation of the approximation of a bearing: NORTH, NORTHEAST, EAST, SOUTHEAST, SOUTH, SOUTHWEST, WEST, or NORTHWEST.
• (point-from-point-in-direction point initial-bearing distance): the POINT you'd end up at if you start at point, facing initial-bearing, and travel the given distance.
• (bearing-difference bearing1 bearing2): the difference of two bearings, as radians in the range [-π,+π).
• (relative-bearing point1 point2 point3): having travelled from point1 to point2, returns the relative bearing to then travel from point2 to point3, in radians in the range [-π,+π).
• (describe-relative-bearing radians): for the given relative bearing, returns symbolic representations of its direction (LEFT, RIGHT, or NIL for dead-ahead) and approximate absolute angle (STRAIGHT, OBTUSE, RIGHT, ACUTE, REVERSE).

Other functions include:

• (distance-between point1 point2)
• (midpoint points-list)
• (greatest-distance &rest points): the greatest distance between any two of the given points.
• (closest-point point points &key key): the object from points that is closest to point. key is applied to each object in points to produce the actual point for comparison, in which case these objects don't necessarily have to be POINT instances. So, to find the closest line segment to point, you could give a list of LINE-SEGMENTs as points, with a key function that returns the closest point on its given line to point.
• (douglas-peucker points threshold-distance &optional slow-and-accurate-p): Annotates a polyline expressed by points, giving you enough information to selectively reduce the detail of (or simplify/smooth) the polyline. Returns a vector of distances parallel to the given sequence of POINTs. Each distance expresses the prominence of its point; smaller distances correspond to points that may be "shaved off" in order to simplify the polyline. NIL may be in place of some distances to indicate that the corresponding point has been discarded, and T will be in place at the first and last points. This is a variant of the Ramer-Douglas-Peucker algorithm.
• (google-polyline points &key ...): encodes the given list of POINTs with Google's encoded polyline coding. For use with the Google Maps API. See the function signature and documentation for detailed usage information. See google-polyline.lisp for low-level encoding functions for points, reals, signed integers, and unsigned integers.

Download

The most recent release is 0.2, released 2011-06-14. It depends on: spatial-trees (Debian: cl-spatial-trees), cl-jpl-util (version 0.4 or later).

Breaking changes in 0.2:

• The package has been renamed from COM.ENROUTESYSTEMS.GEO to GEO. Previously, GEO was a nickname. If you used this nickname in your code, you should not have to update it for the change of package name.
• The AREA function on POLYGON has been deleted due to poor accuracy. It would take a lot of work to implement this function correctly, and the author no longer needs this functionality. I apologize if this impacts you.

Other changes:

• GOOGLE-POLYLINE now correctly uses *STANDARD-OUTPUT* when given T as a stream.
• New function COERCE-POINT.
• New function INTERPOLATE-BETWEEN-POINTS.
• Small clean-ups, microoptimizations, and docstring clarifications.

Download:

• cl-geo-0.2.tar.gz: ASDF package
• cl-geo-0.2.tar.gz.sig: OpenPGP detached signature

Older version:

• cl-geo-0.1.tar.gz: ASDF package
• cl-geo-0.1.tar.gz.sig: OpenPGP detached signature

I sign all my software with OpenPGP, key ID 0x80555CED7394F948, fingerprint 2771 AF53 5D09 BDFB A8D0 BEF3 8055 5CED 7394 F948.

Copying

This software is licensed under permissive, BSD-like terms, copied from the ISC license:

Contact

I'm reachable via e-mail for feedback, questions, help requests, and bug reports: jpl-software at surejourney.com