The cl-geometry Reference Manual

Table of Contents

The cl-geometry Reference Manual

This is the cl-geometry Reference Manual, version 0.0.3, generated automatically by Declt version 3.0 "Montgomery Scott" on Fri Jun 26 10:14:32 2020 GMT+0.

1 Introduction

cl-geometry

This is a system for two dimensional computational geometry for Common Lisp.

Notes

The system assumes exact rational arithmetic, so no floating point coordinates are allowed. This is not checked when creating geometric objects.

The system was not heavily tested or used. Comments and/or patches welcome.

Classes

• point
• line-segment (ie. an ordered set of two points)
• line (an infinite geometric object given by equation Ax+By+C=0)
• polygon (an ordered set of n points)

Decomposition

Most functions are explained by their docstrings. The most complex and somewhat chaotic are decomposition/triangulation functions.

triangulate polygon

Returns a set of triangles obtained using ear-removal method. This works only on simple polygons (ie. nonself-intersecting), and is quadratic in the number of edges.

decompose-complex-polygon-nondisjoint polygon

Returns a set of possibly intersecting simple polygons from a complex one. This is quadratic in the number of edges at least. The only guarantee is that the union of edges of returned polygons form original polygon, in particular, this does no form of interior testing.

shamos-hoey edge-list

Takes a list of edges (line segments) and returns true if there is at least one intersection.

bentley-ottmann edge-list

Takes a list of edges and returns all intersection points.

decompose-complex-polygon-bentley-ottmann polygon

Returns a set of possibly intersecting simple polygons. This is similar to decompose-complex-polygon-nondisjoint above but should be faster.

