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.3 "Robert April" on Tue Feb 20 08:04:46 2018 GMT+0.


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

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

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

2d-geometry


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

3.1.3 cl-geometry/trivial-geometry.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

trivial-geometry.lisp

Exported Definitions

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

3.1.4 cl-geometry/basic-point.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

basic-point.lisp

Exported Definitions
Internal Definitions

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

3.1.5 cl-geometry/bounding-box.lisp

Dependency

package.lisp (file)

Parent

cl-geometry (system)

Location

bounding-box.lisp

Internal Definitions

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

3.1.6 cl-geometry/basic-line.lisp

Dependencies
Parent

cl-geometry (system)

Location

basic-line.lisp

Exported Definitions
Internal Definitions

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

3.1.7 cl-geometry/representations.lisp

Dependencies
Parent

cl-geometry (system)

Location

representations.lisp

Exported Definitions
Internal Definitions

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

3.1.8 cl-geometry/polygon-class.lisp

Dependencies
Parent

cl-geometry (system)

Location

polygon-class.lisp

Exported Definitions
Internal Definitions

point-ring (method)


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

3.1.9 cl-geometry/basic-polygon.lisp

Dependencies
Parent

cl-geometry (system)

Location

basic-polygon.lisp

Exported Definitions
Internal Definitions

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

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)


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

3.1.12 cl-geometry/heap.lisp

Parent

cl-geometry (system)

Location

heap.lisp

Packages

ramarren-utils

Exported Definitions
Internal Definitions

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

3.1.13 cl-geometry/bentley-ottmann.lisp

Dependencies
Parent

cl-geometry (system)

Location

bentley-ottmann.lisp

Exported Definitions
Internal Definitions

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

3.1.14 cl-geometry/trapezoidation.lisp

Dependencies
Parent

cl-geometry (system)

Location

trapezoidation.lisp

Internal Definitions

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

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

2d-geometry

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

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-ellipse-axes A B

Area of an ellipse given semimajor and semiminor axes.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-rectangle A B

Area of a rectangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-simple-polygon POLYGON

Calculate an area of a simple polygon.

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: area-square A

Area of a square given length of a side.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

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

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: area-triangle-edges A B C

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

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

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

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

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: bentley-ottmann EDGE-LIST

Return a list of intersection points (events).

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: circumference-circle R

Circumference of a circle.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: circumference-ellipse-axes A B

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

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: colinear-p A B C

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

Package

2d-geometry

Source

basic-point.lisp (file)

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

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

Package

2d-geometry

Source

basic-point.lisp (file)

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

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

Package

2d-geometry

Source

polygon.lisp (file)

Function: decompose-complex-polygon-nondisjoint POLYGON

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

Package

2d-geometry

Source

decomposition.lisp (file)

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

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

Package

2d-geometry

Source

polygon.lisp (file)

Function: distance X1 Y1 X2 Y2

Distance between two points on a plane.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: frustrated-polygon-p POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: heap-empty WHERE
Package

ramarren-utils

Source

heap.lisp (file)

Function: heap-peek WHERE
Package

ramarren-utils

Source

heap.lisp (file)

Function: heapify WHAT COMPAR

Turns list into a heap

Package

ramarren-utils

Source

heap.lisp (file)

Function: line-from-segment LINE-SEGMENT

Calculate line from line segment.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-segment-length LINE-SEGMENT

Calculate length of a segment.

Package

2d-geometry

Source

basic-line.lisp (file)

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

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

Package

2d-geometry

Source

basic-line.lisp (file)

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

Find an intersection of two colinear line segments.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-x-at-y LINE Y

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: line-y-at-x LINE X

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-equal-p LINE1 LINE2

Check if two lines are equal.

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-intersection-point LINE1 LINE2

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

Package

2d-geometry

Source

basic-line.lisp (file)

Function: lines-parralel-p LINE1 LINE2

Check if two lines are parrallel.

Package

2d-geometry

Source

basic-line.lisp (file)

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

2d-geometry

Source

polygon-class.lisp (file)

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

2d-geometry

Source

polygon-class.lisp (file)

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

2d-geometry

Source

polygon-class.lisp (file)

Function: nheap-extract WHERE
Package

ramarren-utils

Source

heap.lisp (file)

Function: nheap-insert WHAT WHERE
Package

ramarren-utils

Source

heap.lisp (file)

Function: perimeter-rectangle A B

Perimeter of a rectangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: perimeter-square A

Perimeter of a square given length of a side.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: perimeter-triangle A B C

Perimeter of a triangle given length of edges.

Package

2d-geometry

Source

trivial-geometry.lisp (file)

Function: point-equal-p POINT1 POINT2

Checks if two points are geometrically equal.

Package

2d-geometry

Source

basic-point.lisp (file)

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

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

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

Calculate winding number of a point.

Package

2d-geometry

Source

basic-polygon.lisp (file)

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

Check if point is in polygon using winding number rule.

Package

2d-geometry

Source

basic-polygon.lisp (file)

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

Return triangles of polygon1 minus polygon2.

Package

2d-geometry

Source

polygon-binary.lisp (file)

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

Return triangles of polygon with some holes.

Package

2d-geometry

Source

polygon-binary.lisp (file)

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

Return triangles of an intersection of two polygons.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: polygon-orientation POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

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

Return triangles of an union of two polygons.

Package

2d-geometry

Source

polygon-binary.lisp (file)

Function: shamos-hoey EDGE-LIST

Returns t if there is at least one intersection.

Package

2d-geometry

Source

