# The cl-geometry Reference Manual

## Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

# The cl-geometry Reference Manual

This is the cl-geometry Reference Manual, version 0.0.3, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:08:55 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

# 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`.

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

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

Previous: , Up: Systems   [Contents][Index]

### 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

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Files

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

Previous: , Up: Files   [Contents][Index]

### 3.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.1 cl-geometry.asd

Location

cl-geometry.asd

Systems

cl-geometry (system)

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.2 cl-geometry/package.lisp

Dependency

heap.lisp (file)

Parent

cl-geometry (system)

Location

package.lisp

Packages

#### 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
• x (method)
• y (method)
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

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 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
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

Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.16 cl-geometry/polygon-binary.lisp

Dependencies
Parent

cl-geometry (system)

Location

polygon-binary.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Packages

Packages are listed by definition order.

Next: , Previous: , Up: Packages   [Contents][Index]

### 4.1 2d-geometry

Source

package.lisp (file)

Nicknames
• cl-geometry
• geometry
Use List
Exported Definitions
Internal Definitions

Previous: , Up: Packages   [Contents][Index]

### 4.2 ramarren-utils

Source

heap.lisp (file)

Use List

common-lisp

Used By List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Definitions

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

Next: , Previous: , Up: Definitions   [Contents][Index]

### 5.1 Exported definitions

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.1 Functions

Function: area-circle R

Area of a circle.

Package
Source

trivial-geometry.lisp (file)

Function: area-ellipse-axes A B

Area of an ellipse given semimajor and semiminor axes.

Package
Source

trivial-geometry.lisp (file)

Function: area-rectangle A B

Area of a rectangle given length of edges.

Package
Source

trivial-geometry.lisp (file)

Function: area-simple-polygon POLYGON

Calculate an area of a simple polygon.

Package
Source

basic-polygon.lisp (file)

Function: area-square A

Area of a square given length of a side.

Package
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
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
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
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
Source

trivial-geometry.lisp (file)

Function: bentley-ottmann EDGE-LIST

Return a list of intersection points (events).

Package
Source

bentley-ottmann.lisp (file)

Function: circumference-circle R

Circumference of a circle.

Package
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
Source

trivial-geometry.lisp (file)

Function: colinear-p A B C

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

Package
Source

basic-point.lisp (file)

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

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

Package
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
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
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
Source

polygon.lisp (file)

Function: distance X1 Y1 X2 Y2

Distance between two points on a plane.

Package
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
Source

basic-polygon.lisp (file)

Function: heap-empty WHERE
Package
Source

heap.lisp (file)

Function: heap-peek WHERE
Package
Source

heap.lisp (file)

Function: heapify WHAT COMPAR

Turns list into a heap

Package
Source

heap.lisp (file)

Function: line-from-segment LINE-SEGMENT

Calculate line from line segment.

Package
Source

basic-line.lisp (file)

Function: line-segment-length LINE-SEGMENT

Calculate length of a segment.

Package
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
Source

basic-line.lisp (file)

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

Find an intersection of two colinear line segments.

Package
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
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
Source

basic-line.lisp (file)

Function: lines-equal-p LINE1 LINE2

Check if two lines are equal.

Package
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
Source

basic-line.lisp (file)

Function: lines-parralel-p LINE1 LINE2

Check if two lines are parrallel.

Package
Source

basic-line.lisp (file)

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

polygon-class.lisp (file)

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

polygon-class.lisp (file)

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

polygon-class.lisp (file)

Function: nheap-extract WHERE
Package
Source

heap.lisp (file)

Function: nheap-insert WHAT WHERE
Package
Source

heap.lisp (file)

Function: perimeter-rectangle A B

Perimeter of a rectangle given length of edges.

Package
Source

trivial-geometry.lisp (file)

Function: perimeter-square A

Perimeter of a square given length of a side.

Package
Source

trivial-geometry.lisp (file)

Function: perimeter-triangle A B C

Perimeter of a triangle given length of edges.

Package
Source

trivial-geometry.lisp (file)

Function: point-equal-p POINT1 POINT2

Checks if two points are geometrically equal.

Package
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
Source

basic-polygon.lisp (file)

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

Calculate winding number of a point.

Package
Source

basic-polygon.lisp (file)

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

Check if point is in polygon using winding number rule.

Package
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
Source

polygon-binary.lisp (file)

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

Return triangles of polygon with some holes.

Package
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
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
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
Source

polygon-binary.lisp (file)

Function: shamos-hoey EDGE-LIST

Returns t if there is at least one intersection.

Package
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
Source

basic-polygon.lisp (file)

Function: simple-polygon-sh-p POLYGON

Check if polygon is simple using Shamos-Hoey algorithm.

Package
Source

polygon.lisp (file)

Function: triangulate POLYGON

Triangulate polygon. Returns list of triangles.

Package
Source

triangulation.lisp (file)

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.2 Generic functions

Generic Function: a OBJECT
Generic Function: (setf a) NEW-VALUE OBJECT
Package
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
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
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
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
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
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
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
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
Source

bentley-ottmann.lisp (file)

Reader

x (generic function)