decompose-complex-polygon-triangles polygon &key (in-test 'point-in-polygon-winding-p)

Returns a set of triangles forming the, possibly complex, polygon which fulfill the in-test, which is a function of two arguments, a center point of a given triangle and a polygon. By default winding number interior test is used. The other standard test is even-odd rule implemented by point-in-polygon-crossing-p. Using (constantly t) will return all triangles forming the polygon and its bounding box.

polygon-union polygon1 polygon2 
  &key (in-test 'point-in-polygon-winding-p) (in-test-1 nil) (in-test-2 nil)
polygon-intersection polygon1 polygon2 
  &key (in-test 'point-in-polygon-winding-p) (in-test-1 nil) (in-test-2 nil)
polygon-difference polygon1 polygon2 
  &key (in-test 'point-in-polygon-winding-p) (in-test-1 nil) (in-test-2 nil)

Returns a set of triangles which form two polygons (and their bounding box) and fulfill appropriate interior condition. If in-test-1 or in-test-2 are null, in-test is used. If both have value, in-test is ignored. Tests are function as above. The triangles returned are: for union, that fulfill either test, for intersection that fulfill both tests and difference that succeed first test but fail the second.

polygon-difference-nary polygon &rest holes &key (in-test 'point-in-polygon-winding-p)

Returns a set of triangles which succeed in-test with polygon, but fail with all holes.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 cl-geometry

Author

Jakub Higersberger <ramarren@gmail.com>

License

BSD-style

Description

Library for two dimensional geometry.

Version

0.0.3

Dependencies

• iterate
• trees

Source

cl-geometry.asd (file)

Components

• package.lisp (file)
• trivial-geometry.lisp (file)
• basic-point.lisp (file)
• bounding-box.lisp (file)
• basic-line.lisp (file)
• representations.lisp (file)
• polygon-class.lisp (file)
• basic-polygon.lisp (file)
• triangulation.lisp (file)
• decomposition.lisp (file)
• heap.lisp (file)
• bentley-ottmann.lisp (file)
• trapezoidation.lisp (file)
• polygon.lisp (file)
• polygon-binary.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 cl-geometry.asd

Location

cl-geometry.asd

Systems

cl-geometry (system)

3.1.2 cl-geometry/package.lisp

Dependency

heap.lisp (file)

Parent

cl-geometry (system)

Location

package.lisp

Packages

2d-geometry

3.1.3 cl-geometry/trivial-geometry.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

trivial-geometry.lisp

Exported Definitions

• area-circle (function)
• area-ellipse-axes (function)
• area-rectangle (function)
• area-square (function)
• area-triangle-edge-edge-angle (function)
• area-triangle-edges (function)
• area-triangle-edges-small-angles (function)
• area-triangle-vertices (function)
• circumference-circle (function)
• circumference-ellipse-axes (function)
• distance (function)
• perimeter-rectangle (function)
• perimeter-square (function)
• perimeter-triangle (function)

3.1.4 cl-geometry/basic-point.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

basic-point.lisp

Exported Definitions

• colinear-p (function)
• coords-to-points (function)
• point (class)
• point-equal-p (function)
• x (method)
• y (method)

Internal Definitions

• between-p (function)
• intersect-p (function)
• intersect-proper-p (function)
• left-on-p (function)
• left-p (function)
• make-point (function)
• point-sort-fun (function)
• xor (function)

3.1.5 cl-geometry/bounding-box.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

bounding-box.lisp

Internal Definitions

• bounding-box (class)
• bounding-boxes-intersect-p (function)
• construct-bounding-box (generic function)
• intersect-boxes (function)
• point-in-box-exclusive (function)
• point-in-box-inclusive (function)
• x-max (method)
• (setf x-max) (method)
• x-min (method)
• (setf x-min) (method)
• y-max (method)
• (setf y-max) (method)
• y-min (method)
• (setf y-min) (method)

3.1.6 cl-geometry/basic-line.lisp

Dependencies

• bounding-box.lisp (file)
• package.lisp (file)

Parent

cl-geometry (system)

Location

basic-line.lisp

Exported Definitions

• a (method)
• (setf a) (method)
• b (method)
• (setf b) (method)
• c (method)
• (setf c) (method)
• end (method)
• (setf end) (method)
• line (class)
• line-from-segment (function)
• line-segment (class)
• line-segment-length (function)
• line-segments-intersection-point (function)
• line-segments-intersection-segment (function)
• line-x-at-y (function)
• line-y-at-x (function)
• lines-equal-p (function)
• lines-intersection-point (function)
• lines-parralel-p (function)
• start (method)
• (setf start) (method)

Internal Definitions

• construct-bounding-box (method)
• copy-line-segment (function)
• make-line-segment (function)
• point-line-position (function)

3.1.7 cl-geometry/representations.lisp

Dependencies

• package.lisp (file)
• basic-point.lisp (file)
• basic-line.lisp (file)

Parent

cl-geometry (system)

Location

representations.lisp

Exported Definitions

• x (method)
• y (method)

Internal Definitions

• collect-ring-nodes (function)
• double-linked-ring-from-point-list (function)
• edge-list-from-point-list (function)
• next-node (method)
• (setf next-node) (method)
• point-list-from-ring (function)
• poly-ring-node (class)
• prev-node (method)
• (setf prev-node) (method)
• ring-to-list-of-edges (function)
• val (method)
• (setf val) (method)

3.1.8 cl-geometry/polygon-class.lisp

Dependencies

• package.lisp (file)
• representations.lisp (file)

Parent

cl-geometry (system)

Location

polygon-class.lisp

Exported Definitions

• edge-list (method)
• make-polygon-from-coords (function)
• make-polygon-from-point-list (function)
• make-polygon-from-point-ring (function)
• point-list (method)
• polygon (class)

Internal Definitions

point-ring (method)

3.1.9 cl-geometry/basic-polygon.lisp

Dependencies

• basic-point.lisp (file)
• polygon-class.lisp (file)
• basic-line.lisp (file)

Parent

cl-geometry (system)

Location

basic-polygon.lisp

Exported Definitions

• area-simple-polygon (function)
• frustrated-polygon-p (function)
• point-in-polygon-crossing-p (function)
• point-in-polygon-winding-number (function)
• point-in-polygon-winding-p (function)
• polygon-orientation (function)
• simple-polygon-p (function)

Internal Definitions

• construct-bounding-box (method)
• filter-ray-intersection (function)
• notany-symmetric-test (function)

3.1.10 cl-geometry/triangulation.lisp

Dependencies

• basic-line.lisp (file)
• trivial-geometry.lisp (file)
• basic-polygon.lisp (file)
• representations.lisp (file)
• polygon-class.lisp (file)

Parent

cl-geometry (system)

Location

triangulation.lisp

Exported Definitions

triangulate (function)

Internal Definitions

• diagonal-p (function)
• ear (method)
• (setf ear) (method)
• ear-init (function)
• ear-ring-node (class)
• in-cone-p (function)
• possible-diagonal-p (function)
• remove-ear (function)

3.1.11 cl-geometry/decomposition.lisp

Dependencies

• basic-line.lisp (file)
• basic-polygon.lisp (file)
• triangulation.lisp (file)
• representations.lisp (file)
• polygon-class.lisp (file)

Parent

cl-geometry (system)

Location

decomposition.lisp

Exported Definitions

decompose-complex-polygon-nondisjoint (function)

Internal Definitions

find-intersection (function)

3.1.12 cl-geometry/heap.lisp

Parent

cl-geometry (system)

Location

heap.lisp

Packages

ramarren-utils

Exported Definitions

• heap-empty (function)
• heap-peek (function)
• heapify (function)
• nheap-extract (function)
• nheap-insert (function)

Internal Definitions

• heap-lchild (function)
• heap-parent (function)
• heap-rchild (function)

3.1.13 cl-geometry/bentley-ottmann.lisp

Dependencies

• heap.lisp (file)
• representations.lisp (file)
• polygon-class.lisp (file)

Parent

cl-geometry (system)

Location

bentley-ottmann.lisp

Exported Definitions

• bentley-ottmann (function)
• shamos-hoey (function)
• (setf x) (generic function)
• (setf x) (method)
• (setf y) (generic function)
• (setf y) (method)

Internal Definitions

• add-if-intersection (function)
• check-node-integrity (function)
• check-tree-integrity (function)
• create-initial-event-list (function)
• delete-edge (function)
• direction (method)
• (setf direction) (method)
• edge (method)
• (setf edge) (method)
• edge-tree (method)
• (setf edge-tree) (method)
• edge1 (method)
• (setf edge1) (method)
• edge2 (method)
• (setf edge2) (method)
• event-endpoint (class)
• event-intersection (class)
• insert-edge (function)
• left-endpoint (function)
• move-sweep-line (function)
• order-line-segments-at-point (function)
• recurse-bentley-ottmann (function)
• recurse-shamos-hoey (function)
• right-endpoint (function)
• sweep-line (class)
• taint (method)
• (setf taint) (method)
• taint-segment (class)

3.1.14 cl-geometry/trapezoidation.lisp

Dependencies

• bentley-ottmann.lisp (file)
• polygon-class.lisp (file)

Parent

cl-geometry (system)

Location

trapezoidation.lisp

Internal Definitions

• collapse-trapezoid (function)
• orient-edge-right (function)
• split-trapezoid (function)
• trapezoidize-edges (function)
• vertical-edge-p (function)

3.1.15 cl-geometry/polygon.lisp

Dependencies

• basic-polygon.lisp (file)
• polygon-class.lisp (file)
• triangulation.lisp (file)
• decomposition.lisp (file)
• trapezoidation.lisp (file)

Parent

cl-geometry (system)

Location

polygon.lisp

Exported Definitions

• decompose-complex-polygon-bentley-ottmann (function)
• decompose-complex-polygon-triangles (function)
• simple-polygon-sh-p (function)

Internal Definitions

• trapezoids-to-triangles (function)
• triangle-center-point (function)

3.1.16 cl-geometry/polygon-binary.lisp

Dependencies

• polygon.lisp (file)
• polygon-class.lisp (file)

Parent

cl-geometry (system)

Location

polygon-binary.lisp

Exported Definitions

• polygon-difference (function)
• polygon-difference-nary (function)
• polygon-intersection (function)
• polygon-union (function)

Internal Definitions

• merge-line-segment-into (function)
• polygon-binary (function)
• recurse-sanitize-edges (function)
• sanitize-edges (function)

4 Packages

Packages are listed by definition order.

4.1 2d-geometry

Source

package.lisp (file)

Nicknames

• cl-geometry
• geometry

Use List

• ramarren-utils
• iterate
• common-lisp

Exported Definitions

• a (generic function)
• a (method)
• (setf a) (method)
• (setf a) (generic function)
• area-circle (function)
• area-ellipse-axes (function)
• area-rectangle (function)
• area-simple-polygon (function)
• area-square (function)
• area-triangle-edge-edge-angle (function)
• area-triangle-edges (function)
• area-triangle-edges-small-angles (function)
• area-triangle-vertices (function)
• b (generic function)
• b (method)
• (setf b) (method)
• (setf b) (generic function)
• bentley-ottmann (function)
• c (generic function)
• c (method)
• (setf c) (method)
• (setf c) (generic function)
• circumference-circle (function)
• circumference-ellipse-axes (function)
• colinear-p (function)
• coords-to-points (function)
• decompose-complex-polygon-bentley-ottmann (function)
• decompose-complex-polygon-nondisjoint (function)
• decompose-complex-polygon-triangles (function)
• distance (function)
• edge-list (generic function)
• edge-list (method)
• end (generic function)
• end (method)
• (setf end) (method)
• (setf end) (generic function)
• frustrated-polygon-p (function)
• line (class)
• line-from-segment (function)
• line-segment (class)
• line-segment-length (function)
• line-segments-intersection-point (function)
• line-segments-intersection-segment (function)
• line-x-at-y (function)
• line-y-at-x (function)
• lines-equal-p (function)
• lines-intersection-point (function)
• lines-parralel-p (function)
• make-polygon-from-coords (function)
• make-polygon-from-point-list (function)
• make-polygon-from-point-ring (function)
• perimeter-rectangle (function)
• perimeter-square (function)
• perimeter-triangle (function)
• point (class)
• point-equal-p (function)
• point-in-polygon-crossing-p (function)
• point-in-polygon-winding-number (function)
• point-in-polygon-winding-p (function)
• point-list (generic function)
• point-list (method)
• polygon (class)
• polygon-difference (function)
• polygon-difference-nary (function)
• polygon-intersection (function)
• polygon-orientation (function)
• polygon-union (function)
• shamos-hoey (function)
• simple-polygon-p (function)
• simple-polygon-sh-p (function)
• start (generic function)
• start (method)
• (setf start) (method)
• (setf start) (generic function)
• triangulate (function)
• x (generic function)
• x (method)
• x (method)
• (setf x) (generic function)
• (setf x) (method)
• y (generic function)
• y (method)
• y (method)
• (setf y) (generic function)
• (setf y) (method)

Internal Definitions

• add-if-intersection (function)
• between-p (function)
• bounding-box (class)
• bounding-boxes-intersect-p (function)
• check-node-integrity (function)
• check-tree-integrity (function)
• collapse-trapezoid (function)
• collect-ring-nodes (function)
• construct-bounding-box (generic function)
• construct-bounding-box (method)
• construct-bounding-box (method)
• copy-line-segment (function)
• create-initial-event-list (function)
• delete-edge (function)
• diagonal-p (function)
• direction (generic function)
• direction (method)
• (setf direction) (method)
• (setf direction) (generic function)
• double-linked-ring-from-point-list (function)
• ear (generic function)
• ear (method)
• (setf ear) (method)
• (setf ear) (generic function)
• ear-init (function)
• ear-ring-node (class)
• edge (generic function)
• edge (method)
• (setf edge) (method)
• (setf edge) (generic function)
• edge-list-from-point-list (function)
• edge-tree (generic function)
• edge-tree (method)
• (setf edge-tree) (method)
• (setf edge-tree) (generic function)
• edge1 (generic function)
• edge1 (method)
• (setf edge1) (method)
• (setf edge1) (generic function)
• edge2 (generic function)
• edge2 (method)
• (setf edge2) (method)
• (setf edge2) (generic function)
• event-endpoint (class)
• event-intersection (class)
• filter-ray-intersection (function)
• find-intersection (function)
• in-cone-p (function)
• insert-edge (function)
• intersect-boxes (function)
• intersect-p (function)
• intersect-proper-p (function)
• left-endpoint (function)
• left-on-p (function)
• left-p (function)
• make-line-segment (function)
• make-point (function)
• merge-line-segment-into (function)
• move-sweep-line (function)
• next-node (generic function)
• next-node (method)
• (setf next-node) (method)
• (setf next-node) (generic function)
• notany-symmetric-test (function)
• order-line-segments-at-point (function)
• orient-edge-right (function)
• point-in-box-exclusive (function)
• point-in-box-inclusive (function)
• point-line-position (function)
• point-list-from-ring (function)
• point-ring (generic function)
• point-ring (method)
• point-sort-fun (function)
• poly-ring-node (class)
• polygon-binary (function)
• possible-diagonal-p (function)
• prev-node (generic function)
• prev-node (method)
• (setf prev-node) (method)
• (setf prev-node) (generic function)
• recurse-bentley-ottmann (function)
• recurse-sanitize-edges (function)
• recurse-shamos-hoey (function)
• remove-ear (function)
• right-endpoint (function)
• ring-to-list-of-edges (function)
• sanitize-edges (function)
• split-trapezoid (function)
• sweep-line (class)
• taint (generic function)
• taint (method)
• (setf taint) (method)
• (setf taint) (generic function)
• taint-segment (class)
• trapezoidize-edges (function)
• trapezoids-to-triangles (function)
• triangle-center-point (function)
• val (generic function)
• val (method)
• (setf val) (method)
• (setf val) (generic function)
• vertical-edge-p (function)
• x-max (generic function)
• x-max (method)
• (setf x-max) (method)
• (setf x-max) (generic function)
• x-min (generic function)
• x-min (method)
• (setf x-min) (method)
• (setf x-min) (generic function)
• xor (function)
• y-max (generic function)
• y-max (method)
• (setf y-max) (method)
• (setf y-max) (generic function)
• y-min (generic function)
• y-min (method)
• (setf y-min) (method)
• (setf y-min) (generic function)

4.2 ramarren-utils

Source

heap.lisp (file)

Use List

common-lisp

Used By List

2d-geometry

Exported Definitions

• heap-empty (function)
• heap-peek (function)
• heapify (function)
• nheap-extract (function)
• nheap-insert (function)

Internal Definitions

• heap-lchild (function)
• heap-parent (function)
• heap-rchild (function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: area-circle R

Area of a circle.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-ellipse-axes A B

Area of an ellipse given semimajor and semiminor axes.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-rectangle A B

Area of a rectangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-simple-polygon POLYGON

Calculate an area of a simple polygon.

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: area-square A

Area of a square given length of a side.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-triangle-edge-edge-angle A B ALPHA

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: 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.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-triangle-edges-small-angles A B C

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-triangle-vertices XA YA XB YB XC YC

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: bentley-ottmann EDGE-LIST

Return a list of intersection points (events).

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: circumference-circle R

Circumference of a circle.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: circumference-ellipse-axes A B

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: colinear-p A B C

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: coords-to-points &rest COORD-LIST

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: decompose-complex-polygon-bentley-ottmann POLYGON

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

Package

2d-geometry

Source

polygon.lisp (file)

Function: decompose-complex-polygon-nondisjoint POLYGON

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

Package

2d-geometry

Source

decomposition.lisp (file)

Function: decompose-complex-polygon-triangles POLYGON &key IN-TEST

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.

Package

2d-geometry

Source

polygon.lisp (file)

Function: distance X1 Y1 X2 Y2

Distance between two points on a plane.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: frustrated-polygon-p POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: heap-empty WHERE

Package

ramarren-utils

Source

heap.lisp (file)

Function: heap-peek WHERE

Package

ramarren-utils

Source

heap.lisp (file)

Function: heapify WHAT COMPAR

Turns list into a heap

Package

ramarren-utils

Source

heap.lisp (file)

Function: line-from-segment LINE-SEGMENT

Calculate line from line segment.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-segment-length LINE-SEGMENT

Calculate length of a segment.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-segments-intersection-point LINE-SEGMENT1 LINE-SEGMENT2 &key EXCLUDE-ENDPOINTS

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-segments-intersection-segment LINE-SEGMENT1 LINE-SEGMENT2

Find an intersection of two colinear line segments.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-x-at-y LINE Y

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-y-at-x LINE X

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-equal-p LINE1 LINE2

Check if two lines are equal.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-intersection-point LINE1 LINE2

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-parralel-p LINE1 LINE2

Check if two lines are parrallel.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: make-polygon-from-coords &rest COORD-LIST

Package

2d-geometry

Source

polygon-class.lisp (file)

Function: make-polygon-from-point-list POINT-LIST

Package

2d-geometry

Source

polygon-class.lisp (file)

Function: make-polygon-from-point-ring POINT-RING

Package

2d-geometry

Source

polygon-class.lisp (file)

Function: nheap-extract WHERE

Package

ramarren-utils

Source

heap.lisp (file)

Function: nheap-insert WHAT WHERE

Package

ramarren-utils

Source

heap.lisp (file)

Function: perimeter-rectangle A B

Perimeter of a rectangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: perimeter-square A

Perimeter of a square given length of a side.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: perimeter-triangle A B C

Perimeter of a triangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: point-equal-p POINT1 POINT2

Checks if two points are geometrically equal.

Package

2d-geometry

Source

basic-point.lisp (file)

Function: point-in-polygon-crossing-p POINT POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: point-in-polygon-winding-number POINT POLYGON

Calculate winding number of a point.

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: point-in-polygon-winding-p POINT POLYGON

Check if point is in polygon using winding number rule.

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: polygon-difference POLYGON1 POLYGON2 &key IN-TEST IN-TEST-1 IN-TEST-2

Return triangles of polygon1 minus polygon2.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: polygon-difference-nary POLYGON &rest HOLES &key IN-TEST

Return triangles of polygon with some holes.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: polygon-intersection POLYGON1 POLYGON2 &key IN-TEST IN-TEST-1 IN-TEST-2

Return triangles of an intersection of two polygons.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: polygon-orientation POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: polygon-union POLYGON1 POLYGON2 &key IN-TEST IN-TEST-1 IN-TEST-2

Return triangles of an union of two polygons.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: shamos-hoey EDGE-LIST

Returns t if there is at least one intersection.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: 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.

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: simple-polygon-sh-p POLYGON

Check if polygon is simple using Shamos-Hoey algorithm.

Package

2d-geometry

Source

polygon.lisp (file)

Function: triangulate POLYGON

Triangulate polygon. Returns list of triangles.

Package

2d-geometry

Source

triangulation.lisp (file)

5.1.2 Generic functions

Generic Function: a OBJECT

Generic Function: (setf a) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: a (LINE line)

automatically generated reader method

Source

basic-line.lisp (file)

Method: (setf a) NEW-VALUE (LINE line)

automatically generated writer method

Source

basic-line.lisp (file)

Generic Function: b OBJECT

Generic Function: (setf b) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: b (LINE line)

automatically generated reader method

Source

basic-line.lisp (file)

Method: (setf b) NEW-VALUE (LINE line)

automatically generated writer method

Source

basic-line.lisp (file)

Generic Function: c OBJECT

Generic Function: (setf c) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: c (LINE line)

automatically generated reader method

Source

basic-line.lisp (file)

Method: (setf c) NEW-VALUE (LINE line)

automatically generated writer method

Source

basic-line.lisp (file)

Generic Function: edge-list OBJECT

Package

2d-geometry

Methods

Method: edge-list (POLYGON polygon)

automatically generated reader method

Source

polygon-class.lisp (file)

Generic Function: end OBJECT

Generic Function: (setf end) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: end (LINE-SEGMENT line-segment)

automatically generated reader method

Source

basic-line.lisp (file)

Method: (setf end) NEW-VALUE (LINE-SEGMENT line-segment)

automatically generated writer method

Source

basic-line.lisp (file)

Generic Function: point-list OBJECT

Package

2d-geometry

Methods

Method: point-list (POLYGON polygon)

automatically generated reader method

Source

polygon-class.lisp (file)

Generic Function: start OBJECT

Generic Function: (setf start) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: start (LINE-SEGMENT line-segment)

automatically generated reader method

Source

basic-line.lisp (file)

Method: (setf start) NEW-VALUE (LINE-SEGMENT line-segment)

automatically generated writer method

Source

basic-line.lisp (file)

Generic Function: x OBJECT

Package

2d-geometry

Writer

(setf x) (generic function)

Methods

Method: x (OBJECT poly-ring-node)

Source

representations.lisp (file)

Method: x (POINT point)

automatically generated reader method

Source

basic-point.lisp (file)

Generic Function: (setf x) NEW-VALUE OBJECT

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Reader

x (generic function)

Methods

Method: (setf x) NEW-VALUE (OBJECT sweep-line)

Generic Function: y OBJECT

Package

2d-geometry

Writer

(setf y) (generic function)

Methods

Method: y (OBJECT poly-ring-node)

Source

representations.lisp (file)

Method: y (POINT point)

automatically generated reader method

Source

basic-point.lisp (file)

Generic Function: (setf y) NEW-VALUE OBJECT

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Reader

y (generic function)

Methods

Method: (setf y) NEW-VALUE (OBJECT sweep-line)

5.1.3 Classes

Class: line ()

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

Package

2d-geometry

Source

basic-line.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• c (method)
• c (method)
• b (method)
• b (method)
• a (method)
• a (method)

Direct slots

Slot: a

Initargs

:a

Readers

a (generic function)

Writers

(setf a) (generic function)

Slot: b

Initargs

:b

Readers

b (generic function)

Writers

(setf b) (generic function)

Slot: c

Initargs

:c

Initform

0

Readers

c (generic function)

Writers

(setf c) (generic function)

Class: line-segment ()

A directed line segment defined by two points.

Package

2d-geometry

Source

basic-line.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

taint-segment (class)

Direct methods

• construct-bounding-box (method)
• print-object (method)
• end (method)
• end (method)
• start (method)
• start (method)

Direct slots

Slot: start

Initargs

:start

Initform

(make-instance (quote 2d-geometry:point))

Readers

start (generic function)

Writers

(setf start) (generic function)

Slot: end

Initargs

:end

Initform

(make-instance (quote 2d-geometry:point))

Readers

end (generic function)

Writers

(setf end) (generic function)

Class: point ()

A point on a plane, with cartesian coordinates.

Package

2d-geometry

Source

basic-point.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• event-endpoint (class)
• event-intersection (class)
• sweep-line (class)

Direct methods

• print-object (method)
• y (method)
• x (method)

Direct slots

Slot: x

Initargs

:x

Initform

0

Readers

x (generic function)

Slot: y

Initargs

:y

Initform

0

Readers

y (generic function)

Class: polygon ()

Package

2d-geometry

Source

polygon-class.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• construct-bounding-box (method)
• print-object (method)
• point-ring (method)
• edge-list (method)
• point-list (method)

Direct slots

Slot: point-list

Initargs

:point-list

Readers

point-list (generic function)

Slot: edge-list

Initargs

:edge-list

Readers

edge-list (generic function)

Slot: point-ring

Initargs

:point-ring

Readers

point-ring (generic function)

5.2 Internal definitions

5.2.1 Functions

Function: add-if-intersection EDGE1 EDGE2 EVENT-QUEUE CURRENT-POINT

Add intersection to event queue if edge1 intersects edge2.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: between-p A B C

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: bounding-boxes-intersect-p BOX1 BOX2

Check if two bounding boxes intersect.

Package

2d-geometry

Source

bounding-box.lisp (file)

Function: check-node-integrity NODE SWEEP-LINE

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

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: check-tree-integrity SWEEP-LINE

Verify sweep line tree integrity.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: collapse-trapezoid TRAPEZOID

Reduce degenerate trapezoids to triangles.

Package

2d-geometry

Source

trapezoidation.lisp (file)

Function: collect-ring-nodes RING

Construct a list of all nodes in a ring.

Package

2d-geometry

Source

representations.lisp (file)

Function: copy-line-segment LINE-SEGMENT

Package

2d-geometry

Source

basic-line.lisp (file)

Function: create-initial-event-list EDGE-LIST

Create initial list of endpoint events.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: delete-edge EDGE SWEEP-LINE

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

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: diagonal-p RING-NODE-A RING-NODE-B

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

Package

2d-geometry

Source

triangulation.lisp (file)

Function: double-linked-ring-from-point-list POINT-LIST &optional RING-TYPE

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

Package

2d-geometry

Source

representations.lisp (file)

Function: ear-init POINT-LIST

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

Package

2d-geometry

Source

triangulation.lisp (file)

Function: edge-list-from-point-list POINT-LIST &optional EDGE-TYPE

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

Package

2d-geometry

Source

representations.lisp (file)

Function: filter-ray-intersection POINT EDGE

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: find-intersection EDGE-LIST

Package

2d-geometry

Source

decomposition.lisp (file)

Function: heap-lchild I

Package

ramarren-utils

Source

heap.lisp (file)

Function: heap-parent I

Package

ramarren-utils

Source

heap.lisp (file)

Function: heap-rchild I

Package

ramarren-utils

Source

heap.lisp (file)

Function: in-cone-p RING-NODE B

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

Package

2d-geometry

Source

triangulation.lisp (file)

Function: insert-edge EDGE SWEEP-LINE

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

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: intersect-boxes BOX1 BOX2

Return bounding box common to both boxes.

Package

2d-geometry

Source

bounding-box.lisp (file)

Function: intersect-p A B C D

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: intersect-proper-p A B C D

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: left-endpoint EDGE

Return left endpoint of an edge.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: left-on-p A B C

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: left-p A B C

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

Package

2d-geometry

Source

basic-point.lisp (file)

Function: make-line-segment START END &optional LINE-SEGMENT-TYPE

Create a new line segment.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: make-point X Y &optional POINT-TYPE

Create a new point like object.

Package

2d-geometry

Source

basic-point.lisp (file)

Function: 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.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: move-sweep-line SWEEP-LINE X Y

Move sweep line to new location.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: notany-symmetric-test TESTFUN LIST

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: order-line-segments-at-point LV RV POINT

Return t if lv is above rv at point.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: orient-edge-right EDGE

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

Package

2d-geometry

Source

trapezoidation.lisp (file)

Function: point-in-box-exclusive POINT BOX &key INCLUDE-IN-DEGENERATE-DIMENSION

Check if point is contained inside a bounding box.

Package

2d-geometry

Source

bounding-box.lisp (file)

Function: point-in-box-inclusive POINT BOX

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

Package

2d-geometry

Source

bounding-box.lisp (file)

Function: 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.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: point-list-from-ring RING-NODE

Return a list of points in a ring.

Package

2d-geometry

Source

representations.lisp (file)

Function: point-sort-fun POINT1 POINT2

Order points by increasing x then y.

Package

2d-geometry

Source

basic-point.lisp (file)

Function: polygon-binary POLYGON1 POLYGON2 TRIANGLE-TEST

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

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: possible-diagonal-p RING-DIAG

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

Package

2d-geometry

Source

triangulation.lisp (file)

Function: recurse-bentley-ottmann EVENT-QUEUE SWEEP-LINE ACC

Recurse down event queue.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: recurse-sanitize-edges EDGE-LIST ACC

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: recurse-shamos-hoey EVENT-QUEUE SWEEP-LINE

Recurse down event list.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: remove-ear NODE

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

Package

2d-geometry

Source

triangulation.lisp (file)

Function: right-endpoint EDGE

Return right endpoint of an edge.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: ring-to-list-of-edges RING

Construct a list of edges attached to vertexes.

Package

2d-geometry

Source

representations.lisp (file)

Function: sanitize-edges EDGE-LIST

Drop zero length edges and merge all segment intersecting edges.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: split-trapezoid TRAPEZOID

Split trapezoid into two triangles. Return a cons.

Package

2d-geometry

Source

trapezoidation.lisp (file)

Function: trapezoidize-edges EDGE-LIST

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

Package

2d-geometry

Source

trapezoidation.lisp (file)

Function: trapezoids-to-triangles TRAPEZ

Convert list of trapezoids to list of triangles.

Package

2d-geometry

Source

polygon.lisp (file)

Function: triangle-center-point TRIANGLE

Return a central point of triangle.

Package

2d-geometry

Source

polygon.lisp (file)

Function: vertical-edge-p EDGE

Returns t if edge is horizontal.

Package

2d-geometry

Source

trapezoidation.lisp (file)

Function: xor P Q

Exlusive or logical operation.

Package

2d-geometry

Source

basic-point.lisp (file)

5.2.2 Generic functions

Generic Function: construct-bounding-box OBJECT

Construct a bounding box of a given object.

Package

2d-geometry

Source

bounding-box.lisp (file)

Methods

Method: construct-bounding-box (OBJECT polygon)

Source

basic-polygon.lisp (file)

Method: construct-bounding-box (OBJECT line-segment)

Source

basic-line.lisp (file)

Generic Function: direction OBJECT

Generic Function: (setf direction) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: direction (EVENT-ENDPOINT event-endpoint)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf direction) NEW-VALUE (EVENT-ENDPOINT event-endpoint)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: ear OBJECT

Generic Function: (setf ear) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: ear (EAR-RING-NODE ear-ring-node)

automatically generated reader method

Source

triangulation.lisp (file)

Method: (setf ear) NEW-VALUE (EAR-RING-NODE ear-ring-node)

automatically generated writer method

Source

triangulation.lisp (file)

Generic Function: edge OBJECT

Generic Function: (setf edge) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: edge (EVENT-ENDPOINT event-endpoint)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf edge) NEW-VALUE (EVENT-ENDPOINT event-endpoint)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: edge-tree OBJECT

Generic Function: (setf edge-tree) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: edge-tree (SWEEP-LINE sweep-line)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf edge-tree) NEW-VALUE (SWEEP-LINE sweep-line)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: edge1 OBJECT

Generic Function: (setf edge1) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: edge1 (EVENT-INTERSECTION event-intersection)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf edge1) NEW-VALUE (EVENT-INTERSECTION event-intersection)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: edge2 OBJECT

Generic Function: (setf edge2) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: edge2 (EVENT-INTERSECTION event-intersection)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf edge2) NEW-VALUE (EVENT-INTERSECTION event-intersection)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: next-node OBJECT

Generic Function: (setf next-node) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: next-node (POLY-RING-NODE poly-ring-node)

automatically generated reader method

Source

representations.lisp (file)

Method: (setf next-node) NEW-VALUE (POLY-RING-NODE poly-ring-node)

automatically generated writer method

Source

representations.lisp (file)

Generic Function: point-ring OBJECT

Package

2d-geometry

Methods

Method: point-ring (POLYGON polygon)

automatically generated reader method

Source

polygon-class.lisp (file)

Generic Function: prev-node OBJECT

Generic Function: (setf prev-node) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: prev-node (POLY-RING-NODE poly-ring-node)

automatically generated reader method

Source

representations.lisp (file)

Method: (setf prev-node) NEW-VALUE (POLY-RING-NODE poly-ring-node)

automatically generated writer method

Source

representations.lisp (file)

Generic Function: taint OBJECT

Generic Function: (setf taint) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: taint (TAINT-SEGMENT taint-segment)

automatically generated reader method

Source

bentley-ottmann.lisp (file)

Method: (setf taint) NEW-VALUE (TAINT-SEGMENT taint-segment)

automatically generated writer method

Source

bentley-ottmann.lisp (file)

Generic Function: val OBJECT

Generic Function: (setf val) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: val (POLY-RING-NODE poly-ring-node)

automatically generated reader method

Source

representations.lisp (file)

Method: (setf val) NEW-VALUE (POLY-RING-NODE poly-ring-node)

automatically generated writer method

Source

representations.lisp (file)

Generic Function: x-max OBJECT

Generic Function: (setf x-max) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: x-max (BOUNDING-BOX bounding-box)

automatically generated reader method

Source

bounding-box.lisp (file)

Method: (setf x-max) NEW-VALUE (BOUNDING-BOX bounding-box)

automatically generated writer method

Source

bounding-box.lisp (file)

Generic Function: x-min OBJECT

Generic Function: (setf x-min) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: x-min (BOUNDING-BOX bounding-box)

automatically generated reader method

Source

bounding-box.lisp (file)

Method: (setf x-min) NEW-VALUE (BOUNDING-BOX bounding-box)

automatically generated writer method

Source

bounding-box.lisp (file)

Generic Function: y-max OBJECT

Generic Function: (setf y-max) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: y-max (BOUNDING-BOX bounding-box)

automatically generated reader method

Source

bounding-box.lisp (file)

Method: (setf y-max) NEW-VALUE (BOUNDING-BOX bounding-box)

automatically generated writer method

Source

bounding-box.lisp (file)

Generic Function: y-min OBJECT

Generic Function: (setf y-min) NEW-VALUE OBJECT

Package

2d-geometry

Methods

Method: y-min (BOUNDING-BOX bounding-box)

automatically generated reader method

Source

bounding-box.lisp (file)

Method: (setf y-min) NEW-VALUE (BOUNDING-BOX bounding-box)

automatically generated writer method

Source

bounding-box.lisp (file)

5.2.3 Classes

Class: bounding-box ()

A bounding box.

Package

2d-geometry

Source

bounding-box.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• y-max (method)
• y-max (method)
• y-min (method)
• y-min (method)
• x-max (method)
• x-max (method)
• x-min (method)
• x-min (method)

Direct slots

Slot: x-min

Initargs

:x-min

Readers

x-min (generic function)

Writers

(setf x-min) (generic function)

Slot: x-max

Initargs

:x-max

Readers

x-max (generic function)

Writers

(setf x-max) (generic function)

Slot: y-min

Initargs

:y-min

Readers

y-min (generic function)

Writers

(setf y-min) (generic function)

Slot: y-max

Initargs

:y-max

Readers

y-max (generic function)

Writers

(setf y-max) (generic function)

Class: ear-ring-node ()

Ring node with ear information.

Package

2d-geometry

Source

triangulation.lisp (file)

Direct superclasses

poly-ring-node (class)

Direct methods

• ear (method)
• ear (method)

Direct slots

Slot: ear

Initargs

:ear

Readers

ear (generic function)

Writers

(setf ear) (generic function)

Class: event-endpoint ()

Endpoint event for Bentley-Ottmann algorithm.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Direct superclasses

point (class)

Direct methods

• direction (method)
• direction (method)
• edge (method)
• edge (method)

Direct slots

Slot: edge

Initargs

:edge

Readers

edge (generic function)

Writers

(setf edge) (generic function)

Slot: direction

Initargs

:direction

Readers

direction (generic function)

Writers

(setf direction) (generic function)

Class: event-intersection ()

Intersection event for Bentley-Ottmann algorithm.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Direct superclasses

point (class)

Direct methods

• edge2 (method)
• edge2 (method)
• edge1 (method)
• edge1 (method)

Direct slots

Slot: edge1

Initargs

:edge1

Readers

edge1 (generic function)

Writers

(setf edge1) (generic function)

Slot: edge2

Initargs

:edge2

Readers

edge2 (generic function)

Writers

(setf edge2) (generic function)

Class: poly-ring-node ()

Double linked ring node.

Package

2d-geometry

Source

representations.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

ear-ring-node (class)

Direct methods

• y (method)
• x (method)
• print-object (method)
• prev-node (method)
• prev-node (method)
• next-node (method)
• next-node (method)
• val (method)
• val (method)

Direct slots

Slot: val

Initargs

:val

Readers

val (generic function)

Writers

(setf val) (generic function)

Slot: next

Initargs

:next

Readers

next-node (generic function)

Writers

(setf next-node) (generic function)

Slot: prev

Initargs

:prev

Readers

prev-node (generic function)

Writers

(setf prev-node) (generic function)

Class: sweep-line ()

Sweep line.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Direct superclasses

point (class)

Direct methods

• initialize-instance (method)
• (setf y) (method)
• (setf x) (method)
• edge-tree (method)
• edge-tree (method)

Direct slots

Slot: edge-tree

Readers

edge-tree (generic function)

Writers

(setf edge-tree) (generic function)

Class: taint-segment ()

Extend line-segment with taint boolean.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Direct superclasses

line-segment (class)

Direct methods

• taint (method)
• taint (method)

Direct slots

Slot: taint

Readers

taint (generic function)

Writers

(setf taint) (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions