## pseudocode.js | |
---|---|

## preprocess(polygons)Usage:
Arguments: `polygons` An array of polygons.- Polygons are arrays of vertices.
- Vertices are objects with numeric
`x` and`y` properties.
- Example of structure:
var polygons = [ [{ x: 5, y:4 }, {x: 10, y: 4}, {x: 1, y: 1}], [{ x: 5, y:4 }, {x: 10, y: 4}, {x: 15, y: 10}] ]; Returns: - A
`vertices` object.- Keys are integer polygon ids, assigned to input polygons in the order they are encountered in the input.
- Values are
`vertex` objects with:`vertex.x` and`vertex.y` numeric coordinates,`vertex.memberships` An array whose elements are vertex`membership` objects with:`membership.polygonId` `membership.vertexId` These are assigned to vertices in the order they are encountered in the input,`polygons` .
| `var preprocess = function(polygons){` |

Keys: - Strings of the form
`x+"_"+y` .
- Strings of the form
Values: - Vertex objects
- see description of output for
`preprocess(polygons)`
| ```
var verticesByLocation = {}
var location = function(vertex){
return vertex.x+"_"+vertex.y;
};
``` |

- An array of vertex objects.
- This is returned from the function.
- see description of output for
`preprocess(polygons)`
| ` var vertices = [];` |

## Algorithm- Maintain an incrementing integer
`polygonId` for assigning identifiers to input polygons.- Starts at 0.
| ```
var polygonId = 0;
_(polygons).each(function(polygon){
``` |

- Maintain an incrementing integer
`vertexId` for assigning identifiers to input vertices.- Starts at 0 for each polygon.
| ` var vertexId = 0;` |

- For each polygon, add an empty array
to the
`vertices` variable, which will laer be returned from the function.
| ```
var verticesOfPolygon = vertices[polygonId++] = [];
_(polygon).each(function(_vertex){
``` |

- For each vertex:
- Resolve identical vertices in different polygons to the same object by finding previously processed vertices based on their (x, y) coordinate values.
| ```
var vertexLocation = location(_vertex);
var vertex = vertices[vertexLocation];
if(!vertex)
``` |

- Create the vertex object if it doesn't exist.
| ```
vertex = vertices[vertexLocation] = {
x: _vertex.x,
y: _vertex.y,
memberships: []
};
``` |

- Add a membership for each instance of the vertex.
| ```
vertex.memberships.push({
polygonId: polygonId,
vertexId: vertexId
});
``` |

- Increment the
`vertexId` counter.
| ```
vertexId++;
});
});
return vertices;
};
var quadstream = (function(){
``` |

Arguments: `vertices` The preprocessed vertices of the input polygon set. An array of objects with:`x` `y` `memberships` An array of objects with:`polygonId` `vertexId`
`fileDepth` Is an integer that defines the number of quadtree levels traversed for defining the contents of each file.`maxLevel` The maximum quadtree level to partition vertices into.`bounds` The bounding box to use for the top-level quadtree node, an object with properties:`x` ,`y` ,`width` , and`height` .- Each vertex in
`vertices` must fall within this rectangle.
| ` return function(vertices, fileDepth, maxLevel, bounds){` |

- Keys: spot addresses
- of the form
`level+"_"+i+"_"j`
- of the form
- Values: vertex objects
| ` var spots = {};` |

| ```
var spotAddress = function(level, i, j){
return [level,i,j].join('_');
};
``` |

| ```
var addressOfVertex = function(level, x, y){
var gridSideLength = Math.pow(2, level);
var normalizedX = (x - bounds.x) / bounds.width;
var normalizedY = (y - bounds.y) / bounds.height;
var i = Math.floor(normalizedX * gridSideLength);
var j = Math.floor(normalizedY * gridSideLength);
return spotAddress(level, i, j);
};
``` |

| ```
var stream = function(vertex){
for(var level = 0; level < maxLevel; level++){
var vertexAddress = addressOfVertex(level, vertex.x, vertex.y);
``` |

- If the spot in which the vertex falls at the current level is occupied,
| ```
if(spots[vertexAddress]){
continue;
``` |

- Then go down another level in search of an empty spot.
| ```
}
else
{
``` |

- Otherwise,
- Stuff the empty spot with this vertex and stop looking.
| ```
spots[vertexAddress] = vertex;
break;
}
}
};
``` |

Calling - Except in the case that adjacent vertices are closer
than the maximum resolution of the quadtree determined
by
`maxLevel` .
Conceptually, the tree contains nodes with: `x` ,`y` `memberships` `polygonId` `vertexId` - Ascending
`vertexId` values define order of traversal for drawing the polygons later.
- Ascending
`level` ,`i` ,`j` `children` - Can be computed by looking up nodes that match the following:
`(level + 1, 2 * i , 2 * j)` `(level + 1, 2 * i + 1 , 2 * j)` `(level + 1, 2 * i , 2 * j + 1)` `(level + 1, 2 * i + 1 , 2 * j + 1)`
- Can be computed by looking up nodes that match the following:
| ```
var streamAll = function(vertices){
_(vertices).each(stream);
};
var criticalVertices = function(){
``` |

Select vertices that close gap. | ` return _(vertices).filter(function(vertex){` |

Assume the containing polygon is also a polygon. This assures that vertices along the outside border
between two adjacent polygons `a` `b` - The outer polygon that contains all the others.
| ```
vertex.memberships.length > 2;
});
}
var streamCriticalVertices = function(){
streamAll(criticalVertices());
};
var streamExtremeVertices = function(){
``` |

Find vertices that define polygon bounding boxes. This is so clients can build bounding boxes from the vertices that are in file "1". Also at this stage, store the bounding box of the overall tree. | ```
};
var streamOtherVertices = function(){
``` |

If | ```
streamAll(vertices);
};
var getVerticesForFile = function(file_level, file_i, file_j){
``` |

Save on object creation by re-using an empty array reference - For base case of recursion, so used often
- in O(n)) where n is the number of .
| ```
var emptyArray = [];
var recurse = function(level, i, j){
var vertex = spots[spotAddress(level, i, j)];
``` |

Include all subtrees | ```
var vertices = [];
if( file_level === 0 )
? [vertex] : [];
if(vertex && level < file_level + fileDepth){
vertices.push( recurse(level + 1, 2 * i , 2 * j));
vertices.push( recurse(level + 1, 2 * i + 1 , 2 * j));
vertices.push( recurse(level + 1, 2 * i , 2 * j + 1));
vertices.push( recurse(level + 1, 2 * i + 1 , 2 * j + 1));
return vertices;
}
else
return emptyArray;
};
recurse(0, 0, 0);
};
var buildFiles = function(){
``` |

- Keys: file names
- Values: Objects to be serialized as JSON
| ```
var files = {}
return files;
}
``` |

Assumption: it's all in memory. | ```
streamCriticalVertices();
streamExtremeVertices();
streamOtherVertices();
return buildFiles();
}
})();
``` |