An hypothetical machine would be composed of 3 major parts.

An internal DCEL engine

An internal Doubly Connected Edge List is the fundamental representation of the sheet of paper in a machine. This representation allows easy queries on many important parts of the model.

Geometric primitives

Standard geometric queries, like left/right turns and relative left/right positions (of say a line and a point). The axioms are included here, for sake of grouping. Some axioms (that is, axioms 3, 5 and 6) are not always possible, or are possible in more than one way (or both). The feasibility queries and the different possibilities count queries are two other queries that can be asked to the machine.

A LISP or Scheme interpreter

To patch up the few missing parts (how do you represent lists of, say, points), an OCM should call upon LISP-like features (car, cdr, list, append, etc.) to complete.

It is noteworthy that a few usual concepts have been conveniently forgotten, and are not part of the OCM described here:

Pointers

While any machine that accesses complex objects like edges and faces (which are, in a DCEL represented as a pair of vertices and a list of edges, respectively) needs some sort of reference value, the OCM uses pointers in the same way Java does: You get pointers, but you can only dereference, not access them directly.

Cartesian, Polar, Plucker or whatever Coordinates

Again, no coordinates are provided inside the model itself. While most likely required to do meaningful input/output, the coordinate system used internally by the OCM is not available to the programmer.

Arithmetic

Once coordinates were eliminated, the usefulness of numbers is questionable in a purely geometry-oriented machine. As such, they were not included in the original design.

Before we describe the OCM in details, a few definitions are required:

Point

While Euclid described a point as follwing: A point is that which has no parts, or which has no magnitude, we shall use the following definition: A point is the minimal addressable unit of the OCM, that is, the one datatype that is not defined out of other datatypes.

Line

A line is A maximal set of points that the OCM considers to be colinear. While this may at first sound redundant (A line is colinear points), it defines a line in terms of OCM functionality. A line is the set of points the OCM considers to be a line. It respects the usual stuff, mainly that all triples of points on a given line are all colinear.

Edge

A continuous subset of a line. By continuous, it is understood that if any two points A & B are part of the segment, all points C between A & B are part of the edge as well. An edge has two distinctive points, it's endpoints, which have the important property that all points on the edge are between the endpoints. By between, it is understood, in cartesian coordinates, that a point C is between points A & B on a line L if A, B and C are part of L, and that one of the following is true:

• x_a < x_C < x_B and y_a < y_C < y_B
• x_a < x_C < x_B and y_a > y_C > y_B
• x_a > x_C > x_B and y_a < y_C < y_B
• x_a > x_C > x_B and y_a > y_C > y_B

Face

A face will be defined by the intersection of half-planes, and half-planes will be defined as being the set of all points on the same (given) side of a given line.

A standard data structure of computational geometer, the DCEL represents the four main primitives datatypes as such:

Point (Vertex)

A vertex just is. It is represented by the coordinates of the vertex, but those are not available to OCM programmers.

Half-Edge

Half-Edges are, as can be supposed, two to an edge. They represent, intutuively the 'right' and 'left' side. Since an edge always, in the OCM, connects two faces, an half-edge is the part of an edge that is connected to one of the two faces.

Defined by the pair of endpoints, two vertices. It contains pointers to each endpoint, to the next and previous edge in a loop around a face, to it's twin edge (the other half-edge that forms a complete edge) and to the face it is associated with. It can also return the line that is concurrent with it.

Face

A face is defined mainly by it's edge loop, that is the set of edge that 'surround' it. A face in the OCM contains a pointer to one of it's edges. A random one.

Line

While not strictly part of std DCELs, a line is defined as above. It mainly exist for left/right position purposes, and because of the way a fold is created: A line is created and then the internal engine creates all edges by finding all intersections and connecting them in order.

First of all, the axioms are the constructive part of the whole machine: You add new lines (and thus new vertices by virtue of intersection and new edges connecting those new vertices).

Second, feasibility queries on those axioms (3, 5 and 6) give some query capability.

Finally, some standard geometric queries have been included, including the right/left turnness of three points (or colinearity) and the right/left relative position (or intersection) of a point to a line (in case of an horizontal line, left = up and right = below).

Used mainly as a patch to whatever has been forgotten, a reduced LISP interpreter has been included, to deal with such things as lists and code representation. It is expected an implementor would need nothing past car, cdr, list, append and functions returning the above mentionned operations.

It is interesting to note that the MIT's AI Lab had a working hardware implementation of a LISP machine in the 1976.