bentley-ottmann.lisp (file)

Function: simple-polygon-p POLYGON

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

Package

2d-geometry

Source

basic-polygon.lisp (file)

Function: simple-polygon-sh-p POLYGON

Check if polygon is simple using Shamos-Hoey algorithm.

Package

2d-geometry

Source

polygon.lisp (file)

Function: triangulate POLYGON

Triangulate polygon. Returns list of triangles.

Package

2d-geometry

Source

triangulation.lisp (file)


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

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)

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

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)


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

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)


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

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)


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

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)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-geometry.asd: The cl-geometry<dot>asd file
cl-geometry/basic-line.lisp: The cl-geometry/basic-line<dot>lisp file
cl-geometry/basic-point.lisp: The cl-geometry/basic-point<dot>lisp file
cl-geometry/basic-polygon.lisp: The cl-geometry/basic-polygon<dot>lisp file
cl-geometry/bentley-ottmann.lisp: The cl-geometry/bentley-ottmann<dot>lisp file
cl-geometry/bounding-box.lisp: The cl-geometry/bounding-box<dot>lisp file
cl-geometry/decomposition.lisp: The cl-geometry/decomposition<dot>lisp file
cl-geometry/heap.lisp: The cl-geometry/heap<dot>lisp file
cl-geometry/package.lisp: The cl-geometry/package<dot>lisp file
cl-geometry/polygon-binary.lisp: The cl-geometry/polygon-binary<dot>lisp file
cl-geometry/polygon-class.lisp: The cl-geometry/polygon-class<dot>lisp file
cl-geometry/polygon.lisp: The cl-geometry/polygon<dot>lisp file
cl-geometry/representations.lisp: The cl-geometry/representations<dot>lisp file
cl-geometry/trapezoidation.lisp: The cl-geometry/trapezoidation<dot>lisp file
cl-geometry/triangulation.lisp: The cl-geometry/triangulation<dot>lisp file
cl-geometry/trivial-geometry.lisp: The cl-geometry/trivial-geometry<dot>lisp file

F
File, Lisp, cl-geometry.asd: The cl-geometry<dot>asd file
File, Lisp, cl-geometry/basic-line.lisp: The cl-geometry/basic-line<dot>lisp file
File, Lisp, cl-geometry/basic-point.lisp: The cl-geometry/basic-point<dot>lisp file
File, Lisp, cl-geometry/basic-polygon.lisp: The cl-geometry/basic-polygon<dot>lisp file
File, Lisp, cl-geometry/bentley-ottmann.lisp: The cl-geometry/bentley-ottmann<dot>lisp file
File, Lisp, cl-geometry/bounding-box.lisp: The cl-geometry/bounding-box<dot>lisp file
File, Lisp, cl-geometry/decomposition.lisp: The cl-geometry/decomposition<dot>lisp file
File, Lisp, cl-geometry/heap.lisp: The cl-geometry/heap<dot>lisp file
File, Lisp, cl-geometry/package.lisp: The cl-geometry/package<dot>lisp file
File, Lisp, cl-geometry/polygon-binary.lisp: The cl-geometry/polygon-binary<dot>lisp file
File, Lisp, cl-geometry/polygon-class.lisp: The cl-geometry/polygon-class<dot>lisp file
File, Lisp, cl-geometry/polygon.lisp: The cl-geometry/polygon<dot>lisp file
File, Lisp, cl-geometry/representations.lisp: The cl-geometry/representations<dot>lisp file
File, Lisp, cl-geometry/trapezoidation.lisp: The cl-geometry/trapezoidation<dot>lisp file
File, Lisp, cl-geometry/triangulation.lisp: The cl-geometry/triangulation<dot>lisp file
File, Lisp, cl-geometry/trivial-geometry.lisp: The cl-geometry/trivial-geometry<dot>lisp file

L
Lisp File, cl-geometry.asd: The cl-geometry<dot>asd file
Lisp File, cl-geometry/basic-line.lisp: The cl-geometry/basic-line<dot>lisp file
Lisp File, cl-geometry/basic-point.lisp: The cl-geometry/basic-point<dot>lisp file
Lisp File, cl-geometry/basic-polygon.lisp: The cl-geometry/basic-polygon<dot>lisp file
Lisp File, cl-geometry/bentley-ottmann.lisp: The cl-geometry/bentley-ottmann<dot>lisp file
Lisp File, cl-geometry/bounding-box.lisp: The cl-geometry/bounding-box<dot>lisp file
Lisp File, cl-geometry/decomposition.lisp: The cl-geometry/decomposition<dot>lisp file
Lisp File, cl-geometry/heap.lisp: The cl-geometry/heap<dot>lisp file
Lisp File, cl-geometry/package.lisp: The cl-geometry/package<dot>lisp file
Lisp File, cl-geometry/polygon-binary.lisp: The cl-geometry/polygon-binary<dot>lisp file
Lisp File, cl-geometry/polygon-class.lisp: The cl-geometry/polygon-class<dot>lisp file
Lisp File, cl-geometry/polygon.lisp: The cl-geometry/polygon<dot>lisp file
Lisp File, cl-geometry/representations.lisp: The cl-geometry/representations<dot>lisp file
Lisp File, cl-geometry/trapezoidation.lisp: The cl-geometry/trapezoidation<dot>lisp file
Lisp File, cl-geometry/triangulation.lisp: The cl-geometry/triangulation<dot>lisp file
Lisp File, cl-geometry/trivial-geometry.lisp: The cl-geometry/trivial-geometry<dot>lisp file

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

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

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

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