Common Lisp Package: 2D-GEOMETRY

README:

FUNCTION

Public

AREA-CIRCLE (R)

Area of a circle.

AREA-ELLIPSE-AXES (A B)

Area of an ellipse given semimajor and semiminor axes.

AREA-RECTANGLE (A B)

Area of a rectangle given length of edges.

AREA-SIMPLE-POLYGON (POLYGON)

Calculate an area of a simple polygon.

AREA-SQUARE (A)

Area of a square given length of a side.

AREA-TRIANGLE-EDGE-EDGE-ANGLE (A B ALPHA)

Area of a triangle given length of two edges and an angle between them.

AREA-TRIANGLE-EDGES (A B C)

Area of a triangle given length of edges using Heron's formula. Numerically unstable for triangles with very small angles.

AREA-TRIANGLE-EDGES-SMALL-ANGLES (A B C)

Area of a triangle given length of edges using numerically stabilized Heron's formula.

AREA-TRIANGLE-VERTICES (XA YA XB YB XC YC)

Area of a triangle given positions of vertices. Will return negative for clockwise oriented triangle.

BENTLEY-OTTMANN (EDGE-LIST)

Return a list of intersection points (events).

CIRCUMFERENCE-CIRCLE (R)

Circumference of a circle.

CIRCUMFERENCE-ELLIPSE-AXES (A B)

Circumference of an ellipse given semimajor and semiminro axes using Ramanujan's approximation.

COLINEAR-P (A B C)

Is c on the line defined by a->b?

COORDS-TO-POINTS (&REST COORD-LIST)

Coordinate list (x1 y1 x2 y2 ... xn yn) to point list

DECOMPOSE-COMPLEX-POLYGON-BENTLEY-OTTMANN (POLYGON)

Decompose polygon using bentley-ottmann, hopefully in something close to quadratic time.

DECOMPOSE-COMPLEX-POLYGON-NONDISJOINT (POLYGON)

Decomposes a complex polygon into a set of simple ones, possibly some entirely contained in others.

