- A set of points on a plane , .
- An array of weights , , one for each
point .
- Parameter space
, restricted to the rectangle
,
.
- A vote threshold .
- A maximum level of subdivision .

**begin**

- Declare new variables:
- Arrays
and
of intercepts
,
, .
An array of boolean flags .

Integer variables and .

Variables and comprising a point in space.

Another array of flags .

Boolean flags , , and .

The variables , , , and array are used to keep track of the best fit as the algorithm proceeds.

Set all the to .

For each point :

**begin**- Set flags corresponding to intercepts lying below/above vertices of
the root rectangle:
if set to , otherwise set it to .

if set to , otherwise set it to .

if set to , otherwise set it to .

if set to , otherwise set it to .

If the 's are either all true or all false, the line misses the root rectangle, otherwise they intersect. If they intersect, set to , to and to .

**end**Call the procedure with arguments as follows:

- Array of flags .
- Arrays
and
.
- Variables and .
- Initial level of subdivision 0.
- Initial accumulator value 0.
- Empty line of descent list.

Procedure ( array of flags , arrays of intercepts and , variables and , subdivision level , accumulator value , line of descent list ):

**begin**

- Declare new variables:
- Boolean flag arrays , ,
and each with elements.
All the elements of the flag arrays are initialised to .
Array of intercepts with elements.

Accumulators , , and , initialised to zero.

Variable .

Nine boolean flags , , , , , , , , .

Boolean flag , initialised to .

Sum the votes for the child rectangles: For each such that :

**begin**- Set flags , etc. to .
Set to .

If then:

**begin**- Set to .
If then:

**begin**- Set to .
If then set to .

**end**

**end**Repeat for intercept and flags , and .

Repeat for intercept and flags , and .

**end**If , , and are not all either or :

**begin**- Add weight to
Set flag to .

**end**Repeat for flags , , and , accumulator and flag .

Repeat for flags , , and , accumulator and flag .

Repeat for flags , , and , accumulator and flag .

Subdivide child rectangles receiving greater than or equal to votes: If :

**begin**

- If recursively subdivide child rectangle:
**begin**- Add [-1,-1] to original line of descent.
Call with arguments , , , , , , and extended line of descent.

Set flag to .

**end**Repeat with accumulator , index pair [-1,1], flag list , intercept arrays and , and values and .

Repeat with accumulator , index pair [1,-1], flag list , intercept arrays and , and values and .

Repeat with accumulator , index pair [1,1], flag list , intercept arrays and , and values and .

If is still (i.e. no further subdivision of this rectangle), test for best fit so far:

- If
or if
and
:
**begin**- Set to .
Set to .

Calculate centre of rectangle in direction by calling procedure with the line of descent as argument. The result is copied into .

Set to .

Copy array of flags into array .

**end**

Procedure ( line of descent list ):
**begin**

- Declare new variables:
- Array of three elements with indices -1, 0 and 1. The zero (middle) element of is not used.

Set to zero.

While line of descent not traversed (i.e. root rectangle not yet reached):

**begin**- Take next pair of indices on line of descent.
Replace old value of :

**end**Add centre -coordinate of root cube to :

At the end of the algorithm is the highest level of subdivision reached, the highest accumulator value at level , while and hold the best fit line parameters.

Note that the points are never used by the procedure . All the information about the points is contained in the intercept arrays. The index part of the line of descent is actually superflous since the positions of rectangles are passed from parent to child via and .