Methods
Method: (setf x) NEW-VALUE (OBJECT sweep-line)
Generic Function: y OBJECT
Package
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
Source

bentley-ottmann.lisp (file)

Reader

y (generic function)

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

Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.3 Classes

Class: line ()

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

Package
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
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
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
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)

Previous: , Up: Definitions   [Contents][Index]

### 5.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.1 Functions

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

Add intersection to event queue if edge1 intersects edge2.

Package
Source

bentley-ottmann.lisp (file)

Function: between-p A B C

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

Package
Source

basic-point.lisp (file)

Function: bounding-boxes-intersect-p BOX1 BOX2

Check if two bounding boxes intersect.

Package
Source

bounding-box.lisp (file)

Function: check-node-integrity NODE SWEEP-LINE

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

Package
Source

bentley-ottmann.lisp (file)

Function: check-tree-integrity SWEEP-LINE

Verify sweep line tree integrity.

Package
Source

bentley-ottmann.lisp (file)

Function: collapse-trapezoid TRAPEZOID

Reduce degenerate trapezoids to triangles.

Package
Source

trapezoidation.lisp (file)

Function: collect-ring-nodes RING

Construct a list of all nodes in a ring.

Package
Source

representations.lisp (file)

Function: copy-line-segment LINE-SEGMENT
Package
Source

basic-line.lisp (file)

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

Create initial list of endpoint events.

Package
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
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
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
Source

representations.lisp (file)

Function: ear-init POINT-LIST

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

Package
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
Source

representations.lisp (file)

Function: filter-ray-intersection POINT EDGE

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

Package
Source

basic-polygon.lisp (file)

Function: find-intersection EDGE-LIST
Package
Source

decomposition.lisp (file)

Function: heap-lchild I
Package
Source

heap.lisp (file)

Function: heap-parent I
Package
Source

heap.lisp (file)

Function: heap-rchild I
Package
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
Source

triangulation.lisp (file)

Function: insert-edge EDGE SWEEP-LINE

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

Package
Source

bentley-ottmann.lisp (file)

Function: intersect-boxes BOX1 BOX2

Return bounding box common to both boxes.

Package
Source

bounding-box.lisp (file)

Function: intersect-p A B C D

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

Package
Source

basic-point.lisp (file)

Function: intersect-proper-p A B C D

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

Package
Source

basic-point.lisp (file)

Function: left-endpoint EDGE

Return left endpoint of an edge.

Package
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
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
Source

basic-point.lisp (file)

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

Create a new line segment.

Package
Source

basic-line.lisp (file)

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

Create a new point like object.

Package
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
Source

polygon-binary.lisp (file)

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

Move sweep line to new location.

Package
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
Source

basic-polygon.lisp (file)

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

Return t if lv is above rv at point.

Package
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
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
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
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
Source

basic-line.lisp (file)

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

Return a list of points in a ring.

Package
Source

representations.lisp (file)

Function: point-sort-fun POINT1 POINT2

Order points by increasing x then y.

Package
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
Source

polygon-binary.lisp (file)

Function: possible-diagonal-p RING-DIAG

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

Package
Source

triangulation.lisp (file)

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

Recurse down event queue.

Package
Source

bentley-ottmann.lisp (file)

Function: recurse-sanitize-edges EDGE-LIST ACC
Package
Source

polygon-binary.lisp (file)

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

Recurse down event list.

Package
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
Source

triangulation.lisp (file)

Function: right-endpoint EDGE

Return right endpoint of an edge.

Package
Source

bentley-ottmann.lisp (file)

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

Construct a list of edges attached to vertexes.

Package
Source

representations.lisp (file)

Function: sanitize-edges EDGE-LIST

Drop zero length edges and merge all segment intersecting edges.

Package
Source

polygon-binary.lisp (file)

Function: split-trapezoid TRAPEZOID

Split trapezoid into two triangles. Return a cons.

Package
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
Source

trapezoidation.lisp (file)

Function: trapezoids-to-triangles TRAPEZ

Convert list of trapezoids to list of triangles.

Package
Source

polygon.lisp (file)

Function: triangle-center-point TRIANGLE

Return a central point of triangle.

Package
Source

polygon.lisp (file)

Function: vertical-edge-p EDGE

Returns t if edge is horizontal.

Package
Source

trapezoidation.lisp (file)

Function: xor P Q

Exlusive or logical operation.

Package
Source

basic-point.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.2 Generic functions

Generic Function: construct-bounding-box OBJECT

Construct a bounding box of a given object.

Package
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)

Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.3 Classes

Class: bounding-box ()

A bounding box.

Package
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
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
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
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
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
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
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)

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Jump to: C   F   L
Jump to: C   F   L

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

Jump to: (   A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   V   X   Y
Jump to: (   A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   V   X   Y

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.3 Variables

Jump to: A   B   C   D   E   N   P   S   T   V   X   Y
Jump to: A   B   C   D   E   N   P   S   T   V   X   Y

Previous: , Up: Indexes   [Contents][Index]

### A.4 Data types

Jump to: 2   B   C   E   L   P   R   S   T
Jump to: 2   B   C   E   L   P   R   S   T