DECOMPOSE-COMPLEX-POLYGON-TRIANGLES (POLYGON &KEY (IN-TEST 'POINT-IN-POLYGON-WINDING-P))

Decomposes a complex polygon into triangles. Returns a list of triangles inside polygon according to :in-test, which is a function taking a point and a polygon.

DISTANCE (X1 Y1 X2 Y2)

Distance between two points on a plane.

FRUSTRATED-POLYGON-P (POLYGON)

Check if there are any zero length edges or that any two colinear edges intersect.

LINE-FROM-SEGMENT (LINE-SEGMENT)

Calculate line from line segment.

LINE-SEGMENT-LENGTH (LINE-SEGMENT)

Calculate length of a segment.

LINE-SEGMENTS-INTERSECTION-POINT (LINE-SEGMENT1 LINE-SEGMENT2 &KEY (EXCLUDE-ENDPOINTS NIL))

Find point of intersection of two segments. Returns nil if they do not intersect and point instance otherwise.

LINE-SEGMENTS-INTERSECTION-SEGMENT (LINE-SEGMENT1 LINE-SEGMENT2)

Find an intersection of two colinear line segments.

LINE-X-AT-Y (LINE Y)

Return x coordinate of a point with a given y coordinate on a line.

LINE-Y-AT-X (LINE X)

Return y coordinate of a point with a given x coordinate on a line.

LINES-EQUAL-P (LINE1 LINE2)

Check if two lines are equal.

LINES-INTERSECTION-POINT (LINE1 LINE2)

Find point of intersection of two lines. Returns nil if lines are parallel and point instance otherwise.

LINES-PARRALEL-P (LINE1 LINE2)

Check if two lines are parrallel.

PERIMETER-RECTANGLE (A B)

Perimeter of a rectangle given length of edges.

PERIMETER-SQUARE (A)

Perimeter of a square given length of a side.

PERIMETER-TRIANGLE (A B C)

Perimeter of a triangle given length of edges.

POINT-EQUAL-P (POINT1 POINT2)

Checks if two points are geometrically equal.

POINT-IN-POLYGON-CROSSING-P (POINT POLYGON)

Determine if a point belongs to a polygon using crossing (oddeven) rule.

POINT-IN-POLYGON-WINDING-NUMBER (POINT POLYGON)

Calculate winding number of a point.

POINT-IN-POLYGON-WINDING-P (POINT POLYGON)

Check if point is in polygon using winding number rule.

POLYGON-DIFFERENCE (POLYGON1 POLYGON2 &KEY (IN-TEST 'POINT-IN-POLYGON-WINDING-P) (IN-TEST-1 NIL) (IN-TEST-2 NIL))

Return triangles of polygon1 minus polygon2.

POLYGON-DIFFERENCE-NARY (POLYGON &REST HOLES &KEY (IN-TEST 'POINT-IN-POLYGON-WINDING-P))

Return triangles of polygon with some holes.

POLYGON-INTERSECTION (POLYGON1 POLYGON2 &KEY (IN-TEST 'POINT-IN-POLYGON-WINDING-P) (IN-TEST-1 NIL) (IN-TEST-2 NIL))

Return triangles of an intersection of two polygons.

POLYGON-ORIENTATION (POLYGON)

Return 1 if polygon is counterclockwise and -1 if it is oriented clockwise. Assumes simple polygon.

POLYGON-UNION (POLYGON1 POLYGON2 &KEY (IN-TEST 'POINT-IN-POLYGON-WINDING-P) (IN-TEST-1 NIL) (IN-TEST-2 NIL))

Return triangles of an union of two polygons.

SHAMOS-HOEY (EDGE-LIST)

Returns t if there is at least one intersection.

SIMPLE-POLYGON-P (POLYGON)

Check if polygon is simple, ie. if no two edges intersect, assuming only point intersections are possible. This uses brute force, comparing each edge to every other edge.

SIMPLE-POLYGON-SH-P (POLYGON)

Check if polygon is simple using Shamos-Hoey algorithm.

TRIANGULATE (POLYGON)

Triangulate polygon. Returns list of triangles.

Undocumented

MAKE-POLYGON-FROM-COORDS (&REST COORD-LIST)

MAKE-POLYGON-FROM-POINT-LIST (POINT-LIST)

MAKE-POLYGON-FROM-POINT-RING (POINT-RING)

Private

ADD-IF-INTERSECTION (EDGE1 EDGE2 EVENT-QUEUE CURRENT-POINT)

Add intersection to event queue if edge1 intersects edge2.

BETWEEN-P (A B C)

Is c colinear with a->b and lies between them?

BOUNDING-BOXES-INTERSECT-P (BOX1 BOX2)

Check if two bounding boxes intersect.

CHECK-NODE-INTEGRITY (NODE SWEEP-LINE)

Verify sweep line tree node integrity, recursively descending into children.

CHECK-TREE-INTEGRITY (SWEEP-LINE)

Verify sweep line tree integrity.

COLLAPSE-TRAPEZOID (TRAPEZOID)

Reduce degenerate trapezoids to triangles.

COLLECT-RING-NODES (RING)

Construct a list of all nodes in a ring.

CREATE-INITIAL-EVENT-LIST (EDGE-LIST)

Create initial list of endpoint events.

DELETE-EDGE (EDGE SWEEP-LINE)

Delete an edge from sweep-line, returns a cons of newly neighbouring edges.

DIAGONAL-P (RING-NODE-A RING-NODE-B)

Is a line segment between two nodes a diagonal of polygon the nodes belong to?

DOUBLE-LINKED-RING-FROM-POINT-LIST (POINT-LIST &OPTIONAL (RING-TYPE 'POLY-RING-NODE))

Change polygon representation from list of points to double linked ring of points.

EAR-INIT (POINT-LIST)

Takes a list of points and creates a ring initialized with ear data.

EDGE-LIST-FROM-POINT-LIST (POINT-LIST &OPTIONAL (EDGE-TYPE 'LINE-SEGMENT))

Change polygon represented as a list of points into a list of edges (line segments).

FILTER-RAY-INTERSECTION (POINT EDGE)

Return t if edge does not intersect ray from point properly.

IN-CONE-P (RING-NODE B)

Is line segment ring-node->b in cone defined by angle with vertex defined by ring-node?

INSERT-EDGE (EDGE SWEEP-LINE)

Insert new edge into sweep-line, returns a cons of neighbouring edges.

INTERSECT-BOXES (BOX1 BOX2)

Return bounding box common to both boxes.

INTERSECT-P (A B C D)

Do segments a->b and c->d intersect?

INTERSECT-PROPER-P (A B C D)

Do segments a->b and c->d intersect?

LEFT-ENDPOINT (EDGE)

Return left endpoint of an edge.

LEFT-ON-P (A B C)

Is c to the left or on the oriented line defined by a->b?

LEFT-P (A B C)

Is c to the left of the oriented line defined by a->b?

MAKE-LINE-SEGMENT (START END &OPTIONAL (LINE-SEGMENT-TYPE 'LINE-SEGMENT))

Create a new line segment.

MAKE-POINT (X Y &OPTIONAL (POINT-TYPE 'POINT))

Create a new point like object.

MERGE-LINE-SEGMENT-INTO (LS1 LS2)

If two segments are colinear and intersect, extends the first one to include the second. Reorients the first edge to the left.

MOVE-SWEEP-LINE (SWEEP-LINE X Y)

Move sweep line to new location.

NOTANY-SYMMETRIC-TEST (TESTFUN LIST)

Return t if test is nil for every combination of elements of list, assuming test is symmetric.

ORDER-LINE-SEGMENTS-AT-POINT (LV RV POINT)

Return t if lv is above rv at point.

ORIENT-EDGE-RIGHT (EDGE)

Returns an edge oriented up. It makes a new object event if argument is already up.

POINT-IN-BOX-EXCLUSIVE (POINT BOX &KEY (INCLUDE-IN-DEGENERATE-DIMENSION NIL))

Check if point is contained inside a bounding box.

POINT-IN-BOX-INCLUSIVE (POINT BOX)

Check if point is contained inside or directly on a bounding box.

POINT-LINE-POSITION (POINT LINE)

Returns >0 if point is to left/above the line, 0 if on the line and <0 if to the right/below the line.

POINT-LIST-FROM-RING (RING-NODE)

Return a list of points in a ring.

POINT-SORT-FUN (POINT1 POINT2)

Order points by increasing x then y.

POLYGON-BINARY (POLYGON1 POLYGON2 TRIANGLE-TEST)

Return all triangles fulfilling triangle-test from triangulation of all edges of two polygons.

POSSIBLE-DIAGONAL-P (RING-DIAG)

Checks if ring-diag does not intersect any edge in a ring.

RECURSE-BENTLEY-OTTMANN (EVENT-QUEUE SWEEP-LINE ACC)

Recurse down event queue.

RECURSE-SHAMOS-HOEY (EVENT-QUEUE SWEEP-LINE)

Recurse down event list.

REMOVE-EAR (NODE)

Remove an ear centered on node from ring, returning new node, the removed ear and new edge list.

RIGHT-ENDPOINT (EDGE)

Return right endpoint of an edge.

RING-TO-LIST-OF-EDGES (RING)

Construct a list of edges attached to vertexes.

SANITIZE-EDGES (EDGE-LIST)

Drop zero length edges and merge all segment intersecting edges.

SPLIT-TRAPEZOID (TRAPEZOID)

Split trapezoid into two triangles. Return a cons.

TRAPEZOIDIZE-EDGES (EDGE-LIST)

Returns a list of trapezoids build from a set of edges and their bounding box.

TRAPEZOIDS-TO-TRIANGLES (TRAPEZ)

Convert list of trapezoids to list of triangles.

TRIANGLE-CENTER-POINT (TRIANGLE)

Return a central point of triangle.

VERTICAL-EDGE-P (EDGE)

Returns t if edge is horizontal.

XOR (P Q)

Exlusive or logical operation.

Undocumented

COPY-LINE-SEGMENT (LINE-SEGMENT)

FIND-INTERSECTION (EDGE-LIST)

RECURSE-SANITIZE-EDGES (EDGE-LIST ACC)

GENERIC-FUNCTION

Public

Undocumented

SETFX (NEW-VALUE OBJECT)

SETFY (NEW-VALUE OBJECT)

Private

CONSTRUCT-BOUNDING-BOX (OBJECT)

Construct a bounding box of a given object.

SLOT-ACCESSOR

Public

Undocumented

A (OBJECT)

SETFA (NEW-VALUE OBJECT)

B (OBJECT)

SETFB (NEW-VALUE OBJECT)

C (OBJECT)

SETFC (NEW-VALUE OBJECT)

EDGE-LIST (OBJECT)

END (OBJECT)

SETFEND (NEW-VALUE OBJECT)

POINT-LIST (OBJECT)

START (OBJECT)

SETFSTART (NEW-VALUE OBJECT)

X (OBJECT)

Y (OBJECT)

Private

Undocumented

DIRECTION (OBJECT)

SETFDIRECTION (NEW-VALUE OBJECT)

EAR (OBJECT)

SETFEAR (NEW-VALUE OBJECT)

EDGE (OBJECT)

SETFEDGE (NEW-VALUE OBJECT)

EDGE-TREE (OBJECT)

SETFEDGE-TREE (NEW-VALUE OBJECT)

EDGE1 (OBJECT)

SETFEDGE1 (NEW-VALUE OBJECT)

EDGE2 (OBJECT)

SETFEDGE2 (NEW-VALUE OBJECT)

NEXT-NODE (OBJECT)

SETFNEXT-NODE (NEW-VALUE OBJECT)

POINT-RING (OBJECT)

PREV-NODE (OBJECT)

SETFPREV-NODE (NEW-VALUE OBJECT)

TAINT (OBJECT)

SETFTAINT (NEW-VALUE OBJECT)

VAL (OBJECT)

SETFVAL (NEW-VALUE OBJECT)

X-MAX (OBJECT)

SETFX-MAX (NEW-VALUE OBJECT)

X-MIN (OBJECT)

SETFX-MIN (NEW-VALUE OBJECT)

Y-MAX (OBJECT)

SETFY-MAX (NEW-VALUE OBJECT)

Y-MIN (OBJECT)

SETFY-MIN (NEW-VALUE OBJECT)

CLASS

Public

LINE

A line with an equation Ax+By+C=0.

LINE-SEGMENT

A directed line segment defined by two points.

POINT

A point on a plane, with cartesian coordinates.

Undocumented

POLYGON

Private

BOUNDING-BOX

A bounding box.

EAR-RING-NODE

Ring node with ear information.

EVENT-ENDPOINT

Endpoint event for Bentley-Ottmann algorithm.

EVENT-INTERSECTION

Intersection event for Bentley-Ottmann algorithm.

POLY-RING-NODE

Double linked ring node.

SWEEP-LINE

Sweep line.

TAINT-SEGMENT

Extend line-segment with taint boolean.