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 Tue Dec 22 12:20:38 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
-
- Source
cl-geometry.asd (file)
- Components
-
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
-
3.1.4 cl-geometry/basic-point.lisp
- Dependency
package.lisp (file)
- Parent
cl-geometry (system)
- Location
basic-point.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.5 cl-geometry/bounding-box.lisp
- Dependency
package.lisp (file)
- Parent
cl-geometry (system)
- Location
bounding-box.lisp
- Internal Definitions
-
3.1.6 cl-geometry/basic-line.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
basic-line.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.7 cl-geometry/representations.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
representations.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.8 cl-geometry/polygon-class.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
polygon-class.lisp
- Exported Definitions
-
- Internal Definitions
point-ring (method)
3.1.9 cl-geometry/basic-polygon.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
basic-polygon.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.10 cl-geometry/triangulation.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
triangulation.lisp
- Exported Definitions
triangulate (function)
- Internal Definitions
-
3.1.11 cl-geometry/decomposition.lisp
- Dependencies
-
- 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
-
- Internal Definitions
-
3.1.13 cl-geometry/bentley-ottmann.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
bentley-ottmann.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.14 cl-geometry/trapezoidation.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
trapezoidation.lisp
- Internal Definitions
-
3.1.15 cl-geometry/polygon.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
polygon.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.16 cl-geometry/polygon-binary.lisp
- Dependencies
-
- Parent
cl-geometry (system)
- Location
polygon-binary.lisp
- Exported Definitions
-
- Internal Definitions
-
4 Packages
Packages are listed by definition order.
4.1 2d-geometry
- Source
package.lisp (file)
- Nicknames
-
- Use List
-
- Exported Definitions
-
- Internal Definitions
-
4.2 ramarren-utils
- Source
heap.lisp (file)
- Use List
common-lisp
- Used By List
2d-geometry
- Exported Definitions
-
- Internal Definitions
-
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)
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
| Index Entry | | Section |
|
C | | |
| cl-geometry.asd: | | The cl-geometry․asd file |
| cl-geometry/basic-line.lisp: | | The cl-geometry/basic-line․lisp file |
| cl-geometry/basic-point.lisp: | | The cl-geometry/basic-point․lisp file |
| cl-geometry/basic-polygon.lisp: | | The cl-geometry/basic-polygon․lisp file |
| cl-geometry/bentley-ottmann.lisp: | | The cl-geometry/bentley-ottmann․lisp file |
| cl-geometry/bounding-box.lisp: | | The cl-geometry/bounding-box․lisp file |
| cl-geometry/decomposition.lisp: | | The cl-geometry/decomposition․lisp file |
| cl-geometry/heap.lisp: | | The cl-geometry/heap․lisp file |
| cl-geometry/package.lisp: | | The cl-geometry/package․lisp file |
| cl-geometry/polygon-binary.lisp: | | The cl-geometry/polygon-binary․lisp file |
| cl-geometry/polygon-class.lisp: | | The cl-geometry/polygon-class․lisp file |
| cl-geometry/polygon.lisp: | | The cl-geometry/polygon․lisp file |
| cl-geometry/representations.lisp: | | The cl-geometry/representations․lisp file |
| cl-geometry/trapezoidation.lisp: | | The cl-geometry/trapezoidation․lisp file |
| cl-geometry/triangulation.lisp: | | The cl-geometry/triangulation․lisp file |
| cl-geometry/trivial-geometry.lisp: | | The cl-geometry/trivial-geometry․lisp file |
|
F | | |
| File, Lisp, cl-geometry.asd: | | The cl-geometry․asd file |
| File, Lisp, cl-geometry/basic-line.lisp: | | The cl-geometry/basic-line․lisp file |
| File, Lisp, cl-geometry/basic-point.lisp: | | The cl-geometry/basic-point․lisp file |
| File, Lisp, cl-geometry/basic-polygon.lisp: | | The cl-geometry/basic-polygon․lisp file |
| File, Lisp, cl-geometry/bentley-ottmann.lisp: | | The cl-geometry/bentley-ottmann․lisp file |
| File, Lisp, cl-geometry/bounding-box.lisp: | | The cl-geometry/bounding-box․lisp file |
| File, Lisp, cl-geometry/decomposition.lisp: | | The cl-geometry/decomposition․lisp file |
| File, Lisp, cl-geometry/heap.lisp: | | The cl-geometry/heap․lisp file |
| File, Lisp, cl-geometry/package.lisp: | | The cl-geometry/package․lisp file |
| File, Lisp, cl-geometry/polygon-binary.lisp: | | The cl-geometry/polygon-binary․lisp file |
| File, Lisp, cl-geometry/polygon-class.lisp: | | The cl-geometry/polygon-class․lisp file |
| File, Lisp, cl-geometry/polygon.lisp: | | The cl-geometry/polygon․lisp file |
| File, Lisp, cl-geometry/representations.lisp: | | The cl-geometry/representations․lisp file |
| File, Lisp, cl-geometry/trapezoidation.lisp: | | The cl-geometry/trapezoidation․lisp file |
| File, Lisp, cl-geometry/triangulation.lisp: | | The cl-geometry/triangulation․lisp file |
| File, Lisp, cl-geometry/trivial-geometry.lisp: | | The cl-geometry/trivial-geometry․lisp file |
|
L | | |
| Lisp File, cl-geometry.asd: | | The cl-geometry․asd file |
| Lisp File, cl-geometry/basic-line.lisp: | | The cl-geometry/basic-line․lisp file |
| Lisp File, cl-geometry/basic-point.lisp: | | The cl-geometry/basic-point․lisp file |
| Lisp File, cl-geometry/basic-polygon.lisp: | | The cl-geometry/basic-polygon․lisp file |
| Lisp File, cl-geometry/bentley-ottmann.lisp: | | The cl-geometry/bentley-ottmann․lisp file |
| Lisp File, cl-geometry/bounding-box.lisp: | | The cl-geometry/bounding-box․lisp file |
| Lisp File, cl-geometry/decomposition.lisp: | | The cl-geometry/decomposition․lisp file |
| Lisp File, cl-geometry/heap.lisp: | | The cl-geometry/heap․lisp file |
| Lisp File, cl-geometry/package.lisp: | | The cl-geometry/package․lisp file |
| Lisp File, cl-geometry/polygon-binary.lisp: | | The cl-geometry/polygon-binary․lisp file |
| Lisp File, cl-geometry/polygon-class.lisp: | | The cl-geometry/polygon-class․lisp file |
| Lisp File, cl-geometry/polygon.lisp: | | The cl-geometry/polygon․lisp file |
| Lisp File, cl-geometry/representations.lisp: | | The cl-geometry/representations․lisp file |
| Lisp File, cl-geometry/trapezoidation.lisp: | | The cl-geometry/trapezoidation․lisp file |
| Lisp File, cl-geometry/triangulation.lisp: | | The cl-geometry/triangulation․lisp file |
| Lisp File, cl-geometry/trivial-geometry.lisp: | | The cl-geometry/trivial-geometry․lisp file |
|
A.2 Functions
| Index Entry | | Section |
|
( | | |
| (setf a) : | | Exported generic functions |
| (setf a) : | | Exported generic functions |
| (setf b) : | | Exported generic functions |
| (setf b) : | | Exported generic functions |
| (setf c) : | | Exported generic functions |
| (setf c) : | | Exported generic functions |
| (setf direction) : | | Internal generic functions |
| (setf direction) : | | Internal generic functions |
| (setf ear) : | | Internal generic functions |
| (setf ear) : | | Internal generic functions |
| (setf edge) : | | Internal generic functions |
| (setf edge) : | | Internal generic functions |
| (setf edge-tree) : | | Internal generic functions |
| (setf edge-tree) : | | Internal generic functions |
| (setf edge1) : | | Internal generic functions |
| (setf edge1) : | | Internal generic functions |
| (setf edge2) : | | Internal generic functions |
| (setf edge2) : | | Internal generic functions |
| (setf end) : | | Exported generic functions |
| (setf end) : | | Exported generic functions |
| (setf next-node) : | | Internal generic functions |
| (setf next-node) : | | Internal generic functions |
| (setf prev-node) : | | Internal generic functions |
| (setf prev-node) : | | Internal generic functions |
| (setf start) : | | Exported generic functions |
| (setf start) : | | Exported generic functions |
| (setf taint) : | | Internal generic functions |
| (setf taint) : | | Internal generic functions |
| (setf val) : | | Internal generic functions |
| (setf val) : | | Internal generic functions |
| (setf x) : | | Exported generic functions |
| (setf x) : | | Exported generic functions |
| (setf x-max) : | | Internal generic functions |
| (setf x-max) : | | Internal generic functions |
| (setf x-min) : | | Internal generic functions |
| (setf x-min) : | | Internal generic functions |
| (setf y) : | | Exported generic functions |
| (setf y) : | | Exported generic functions |
| (setf y-max) : | | Internal generic functions |
| (setf y-max) : | | Internal generic functions |
| (setf y-min) : | | Internal generic functions |
| (setf y-min) : | | Internal generic functions |
|
A | | |
| a : | | Exported generic functions |
| a : | | Exported generic functions |
| add-if-intersection : | | Internal functions |
| area-circle : | | Exported functions |
| area-ellipse-axes : | | Exported functions |
| area-rectangle : | | Exported functions |
| area-simple-polygon : | | Exported functions |
| area-square : | | Exported functions |
| area-triangle-edge-edge-angle : | | Exported functions |
| area-triangle-edges : | | Exported functions |
| area-triangle-edges-small-angles : | | Exported functions |
| area-triangle-vertices : | | Exported functions |
|
B | | |
| b : | | Exported generic functions |
| b : | | Exported generic functions |
| bentley-ottmann : | | Exported functions |
| between-p : | | Internal functions |
| bounding-boxes-intersect-p : | | Internal functions |
|
C | | |
| c : | | Exported generic functions |
| c : | | Exported generic functions |
| check-node-integrity : | | Internal functions |
| check-tree-integrity : | | Internal functions |
| circumference-circle : | | Exported functions |
| circumference-ellipse-axes : | | Exported functions |
| colinear-p : | | Exported functions |
| collapse-trapezoid : | | Internal functions |
| collect-ring-nodes : | | Internal functions |
| construct-bounding-box : | | Internal generic functions |
| construct-bounding-box : | | Internal generic functions |
| construct-bounding-box : | | Internal generic functions |
| coords-to-points : | | Exported functions |
| copy-line-segment : | | Internal functions |
| create-initial-event-list : | | Internal functions |
|
D | | |
| decompose-complex-polygon-bentley-ottmann : | | Exported functions |
| decompose-complex-polygon-nondisjoint : | | Exported functions |
| decompose-complex-polygon-triangles : | | Exported functions |
| delete-edge : | | Internal functions |
| diagonal-p : | | Internal functions |
| direction : | | Internal generic functions |
| direction : | | Internal generic functions |
| distance : | | Exported functions |
| double-linked-ring-from-point-list : | | Internal functions |
|
E | | |
| ear : | | Internal generic functions |
| ear : | | Internal generic functions |
| ear-init : | | Internal functions |
| edge : | | Internal generic functions |
| edge : | | Internal generic functions |
| edge-list : | | Exported generic functions |
| edge-list : | | Exported generic functions |
| edge-list-from-point-list : | | Internal functions |
| edge-tree : | | Internal generic functions |
| edge-tree : | | Internal generic functions |
| edge1 : | | Internal generic functions |
| edge1 : | | Internal generic functions |
| edge2 : | | Internal generic functions |
| edge2 : | | Internal generic functions |
| end : | | Exported generic functions |
| end : | | Exported generic functions |
|
F | | |
| filter-ray-intersection : | | Internal functions |
| find-intersection : | | Internal functions |
| frustrated-polygon-p : | | Exported functions |
| Function, add-if-intersection : | | Internal functions |
| Function, area-circle : | | Exported functions |
| Function, area-ellipse-axes : | | Exported functions |
| Function, area-rectangle : | | Exported functions |
| Function, area-simple-polygon : | | Exported functions |
| Function, area-square : | | Exported functions |
| Function, area-triangle-edge-edge-angle : | | Exported functions |
| Function, area-triangle-edges : | | Exported functions |
| Function, area-triangle-edges-small-angles : | | Exported functions |
| Function, area-triangle-vertices : | | Exported functions |
| Function, bentley-ottmann : | | Exported functions |
| Function, between-p : | | Internal functions |
| Function, bounding-boxes-intersect-p : | | Internal functions |
| Function, check-node-integrity : | | Internal functions |
| Function, check-tree-integrity : | | Internal functions |
| Function, circumference-circle : | | Exported functions |
| Function, circumference-ellipse-axes : | | Exported functions |
| Function, colinear-p : | | Exported functions |
| Function, collapse-trapezoid : | | Internal functions |
| Function, collect-ring-nodes : | | Internal functions |
| Function, coords-to-points : | | Exported functions |
| Function, copy-line-segment : | | Internal functions |
| Function, create-initial-event-list : | | Internal functions |
| Function, decompose-complex-polygon-bentley-ottmann : | | Exported functions |
| Function, decompose-complex-polygon-nondisjoint : | | Exported functions |
| Function, decompose-complex-polygon-triangles : | | Exported functions |
| Function, delete-edge : | | Internal functions |
| Function, diagonal-p : | | Internal functions |
| Function, distance : | | Exported functions |
| Function, double-linked-ring-from-point-list : | | Internal functions |
| Function, ear-init : | | Internal functions |
| Function, edge-list-from-point-list : | | Internal functions |
| Function, filter-ray-intersection : | | Internal functions |
| Function, find-intersection : | | Internal functions |
| Function, frustrated-polygon-p : | | Exported functions |
| Function, heap-empty : | | Exported functions |
| Function, heap-lchild : | | Internal functions |
| Function, heap-parent : | | Internal functions |
| Function, heap-peek : | | Exported functions |
| Function, heap-rchild : | | Internal functions |
| Function, heapify : | | Exported functions |
| Function, in-cone-p : | | Internal functions |
| Function, insert-edge : | | Internal functions |
| Function, intersect-boxes : | | Internal functions |
| Function, intersect-p : | | Internal functions |
| Function, intersect-proper-p : | | Internal functions |
| Function, left-endpoint : | | Internal functions |
| Function, left-on-p : | | Internal functions |
| Function, left-p : | | Internal functions |
| Function, line-from-segment : | | Exported functions |
| Function, line-segment-length : | | Exported functions |
| Function, line-segments-intersection-point : | | Exported functions |
| Function, line-segments-intersection-segment : | | Exported functions |
| Function, line-x-at-y : | | Exported functions |
| Function, line-y-at-x : | | Exported functions |
| Function, lines-equal-p : | | Exported functions |
| Function, lines-intersection-point : | | Exported functions |
| Function, lines-parralel-p : | | Exported functions |
| Function, make-line-segment : | | Internal functions |
| Function, make-point : | | Internal functions |
| Function, make-polygon-from-coords : | | Exported functions |
| Function, make-polygon-from-point-list : | | Exported functions |
| Function, make-polygon-from-point-ring : | | Exported functions |
| Function, merge-line-segment-into : | | Internal functions |
| Function, move-sweep-line : | | Internal functions |
| Function, nheap-extract : | | Exported functions |
| Function, nheap-insert : | | Exported functions |
| Function, notany-symmetric-test : | | Internal functions |
| Function, order-line-segments-at-point : | | Internal functions |
| Function, orient-edge-right : | | Internal functions |
| Function, perimeter-rectangle : | | Exported functions |
| Function, perimeter-square : | | Exported functions |
| Function, perimeter-triangle : | | Exported functions |
| Function, point-equal-p : | | Exported functions |
| Function, point-in-box-exclusive : | | Internal functions |
| Function, point-in-box-inclusive : | | Internal functions |
| Function, point-in-polygon-crossing-p : | | Exported functions |
| Function, point-in-polygon-winding-number : | | Exported functions |
| Function, point-in-polygon-winding-p : | | Exported functions |
| Function, point-line-position : | | Internal functions |
| Function, point-list-from-ring : | | Internal functions |
| Function, point-sort-fun : | | Internal functions |
| Function, polygon-binary : | | Internal functions |
| Function, polygon-difference : | | Exported functions |
| Function, polygon-difference-nary : | | Exported functions |
| Function, polygon-intersection : | | Exported functions |
| Function, polygon-orientation : | | Exported functions |
| Function, polygon-union : | | Exported functions |
| Function, possible-diagonal-p : | | Internal functions |
| Function, recurse-bentley-ottmann : | | Internal functions |
| Function, recurse-sanitize-edges : | | Internal functions |
| Function, recurse-shamos-hoey : | | Internal functions |
| Function, remove-ear : | | Internal functions |
| Function, right-endpoint : | | Internal functions |
| Function, ring-to-list-of-edges : | | Internal functions |
| Function, sanitize-edges : | | Internal functions |
| Function, shamos-hoey : | | Exported functions |
| Function, simple-polygon-p : | | Exported functions |
| Function, simple-polygon-sh-p : | | Exported functions |
| Function, split-trapezoid : | | Internal functions |
| Function, trapezoidize-edges : | | Internal functions |
| Function, trapezoids-to-triangles : | | Internal functions |
| Function, triangle-center-point : | | Internal functions |
| Function, triangulate : | | Exported functions |
| Function, vertical-edge-p : | | Internal functions |
| Function, xor : | | Internal functions |
|
G | | |
| Generic Function, (setf a) : | | Exported generic functions |
| Generic Function, (setf b) : | | Exported generic functions |
| Generic Function, (setf c) : | | Exported generic functions |
| Generic Function, (setf direction) : | | Internal generic functions |
| Generic Function, (setf ear) : | | Internal generic functions |
| Generic Function, (setf edge) : | | Internal generic functions |
| Generic Function, (setf edge-tree) : | | Internal generic functions |
| Generic Function, (setf edge1) : | | Internal generic functions |
| Generic Function, (setf edge2) : | | Internal generic functions |
| Generic Function, (setf end) : | | Exported generic functions |
| Generic Function, (setf next-node) : | | Internal generic functions |
| Generic Function, (setf prev-node) : | | Internal generic functions |
| Generic Function, (setf start) : | | Exported generic functions |
| Generic Function, (setf taint) : | | Internal generic functions |
| Generic Function, (setf val) : | | Internal generic functions |
| Generic Function, (setf x) : | | Exported generic functions |
| Generic Function, (setf x-max) : | | Internal generic functions |
| Generic Function, (setf x-min) : | | Internal generic functions |
| Generic Function, (setf y) : | | Exported generic functions |
| Generic Function, (setf y-max) : | | Internal generic functions |
| Generic Function, (setf y-min) : | | Internal generic functions |
| Generic Function, a : | | Exported generic functions |
| Generic Function, b : | | Exported generic functions |
| Generic Function, c : | | Exported generic functions |
| Generic Function, construct-bounding-box : | | Internal generic functions |
| Generic Function, direction : | | Internal generic functions |
| Generic Function, ear : | | Internal generic functions |
| Generic Function, edge : | | Internal generic functions |
| Generic Function, edge-list : | | Exported generic functions |
| Generic Function, edge-tree : | | Internal generic functions |
| Generic Function, edge1 : | | Internal generic functions |
| Generic Function, edge2 : | | Internal generic functions |
| Generic Function, end : | | Exported generic functions |
| Generic Function, next-node : | | Internal generic functions |
| Generic Function, point-list : | | Exported generic functions |
| Generic Function, point-ring : | | Internal generic functions |
| Generic Function, prev-node : | | Internal generic functions |
| Generic Function, start : | | Exported generic functions |
| Generic Function, taint : | | Internal generic functions |
| Generic Function, val : | | Internal generic functions |
| Generic Function, x : | | Exported generic functions |
| Generic Function, x-max : | | Internal generic functions |
| Generic Function, x-min : | | Internal generic functions |
| Generic Function, y : | | Exported generic functions |
| Generic Function, y-max : | | Internal generic functions |
| Generic Function, y-min : | | Internal generic functions |
|
H | | |
| heap-empty : | | Exported functions |
| heap-lchild : | | Internal functions |
| heap-parent : | | Internal functions |
| heap-peek : | | Exported functions |
| heap-rchild : | | Internal functions |
| heapify : | | Exported functions |
|
I | | |
| in-cone-p : | | Internal functions |
| insert-edge : | | Internal functions |
| intersect-boxes : | | Internal functions |
| intersect-p : | | Internal functions |
| intersect-proper-p : | | Internal functions |
|
L | | |
| left-endpoint : | | Internal functions |
| left-on-p : | | Internal functions |
| left-p : | | Internal functions |
| line-from-segment : | | Exported functions |
| line-segment-length : | | Exported functions |
| line-segments-intersection-point : | | Exported functions |
| line-segments-intersection-segment : | | Exported functions |
| line-x-at-y : | | Exported functions |
| line-y-at-x : | | Exported functions |
| lines-equal-p : | | Exported functions |
| lines-intersection-point : | | Exported functions |
| lines-parralel-p : | | Exported functions |
|
M | | |
| make-line-segment : | | Internal functions |
| make-point : | | Internal functions |
| make-polygon-from-coords : | | Exported functions |
| make-polygon-from-point-list : | | Exported functions |
| make-polygon-from-point-ring : | | Exported functions |
| merge-line-segment-into : | | Internal functions |
| Method, (setf a) : | | Exported generic functions |
| Method, (setf b) : | | Exported generic functions |
| Method, (setf c) : | | Exported generic functions |
| Method, (setf direction) : | | Internal generic functions |
| Method, (setf ear) : | | Internal generic functions |
| Method, (setf edge) : | | Internal generic functions |
| Method, (setf edge-tree) : | | Internal generic functions |
| Method, (setf edge1) : | | Internal generic functions |
| Method, (setf edge2) : | | Internal generic functions |
| Method, (setf end) : | | Exported generic functions |
| Method, (setf next-node) : | | Internal generic functions |
| Method, (setf prev-node) : | | Internal generic functions |
| Method, (setf start) : | | Exported generic functions |
| Method, (setf taint) : | | Internal generic functions |
| Method, (setf val) : | | Internal generic functions |
| Method, (setf x) : | | Exported generic functions |
| Method, (setf x-max) : | | Internal generic functions |
| Method, (setf x-min) : | | Internal generic functions |
| Method, (setf y) : | | Exported generic functions |
| Method, (setf y-max) : | | Internal generic functions |
| Method, (setf y-min) : | | Internal generic functions |
| Method, a : | | Exported generic functions |
| Method, b : | | Exported generic functions |
| Method, c : | | Exported generic functions |
| Method, construct-bounding-box : | | Internal generic functions |
| Method, construct-bounding-box : | | Internal generic functions |
| Method, direction : | | Internal generic functions |
| Method, ear : | | Internal generic functions |
| Method, edge : | | Internal generic functions |
| Method, edge-list : | | Exported generic functions |
| Method, edge-tree : | | Internal generic functions |
| Method, edge1 : | | Internal generic functions |
| Method, edge2 : | | Internal generic functions |
| Method, end : | | Exported generic functions |
| Method, next-node : | | Internal generic functions |
| Method, point-list : | | Exported generic functions |
| Method, point-ring : | | Internal generic functions |
| Method, prev-node : | | Internal generic functions |
| Method, start : | | Exported generic functions |
| Method, taint : | | Internal generic functions |
| Method, val : | | Internal generic functions |
| Method, x : | | Exported generic functions |
| Method, x : | | Exported generic functions |
| Method, x-max : | | Internal generic functions |
| Method, x-min : | | Internal generic functions |
| Method, y : | | Exported generic functions |
| Method, y : | | Exported generic functions |
| Method, y-max : | | Internal generic functions |
| Method, y-min : | | Internal generic functions |
| move-sweep-line : | | Internal functions |
|
N | | |
| next-node : | | Internal generic functions |
| next-node : | | Internal generic functions |
| nheap-extract : | | Exported functions |
| nheap-insert : | | Exported functions |
| notany-symmetric-test : | | Internal functions |
|
O | | |
| order-line-segments-at-point : | | Internal functions |
| orient-edge-right : | | Internal functions |
|
P | | |
| perimeter-rectangle : | | Exported functions |
| perimeter-square : | | Exported functions |
| perimeter-triangle : | | Exported functions |
| point-equal-p : | | Exported functions |
| point-in-box-exclusive : | | Internal functions |
| point-in-box-inclusive : | | Internal functions |
| point-in-polygon-crossing-p : | | Exported functions |
| point-in-polygon-winding-number : | | Exported functions |
| point-in-polygon-winding-p : | | Exported functions |
| point-line-position : | | Internal functions |
| point-list : | | Exported generic functions |
| point-list : | | Exported generic functions |
| point-list-from-ring : | | Internal functions |
| point-ring : | | Internal generic functions |
| point-ring : | | Internal generic functions |
| point-sort-fun : | | Internal functions |
| polygon-binary : | | Internal functions |
| polygon-difference : | | Exported functions |
| polygon-difference-nary : | | Exported functions |
| polygon-intersection : | | Exported functions |
| polygon-orientation : | | Exported functions |
| polygon-union : | | Exported functions |
| possible-diagonal-p : | | Internal functions |
| prev-node : | | Internal generic functions |
| prev-node : | | Internal generic functions |
|
R | | |
| recurse-bentley-ottmann : | | Internal functions |
| recurse-sanitize-edges : | | Internal functions |
| recurse-shamos-hoey : | | Internal functions |
| remove-ear : | | Internal functions |
| right-endpoint : | | Internal functions |
| ring-to-list-of-edges : | | Internal functions |
|
S | | |
| sanitize-edges : | | Internal functions |
| shamos-hoey : | | Exported functions |
| simple-polygon-p : | | Exported functions |
| simple-polygon-sh-p : | | Exported functions |
| split-trapezoid : | | Internal functions |
| start : | | Exported generic functions |
| start : | | Exported generic functions |
|
T | | |
| taint : | | Internal generic functions |
| taint : | | Internal generic functions |
| trapezoidize-edges : | | Internal functions |
| trapezoids-to-triangles : | | Internal functions |
| triangle-center-point : | | Internal functions |
| triangulate : | | Exported functions |
|
V | | |
| val : | | Internal generic functions |
| val : | | Internal generic functions |
| vertical-edge-p : | | Internal functions |
|
X | | |
| x : | | Exported generic functions |
| x : | | Exported generic functions |
| x : | | Exported generic functions |
| x-max : | | Internal generic functions |
| x-max : | | Internal generic functions |
| x-min : | | Internal generic functions |
| x-min : | | Internal generic functions |
| xor : | | Internal functions |
|
Y | | |
| y : | | Exported generic functions |
| y : | | Exported generic functions |
| y : | | Exported generic functions |
| y-max : | | Internal generic functions |
| y-max : | | Internal generic functions |
| y-min : | | Internal generic functions |
| y-min : | | Internal generic functions |
|
A.3 Variables
| Index Entry | | Section |
|
A | | |
| a : | | Exported classes |
|
B | | |
| b : | | Exported classes |
|
C | | |
| c : | | Exported classes |
|
D | | |
| direction : | | Internal classes |
|
E | | |
| ear : | | Internal classes |
| edge : | | Internal classes |
| edge-list : | | Exported classes |
| edge-tree : | | Internal classes |
| edge1 : | | Internal classes |
| edge2 : | | Internal classes |
| end : | | Exported classes |
|
N | | |
| next : | | Internal classes |
|
P | | |
| point-list : | | Exported classes |
| point-ring : | | Exported classes |
| prev : | | Internal classes |
|
S | | |
| Slot, a : | | Exported classes |
| Slot, b : | | Exported classes |
| Slot, c : | | Exported classes |
| Slot, direction : | | Internal classes |
| Slot, ear : | | Internal classes |
| Slot, edge : | | Internal classes |
| Slot, edge-list : | | Exported classes |
| Slot, edge-tree : | | Internal classes |
| Slot, edge1 : | | Internal classes |
| Slot, edge2 : | | Internal classes |
| Slot, end : | | Exported classes |
| Slot, next : | | Internal classes |
| Slot, point-list : | | Exported classes |
| Slot, point-ring : | | Exported classes |
| Slot, prev : | | Internal classes |
| Slot, start : | | Exported classes |
| Slot, taint : | | Internal classes |
| Slot, val : | | Internal classes |
| Slot, x : | | Exported classes |
| Slot, x-max : | | Internal classes |
| Slot, x-min : | | Internal classes |
| Slot, y : | | Exported classes |
| Slot, y-max : | | Internal classes |
| Slot, y-min : | | Internal classes |
| start : | | Exported classes |
|
T | | |
| taint : | | Internal classes |
|
V | | |
| val : | | Internal classes |
|
X | | |
| x : | | Exported classes |
| x-max : | | Internal classes |
| x-min : | | Internal classes |
|
Y | | |
| y : | | Exported classes |
| y-max : | | Internal classes |
| y-min : | | Internal classes |
|
A.4 Data types
| Index Entry | | Section |
|
2 | | |
| 2d-geometry : | | The 2d-geometry package |
|
B | | |
| bounding-box : | | Internal classes |
|
C | | |
| cl-geometry : | | The cl-geometry system |
| Class, bounding-box : | | Internal classes |
| Class, ear-ring-node : | | Internal classes |
| Class, event-endpoint : | | Internal classes |
| Class, event-intersection : | | Internal classes |
| Class, line : | | Exported classes |
| Class, line-segment : | | Exported classes |
| Class, point : | | Exported classes |
| Class, poly-ring-node : | | Internal classes |
| Class, polygon : | | Exported classes |
| Class, sweep-line : | | Internal classes |
| Class, taint-segment : | | Internal classes |
|
E | | |
| ear-ring-node : | | Internal classes |
| event-endpoint : | | Internal classes |
| event-intersection : | | Internal classes |
|
L | | |
| line : | | Exported classes |
| line-segment : | | Exported classes |
|
P | | |
| Package, 2d-geometry : | | The 2d-geometry package |
| Package, ramarren-utils : | | The ramarren-utils package |
| point : | | Exported classes |
| poly-ring-node : | | Internal classes |
| polygon : | | Exported classes |
|
R | | |
| ramarren-utils : | | The ramarren-utils package |
|
S | | |
| sweep-line : | | Internal classes |
| System, cl-geometry : | | The cl-geometry system |
|
T | | |
| taint-segment : | | Internal classes |
|