1 /**
  2  * @namespace global
  3  */
  4 var URBGEN = URBGEN || {};
  5 /**
  6  * Represents a point. If no x, y and z are specified, the point will have
  7  * coordinates (0, 0, 0).
  8  * @constructor
  9  * @param {number} x - The x coordinate of the point.
 10  * @param {number} y - The y coordinate of the point.
 11  * @param {number} y - The y coordinate of the point.
 12  */
 13 URBGEN.Point = function (x, y, z) {
 14     /**
 15      * This Point's x coordinate.
 16      * @type number
 17      */
 18     this.x = x || 0;
 19     /**
 20      * This Point's y coordinate.
 21      * @type number
 22      */
 23     this.y = y || 0;
 24     /**
 25      * This Point's z coordinate.
 26      * @type number
 27      */
 28     this.z = z || 0;
 29     /**
 30      * This point's adjacent points in the order: above, left, right, below. A
 31      * value of 0 indicates that this point has no adjacent point in that
 32      * direction.
 33      * @type URBGEN.Point[]
 34      */
 35     this.neighbors = [0, 0, 0, 0];
 36 };
 37 /**
 38  * Sets this points x, y and z coordinates to those of the specified Point.
 39  * @param {URBGEN.Point} point - The Point providing the values to set.
 40  */
 41 URBGEN.Point.prototype.setValues = function (point) {
 42     this.x = point.x;
 43     this.y = point.y;
 44     this.z = point.z;
 45 };
 46 /**
 47  * Defines a polygon.
 48  * @constructor
 49  * @param {URBGEN.Point} p0 - the top left corner of the polygon.
 50  * @param {URBGEN.Point} p1 - the top right corner of the polygon.
 51  * @param {URBGEN.Point} p2 - the bottom left corner of the polygon.
 52  * @param {URBGEN.Point} p3 - the bottom right corner of the polygon.
 53  */
 54 URBGEN.Poly = function (p0, p1, p2, p3) {
 55     /**
 56      * This polygon's corners, in the order: topleft, topright, bottomleft,
 57      * bottomright.
 58      * @type URBGEN.Point[]
 59      */
 60     this.corners = [p0, p1, p2, p3];
 61     /**
 62      * The lengths of this polygon's edges, in the order: top, right, left,
 63      * bottom.
 64      * @type number[]
 65      */
 66     this.edgeLengths = [
 67         URBGEN.Util.getLineSegmentLength(this.corners[0], this.corners[
 68             1]),
 69         URBGEN.Util.getLineSegmentLength(this.corners[1], this.corners[
 70             3]),
 71         URBGEN.Util.getLineSegmentLength(this.corners[0], this.corners[
 72             2]),
 73         URBGEN.Util.getLineSegmentLength(this.corners[2], this.corners[
 74             3])
 75     ];
 76     /**
 77      * The vertical angle of this polygon's grid.
 78      * @type number
 79      */
 80     this.gridAngle = undefined;
 81 };
 82 /**
 83  * Sets this polygon's grid angle.
 84  * @param {number} random - A random number between 0 - 1 (inclusive).
 85  */
 86 URBGEN.Poly.prototype.setGridAngle = function (random) {
 87     var start = URBGEN.Util.linearInterpolate(this.corners[0], this.corners[
 88             2],
 89         0.5);
 90     var end = URBGEN.Util.linearInterpolate(this.corners[1], this.corners[3],
 91         random * 0.5 + 0.2);
 92     this.gridAngle = URBGEN.Util.getAngle(start, end);
 93 };
 94 /**
 95  * Sets this polygon's corners as neighbors so that there are no
 96  * extra points included on any edge.
 97  */
 98 URBGEN.Poly.prototype.makeSimple = function () {
 99     this.corners[0].neighbors[2] = this.corners[2];
100     this.corners[0].neighbors[3] = this.corners[1];
101     this.corners[1].neighbors[1] = this.corners[0];
102     this.corners[1].neighbors[2] = this.corners[3];
103     this.corners[2].neighbors[0] = this.corners[0];
104     this.corners[2].neighbors[3] = this.corners[3];
105     this.corners[3].neighbors[0] = this.corners[1];
106     this.corners[3].neighbors[1] = this.corners[2];
107 };
108 /**
109  * Represents a 3D geometry.
110  * @constructor
111  */
112 URBGEN.Geometry = function () {
113   /**
114    * This geometry's vertices, stored as a 2D array. Each element is an array
115    * of type [x, y, z]. For example, [[2, 2, 5], [4, 6, 7]] represents two
116    * vertices with coords (2, 2, 5) and (4, 6, 7) respectively.
117    * @type number[][]
118    */
119   this.vertices = [];
120   /**
121    * This geometry's faces, stored as a 2D array. Each element is an array of
122    * type [i, j, k], where i, j and k are the indices of three vertices that
123    * define a 3 sided face.
124    * @type number[][]
125    */
126   this.faces = [];
127 };
128 /**
129  * Represents a city element.
130  * @constructor
131  * @param {URBGEN.Poly} poly - The polygon representing this city element's
132  *     footprint.
133  * @param {number} height - The height of this city element.
134  */
135 URBGEN.CityElement = function (poly, height) {
136     /**
137      * The footprint of this city element.
138      * @type URBGEN.Poly
139      */
140     this.poly = poly;
141     /**
142      * This city element's height. Defaults to 0.
143      * @type number
144      */
145     this.height = height || 0;
146     /**
147      * This city element's area.
148      * @type number
149      */
150      this.area = URBGEN.Util.areaPoly(this.poly);
151 };
152 /**
153  * Represents a plot.
154  * @constructor
155  * @extends URBGEN.CityElement
156  * @param {URBGEN.Poly} poly - This plot's polygon.
157  */
158 URBGEN.CityElement.Plot = function (poly) {
159     URBGEN.CityElement.call(this, poly);
160 };
161 URBGEN.CityElement.Plot.prototype = Object
162     .create(URBGEN.CityElement.prototype);
163 URBGEN.CityElement.Plot.prototype.constructor = URBGEN.CityElement.Plot;
164 /**
165  * Represents a block.
166  * @constructor
167  * @extends URBGEN.CityElement
168  * @param {URBGEN.Poly} poly - This block's outer polygon, including any
169  *     space for streets and sidewalks.
170  * @param {number} streetWidth - The width of the streets surrounding this block.
171  */
172 URBGEN.CityElement.Block = function (poly, streetWidth) {
173     URBGEN.CityElement.call(this, poly);
174     /**
175      * This block's street width.
176      * @type number
177      */
178     this.streetWidth = streetWidth;
179     /**
180      * This block's inner polygon, exluding space for streets and sidewalks.
181      * @type URBGEN.Poly
182      */
183     this.innerPoly = undefined;
184     /**
185      * This block's plots.
186      * @type URBGEN.CityElement.Plot[]
187      */
188     this.plots = [];
189     // Sets this block's inner polygon.
190     this.setInnerPoly(streetWidth);
191 };
192 URBGEN.CityElement.Block.prototype = Object
193     .create(URBGEN.CityElement.prototype);
194 URBGEN.CityElement.Block.prototype.constructor = URBGEN.CityElement.Block;
195 /**
196  * Sets this block's inner polygon. This is the polygon that this block's plots
197  * lie within, excluding any space for streets and sidewalks.
198  */
199 URBGEN.CityElement.Block.prototype.setInnerPoly = function () {
200     this.innerPoly = URBGEN.Util
201         .insetPoly(this.poly, this.streetWidth / 2);
202     this.innerPoly.makeSimple();
203 };
204 /**
205  * Represents a city.
206  * @constructor
207  * @extends URBGEN.CityElement
208  * @param {URBGEN.Poly} poly - The footprint of this city.
209  */
210 URBGEN.CityElement.City = function (poly) {
211     URBGEN.CityElement.call(this, poly);
212     /**
213      * An array of points, each with up to four neighbors, representing this
214      * city's road network.
215      * @type URBGEN.Point[]
216      */
217     this.roads = [];
218     /**
219      * This city's blocks.
220      * @type URBGEN.CityElement.Block[]
221      */
222     this.blocks = [];
223     /**
224      * This city's geometry.
225      * @type URBGEN.Geometry
226      */
227     this.geometry = new URBGEN.Geometry();
228 };
229 URBGEN.CityElement.City.prototype = Object
230     .create(URBGEN.CityElement.prototype);
231 URBGEN.CityElement.City.prototype.constructor = URBGEN.CityElement.City;
232 /**
233  * Returns an array of the plots of this city.
234  * @return URBGEN.CityElement.Plot[] The plots of this city.
235  */
236 URBGEN.CityElement.City.prototype.getPlots = function () {
237     var plots = [];
238     for(var i = 0; i < this.blocks.length; i++) {
239         plots = plots.concat(this.blocks[i].plots);
240     }
241     return plots;
242 };
243 /**
244  * Represents a generator.
245  * @constructor
246  */
247 URBGEN.Generator = function () {
248     /**
249      * This generator's horizontal builder.
250      * @type URBGEN.Builder.HorizontalBuilder
251      */
252     this.horizontalBuilder = new URBGEN.Builder.HorizontalBuilder(this);
253     /**
254      * This generator's vertical builder.
255      * @type URBGEN.Builder.VerticalBuilder
256      */
257     this.verticalBuilder = new URBGEN.Builder.VerticalBuilder(this);
258     /**
259      * This generator's plot builder.
260      * @type URBGEN.Builder.PlotBuilder
261      */
262     this.plotBuilder = new URBGEN.Builder.PlotBuilder(this);
263     /**
264      * This generator's current builder.
265      * @type URBGEN.Builder
266      */
267     this.builder = undefined;
268     /**
269      * This generator's director.
270      * @type URBGEN.Director
271      */
272     this.director = new URBGEN.Director();
273     /**
274      * This generator's current city.
275      * @type URBGEN.Ciy
276      */
277     this.city = undefined;
278     /**
279      * This generator's random number generator.
280      * @type URBGEN.Math.Random
281      */
282     this.random = new URBGEN.Math.Random();
283     /**
284      * The polygon's of this generator's current city.
285      * @type URBGEN.Poly[]
286      */
287     this.cityPolys = [];
288     /**
289      * This generator's global angle.
290      * @type number
291      */
292     this.globalAngle = undefined;
293     /**
294      * This generator's random number seed.
295      * @type number
296      */
297     this.randomSeed = undefined;
298     /**
299      * This generator's regularity1, used to determine start point of new roads.
300      * @type number
301      */
302     this.regularity1 = undefined;
303     /**
304      * This generator's regularity2, used to determine end point of new roads.
305      * @type number
306      */
307     this.regularity2 = undefined;
308     /**
309      * This generator's local grid threshold.
310      * @type number
311      */
312     this.localGrids = undefined;
313     /**
314      * This generator's minimum block size.
315      * @type number
316      */
317     this.blockSize = undefined;
318     /**
319      * This generator's city's width.
320      * @type number
321      */
322     this.cityWidth = undefined;
323     /**
324      * This generator's city's depth.
325      * @type number
326      */
327     this.cityDepth = undefined;
328     /**
329      * This generator's city's street width.
330      * @type number
331      */
332     this.streetWidth = undefined;
333     /**
334      * This generator's through road snap distance.
335      * @type number
336      */
337     this.throughRoads = undefined;
338 };
339 /**
340  * Sets this generator's parameters. If any paramaters in the cityParmas object
341  * are undefined, sets those parameters to random values.
342  * @param {Object} cityParams - The paramters this generator should use to
343  *     generate a city.
344  */
345 URBGEN.Generator.prototype.setParams = function (cityParams) {
346     if(cityParams === undefined) {
347         cityParams = {};
348     }
349     if((0 > cityParams.localGrids) || (1 < cityParams.localGrids) || (
350         cityParams.localGrids === undefined)) {
351         this.localGrids = Math.random();
352     } else {
353         this.localGrids = cityParams.localGrids;
354     }
355     if((0 > cityParams.randomSeed) || (1 < cityParams.randomSeed) || (
356         cityParams.randomSeed === undefined)) {
357         this.randomSeed = Math.random();
358     } else {
359         this.randomSeed = cityParams.randomSeed;
360     }
361     if((0 > cityParams.globalAngle) || (1 < cityParams.globalAngle) || (
362         cityParams.globalAngle === undefined)) {
363         this.globalAngle = Math.random();
364     } else {
365         this.globalAngle = cityParams.globalAngle;
366     }
367     if((0 > cityParams.throughRoads) || (URBGEN.Constants.MAX_THROUGH_ROADS <
368         cityParams.throughRoads) || (cityParams.throughRoads ===
369         undefined)) {
370         this.throughRoads = Math.random() * URBGEN.Constants.MAX_THROUGH_ROADS;
371     } else {
372         this.throughRoads = cityParams.throughRoads;
373     }
374     this.blockSize = cityParams.blockSize || Math.random() * (URBGEN.Constants
375             .MAX_BLOCK_SIZE - URBGEN.Constants.MIN_BLOCK_SIZE) + URBGEN.Constants
376         .MIN_BLOCK_SIZE;
377     this.cityWidth = cityParams.cityWidth || Math.random() * (URBGEN.Constants
378             .MAX_CITY_WIDTH - URBGEN.Constants.MIN_CITY_WIDTH) + URBGEN.Constants
379         .MIN_CITY_WIDTH;
380     this.cityDepth = cityParams.cityDepth || Math.random() * (URBGEN.Constants
381             .MAX_CITY_DEPTH - URBGEN.Constants.MIN_CITY_DEPTH) + URBGEN.Constants
382         .MIN_CITY_DEPTH;
383     this.streetWidth = cityParams.streetWidth || Math.random() * (URBGEN.Constants
384             .MAX_STREET_WIDTH - URBGEN.Constants.MIN_STREET_WIDTH) + URBGEN
385         .Constants.MIN_STREET_WIDTH;
386 };
387 /**
388  * Returns this generator's current city parameters.
389  * @return {Object} The parameters.
390  */
391 URBGEN.Generator.prototype.getParams = function () {
392     var cityParams = {
393         localGrids: this.localGrids,
394         randomSeed: this.randomSeed,
395         globalAngle: this.globalAngle,
396         blockSize: this.blockSize,
397         cityWidth: this.cityWidth,
398         cityDepth: this.cityDepth,
399         throughRoads: this.throughRoads,
400         streetWidth: this.streetWidth
401     };
402     return cityParams;
403 };
404 /**
405  * Initializes this generator.
406  * @throws {URBGEN.Exception.InvalidParamException}
407  */
408 URBGEN.Generator.prototype.init = function () {
409     if(isNaN(this.localGrids) || isNaN(this.randomSeed) || isNaN(this.globalAngle) ||
410         isNaN(this.blockSize) || isNaN(this.cityWidth) || isNaN(this.cityDepth) ||
411         isNaN(this.throughRoads) || isNaN(this.streetWidth)) {
412         throw new URBGEN.Exception.InvalidParamException();
413     }
414     // Initialise the polygon array
415     this.cityPolys = [];
416     // Seed the random number generator
417     this.random.seed = this.randomSeed;
418     // Build the initial polygon
419     var topLeft = new URBGEN.Point(0, 0, 0);
420     var topRight = new URBGEN.Point(this.cityWidth, 0, 0);
421     var bottomLeft = new URBGEN.Point(1, this.cityDepth, 0);
422     var bottomRight = new URBGEN.Point(this.cityWidth - 1, this.cityDepth,
423         0);
424     var poly = new URBGEN.Poly(topLeft, topRight, bottomLeft, bottomRight);
425     // Instantiate a new city
426     this.city = new URBGEN.CityElement.City(poly);
427     poly.makeSimple();
428     this.cityPolys.push(poly);
429     // Add the corners to the nodes graph
430     this.nodes = [topLeft, topRight, bottomLeft, bottomRight];
431     // Set the regularity params
432     this.regularity1 = this.globalAngle * (URBGEN.Constants.MAX_REGULARITY -
433         URBGEN.Constants.MIN_REGULARITY) + URBGEN.Constants.MIN_REGULARITY;
434     this.regularity2 = URBGEN.Constants.MAX_REGULARITY - this.globalAngle *
435         (URBGEN.Constants.MAX_REGULARITY - URBGEN.Constants.MIN_REGULARITY);
436 };
437 /**
438  * Recursively processes an array of polygons.
439  * @param {URBGEN.Point[]} polys - The array of polygons to be processed.
440  * @return {URBGEN.Poly[]} The new polygons.
441  */
442 URBGEN.Generator.prototype.processPolyRecursively = function (polys) {
443     var newPolys = [];
444     for(var i = 0; i < polys.length; i++) {
445         newPolys = newPolys.concat(this.processPoly(polys[i]));
446     }
447     if(polys.length !== newPolys.length) {
448         return this.processPolyRecursively(newPolys);
449     }
450     return newPolys;
451 };
452 /**
453  * Generates a city.
454  * @param {Object} cityParams - The parameters that should be used to generate
455  *     the city.
456  * @return {URBGEN.City} The generated city.
457  */
458 URBGEN.Generator.prototype.generate = function (cityParams) {
459     this.setParams(cityParams);
460     this.init();
461     // Get the initial polygons
462     this.cityPolys = this.processPolyRecursively(this.cityPolys);
463     // Build the city blocks.
464     for(var i = 0; i < this.cityPolys.length; i++) {
465         //TODO this doesn't add every node yet
466         this.city.roads.push(this.cityPolys[i].corners[0]);
467         var poly = this.cityPolys[i];
468         var block = new URBGEN.CityElement.Block(poly, this.streetWidth);
469         this.city.blocks.push(block);
470     }
471     // Build the plots
472     for(var j = 0; j < this.city.blocks.length; j++) {
473         var plots = [];
474         this.plotBuilder.poly = this.city.blocks[j].innerPoly;
475         var plotPolys = this.director.execute(this.plotBuilder);
476         for(var k = 0; k < plotPolys.length; k++) {
477             var plot = new URBGEN.CityElement.Plot(plotPolys[k]);
478             plot.height = this.random.next() * 20 + 20;
479             plots.push(plot);
480         }
481         this.city.blocks[j].plots = plots;
482     }
483     // Build the 3D geometry
484     this.buildGeometry();
485     //return the city
486     return this.city;
487 };
488 /**
489  * Builds a 3D geometry for this generator's current city.
490  */
491 URBGEN.Generator.prototype.buildGeometry = function () {
492     var vertices = this.city.geometry.vertices;
493     var faces = this.city.geometry.faces;
494     var plots = this.city.getPlots();
495     for(var i = 0; i < plots.length; i++) {
496         var building = plots[i].poly;
497         var height = plots[i].height;
498         for(var j = 0; j < building.corners.length; j++) {
499             var vertexTop = building.corners[j];
500             vertices.push([vertexTop.x, vertexTop.y, height]);
501         }
502         for(var k = 0; k < building.corners.length; k++) {
503             var vertexBottom = building.corners[k];
504             vertices.push([vertexBottom.x, vertexBottom.y, 0]);
505         }
506     }
507     for(var l = 1; l < vertices.length + 1; l += 8) {
508         faces.push([l, l + 1, l + 2]);
509         faces.push([l + 2, l + 1, l + 3]);
510         faces.push([l, l + 1, l + 4]);
511         faces.push([l + 4, l + 1, l + 5]);
512         faces.push([l + 1, l + 3, l + 5]);
513         faces.push([l + 5, l + 3, l + 7]);
514         faces.push([l + 3, l + 2, l + 7]);
515         faces.push([l + 7, l + 2, l + 6]);
516         faces.push([l + 2, l, l + 6]);
517         faces.push([l + 6, l, l + 4]);
518     }
519 };
520 /**
521  * Processes a polygon. If a polygon cannot be processed, it is returned.
522  * @param {URBGEN.Poly} poly - The polygon to process.
523  * @return {URBGEN.Poly[]} The new polygons, or the original poly.
524  */
525 URBGEN.Generator.prototype.processPoly = function (poly) {
526     if(URBGEN.Util.areaPoly(poly) < this.blockSize) {
527         return [poly];
528     }
529     this.prepare(poly);
530     try {
531         var newPolys = this.director.execute(this.builder, this.center);
532         return newPolys;
533     } catch(error) {
534         if(error instanceof URBGEN.Exception.EdgeTooShortException) {
535             return [poly];
536         }
537     }
538 };
539 /**
540  * Prepares to process a polygon by loading the appropriate Builder.
541  * @param {URBGEN.Poly} poly - The polygon being prepared for.
542  */
543 URBGEN.Generator.prototype.prepare = function (poly) {
544     // Set the correct builder
545     var horizontalSides = poly.edgeLengths[0] + poly.edgeLengths[3];
546     var verticalSides = poly.edgeLengths[1] + poly.edgeLengths[2];
547     if(verticalSides > horizontalSides) {
548         this.builder = this.horizontalBuilder;
549     } else {
550         this.builder = this.verticalBuilder;
551     }
552     this.builder.poly = poly;
553 };
554 /**
555  * Returns a THREE.Shape representing the specified poly.
556  * @param {URBGEN.Poly} poly - The poly providing the coordinates.
557  * @param {THREE.Shape} shape - The shape to have its coordinates set.
558  * @return {THREE.Shape} The shape with coordinates set.
559  */
560 URBGEN.Generator.prototype.getThreeJSGeometry = function (cityElement) {
561     if (!(cityElement instanceof Array)) {
562       cityElement = [cityElement];
563     }
564     var geometry = new THREE.Geometry();
565     for (var i = 0; i < cityElement.length; i++) {
566         var shape = new THREE.Shape();
567         var poly = cityElement[i].poly;
568         shape.moveTo(poly.corners[0].x, poly.corners[0].y);
569         shape.lineTo(poly.corners[1].x, poly.corners[1].y);
570         shape.lineTo(poly.corners[3].x, poly.corners[3].y);
571         shape.lineTo(poly.corners[2].x, poly.corners[2].y);
572         shape.lineTo(poly.corners[0].x, poly.corners[0].y);
573         var extrusionSettings = {
574             bevelEnabled: false,
575             amount: cityElement[i].height
576         };
577         var geom = new THREE.ExtrudeGeometry(shape, extrusionSettings);
578         geometry.merge(geom);
579     }
580     return geometry;
581 };
582 /**
583  * Returns a string containing vertex and face data in the Wavefront.OBJ file
584  * format. The geometry returned represents bounding boxes for each plot in
585  * this generator's current city.
586  * @return {string} The OBJ data for this generator's current city.
587  */
588 URBGEN.Generator.prototype.OBJData = function () {
589     var geom = this.city.geometry;
590     var verts = geom.vertices;
591     var faces = geom.faces;
592     var output = "";
593     for(var v = 0; v < verts.length; v++) {
594         output += "v " + verts[v][0] + " " + verts[v][1] + " " + verts[v][2] +
595             '\r\n';
596     }
597     for(var f = 0; f < faces.length; f++) {
598         output += "f " + faces[f][0] + " " + faces[f][1] + " " + faces[f][2] +
599             '\r\n';
600     }
601     return output;
602 };
603 /**
604  * Returns a string containing the parameters used to generate this generator's
605  * current city.
606  * @return {string} The parameters used to generate this generator's current city.
607  */
608 URBGEN.Generator.prototype.paramData = function () {
609     var output = ("globalAngle: " + this.globalAngle + ",\r\n" +
610         "blockSize: " + this.blockSize + ",\r\n" + "cityWidth: " + this.cityWidth +
611         ",\r\n" + "cityDepth: " + this.cityDepth + ",\r\n" +
612         "streetWidth: " + this.streetWidth + ",\r\n" + "localGrids: " +
613         this.localGrids + ",\r\n" + "randomSeed: " + this.randomSeed +
614         ",\r\n" + "throughRoads: " + this.throughRoads);
615     return output;
616 };
617 
618 //URBGEN.Builder
619 
620 /**
621  * Represents a builder.
622  * @constructor
623  * @param {URBGEN.Generator} generator - The generator that owns this builder.
624  */
625 URBGEN.Builder = function (generator) {
626     /**
627      * The generator that owns this builder.
628      * @type URBGEN.Generator
629      */
630     this.generator = generator;
631     /**
632      * The current polygon this builder is operating on.
633      * @type URBGEN.Poly
634      */
635     this.poly = undefined;
636     /**
637      * Ths origin point for this builder's dividing line.
638      * @type URBGEN.Point
639      */
640     this.origin = undefined;
641     /**
642      * Ths end point for this builder's dividing line.
643      * @type URBGEN.Point
644      */
645     this.endPoint = undefined;
646     /**
647      * The points this builder will use to build new polygons.
648      * @type URBGEN.Point[]
649      */
650     this.newPoints = [];
651 };
652 /**
653  * Returns an array of new polygons created from this builder's current points.
654  * @return {URBGEN.Poly[]} The new polygons.
655  * @throws {URBGEN.Exception.EdgeTooShortException}
656  */
657 URBGEN.Builder.prototype.buildPolys = function () {
658     var polys = [];
659     for(var i = 0; i < this.newPoints.length; i++) {
660         // Build the new polygon
661         var points = this.newPoints[i];
662         var poly = new URBGEN.Poly(points[0], points[1], points[2], points[
663             3]);
664         // Set the grid angle of the new polygon, if needed
665         var localGridThreshold = this.generator.localGrids * this.generator
666             .city.area;
667         if(URBGEN.Util.areaPoly(poly) < localGridThreshold) {
668             if(this.poly.gridAngle === undefined) {
669                 poly.setGridAngle(this.generator.random.next());
670             } else {
671                 poly.gridAngle = this.poly.gridAngle;
672             }
673         }
674         // Add the polygon
675         polys.push(poly);
676     }
677     for(var j = 0; j < polys.length; j++) {
678         for(var k = 0; k < polys[j].edgeLengths.length; k++) {
679             var length = polys[j].edgeLengths[k];
680             if(length < this.minEdgeLength) {
681                 throw new URBGEN.Exception.EdgeTooShortException();
682             }
683         }
684     }
685     return polys;
686 };
687 /**
688  * Sets this builder's origin and end points for the new dividing line.
689  * @throws {URBGEN.Exception.EdgeTooShortException}
690  */
691 URBGEN.Builder.prototype.setUp = function () {
692     var edgeStart = this.poly.corners[0];
693     var edgeEnd = this.poly.corners[this.corners[0]];
694     var edgeLength = URBGEN.Util.getLineSegmentLength(edgeStart, edgeEnd);
695     var origin;
696     var endPoint;
697     if(this.poly.gridAngle === undefined) {
698         origin = this.pointByRValue(edgeStart, edgeEnd,
699             this.generator.regularity1);
700         this.origin = this.addPointToPath(origin, edgeStart, edgeEnd);
701         edgeStart = this.poly.corners[this.corners[1]];
702         edgeEnd = this.poly.corners[3];
703         edgeLength = URBGEN.Util.getLineSegmentLength(edgeStart, edgeEnd);
704         endPoint = this.pointByRValue(edgeStart, edgeEnd,
705             this.generator.regularity2);
706         this.endPoint = this.addPointToPath(endPoint, edgeStart, edgeEnd);
707     } else {
708         origin = this.pointByRValue(edgeStart, edgeEnd,
709             this.generator.regularity1);
710         this.origin = this.addPointToPath(origin, edgeStart, edgeEnd);
711         edgeStart = this.poly.corners[this.corners[1]];
712         edgeEnd = this.poly.corners[3];
713         endPoint = this.pointByAngle(edgeStart, edgeEnd, this.getGridAngle());
714         this.endPoint = this.addPointToPath(endPoint, edgeStart, edgeEnd);
715     }
716 };
717 /**
718  * Returns the point at which a line at the specified angle intersects with the
719  * edge defined by the specified start and end points. If this point does not lie
720  * on the legal part of the edge (defined as a region starting at the minimum
721  * edge length from the start point and ending at the minium edge length before
722  * the end point) then the closest point in the legal region is returned.
723  * @param {URBGEN.Point} edgeStart - The start point of the edge.
724  * @param {URBGEN.Point} edgeEnd - The end point of the edge.
725  * @param {number} angle - The angle in radians of the intersecting line.
726  * @return {URBGEN.Point} The closest legal point at which the intersecting line
727  *     meets the edge.
728  * @throws {URBGEN.Exception.EdgeTooShortException}
729  */
730 URBGEN.Builder.prototype.pointByAngle = function (edgeStart, edgeEnd, angle) {
731     // Get the edge's length
732     var length = URBGEN.Util.getLineSegmentLength(edgeStart, edgeEnd);
733     // Throw an error if the edge is too short
734     if(length <= URBGEN.Constants.MIN_EDGE_LENGTH) {
735         throw new URBGEN.Exception.EdgeTooShortException();
736     }
737     var minR = URBGEN.Constants.MIN_EDGE_LENGTH / length;
738     var edgeAngle = URBGEN.Util.getAngle(edgeStart, edgeEnd);
739     var point = URBGEN.Util.getIntersect(edgeStart, edgeAngle, this.origin,
740         angle);
741     var r = URBGEN.Util.getPointAsRatio(point, edgeStart, edgeEnd);
742     if(r < minR)
743         r = minR;
744     if(r > 1 - minR)
745         r = 1 - minR;
746     return this.pointByRValue(edgeStart, edgeEnd, r);
747 };
748 /**
749  * Returns the point represented by the specified r value on the edge defined by
750  * the specified start and end points. If this point does not lie on the legal
751  * part of the edge (defined as a region starting at the minimum edge length from
752  * the start point and ending at the minium edge length before the end point) then
753  * the closest point in the legal region is returned.
754  * @param {URBGEN.Point} edgeStart - The start point of the edge.
755  * @param {URBGEN.Point} edgeEnd - The end point of the edge.
756  * @param {number} r - The r value of the new point.
757  * @return {URBGEN.Point} The closest legal point at which the intersecting line
758  *     meets the edge.
759  * @throws {URBGEN.Exception.EdgeTooShortException}
760  */
761 URBGEN.Builder.prototype.pointByRValue = function (edgeStart, edgeEnd, r) {
762     // Get the edge's length
763     var length = URBGEN.Util.getLineSegmentLength(edgeStart, edgeEnd);
764     // Throw an error if the edge is too short
765     if(length <= URBGEN.Constants.MIN_EDGE_LENGTH) {
766         throw new URBGEN.Exception.EdgeTooShortException();
767     }
768     // Work out the legal part of the edge as a range (0 < range < 1)
769     var minR = URBGEN.Constants.MIN_EDGE_LENGTH / length;
770     var range = 1 - 2 * minR;
771     // Use the regularity1 to find a point on this range
772     var pointR = range * r + minR;
773     // Get the actual point
774     var point = URBGEN.Util.linearInterpolate(edgeStart, edgeEnd, pointR);
775     return point;
776 };
777 /**
778  * Adds the specified point to the edge with the specified start and end points.
779  * If there is already a point on this edge within the current throughRoad
780  * distance, returns that point. Otherwise, finds the new point's neighbors on
781  * the edge, sets the neighbor relations to include the new point, and returns
782  * that point.
783  * @param {URBGEN.Point} point - The point to be added to the edge.
784  * @param {URBGEN.Point} edgeStart - The start point of the edge.
785  * @param {URBGEN.Point} edgeEnd - The end point of the edge.
786  * @return {URBGEN.Point} A point within the throughRoad distance on the edge,
787  *     or the originally specified point (with neighbor relations set).
788  */
789 URBGEN.Builder.prototype.addPointToPath = function (point, edgeStart, edgeEnd) {
790     var path = URBGEN.Util.getDirectedPath(edgeStart, edgeEnd, this.direction);
791     var distance = this.generator.throughRoads;
792     var nearPoint = URBGEN.Util.checkNearPoints(point, path, distance,
793         false);
794     if(nearPoint === point) {
795         var neighbors = URBGEN.Util.getNeighbors(point, path);
796         URBGEN.Util.insertPoint(point, neighbors.prev, neighbors.nxt);
797     }
798     return nearPoint;
799 };
800 /**
801  * Represents a horizontal builder.
802  * @constructor
803  * @extends URBGEN.Builder
804  * @param {URBGEN.Generator} generator - The generator that owns this builder.
805  */
806 URBGEN.Builder.HorizontalBuilder = function (generator) {
807     URBGEN.Builder.call(this, generator);
808     /**
809      * The corner indices this builder uses to select edges.
810      * @type number[]
811      */
812     this.corners = [2, 1];
813     /**
814      * This builder's direction index.
815      * @type number
816      */
817     this.direction = 2;
818     /**
819      * The minimum length of an edge produced by this builder.
820      * @type number
821      */
822     this.minEdgeLength = URBGEN.Constants.MIN_EDGE_LENGTH;
823 };
824 URBGEN.Builder.HorizontalBuilder.prototype = Object
825     .create(URBGEN.Builder.prototype);
826 URBGEN.Builder.HorizontalBuilder.prototype.constructor = URBGEN.Builder.HorizontalBuilder;
827 /**
828  * Returns this builder's current poly's grid angle.
829  * @return {number} The grid angle.
830  */
831 URBGEN.Builder.HorizontalBuilder.prototype.getGridAngle = function () {
832     return this.poly.gridAngle;
833 };
834 /**
835  * Sets this builder's current new points.
836  */
837 URBGEN.Builder.HorizontalBuilder.prototype.setNewPoints = function () {
838     this.origin.neighbors[3] = this.endPoint;
839     this.endPoint.neighbors[1] = this.origin;
840     this.newPoints = [
841         [this.poly.corners[0], this.poly.corners[1], this.origin,
842             this.endPoint
843         ],
844         [this.origin, this.endPoint, this.poly.corners[2],
845             this.poly.corners[3]
846         ]
847     ];
848 };
849 /**
850  * Represents a vertical builder.
851  * @constructor
852  * @extends URBGEN.Builder
853  * @param {URBGEN.Generator} generator - The generator that owns this builder.
854  */
855 URBGEN.Builder.VerticalBuilder = function (generator) {
856     URBGEN.Builder.call(this, generator);
857     /**
858      * The corner indices this builder uses to select edges.
859      * @type number[]
860      */
861     this.corners = [1, 2];
862     /**
863      * This builder's direction index.
864      * @type number
865      */
866     this.direction = 3;
867     /**
868      * The minimum length of an edge produced by this builder.
869      * @type number
870      */
871     this.minEdgeLength = URBGEN.Constants.MIN_EDGE_LENGTH;
872 };
873 URBGEN.Builder.VerticalBuilder.prototype = Object
874     .create(URBGEN.Builder.prototype);
875 URBGEN.Builder.VerticalBuilder.prototype.constructor = URBGEN.Builder.VerticalBuilder;
876 /**
877  * Returns this builder's current poly's grid angle + 0.5 * Math.PI.
878  * @return {number} The orthogonal grid angle.
879  */
880 URBGEN.Builder.VerticalBuilder.prototype.getGridAngle = function () {
881     return URBGEN.Util.addAngle(this.poly.gridAngle, 0.5);
882 };
883 /**
884  * Sets this builder's current new points
885  */
886 URBGEN.Builder.VerticalBuilder.prototype.setNewPoints = function () {
887     this.origin.neighbors[2] = this.endPoint;
888     this.endPoint.neighbors[0] = this.origin;
889     this.newPoints = [
890         [this.poly.corners[0], this.origin, this.poly.corners[2],
891             this.endPoint
892         ],
893         [this.origin, this.poly.corners[1], this.endPoint,
894             this.poly.corners[3]
895         ]
896     ];
897 };
898 /**
899  * Represents a plot builder.
900  * @constructor
901  * @extends URBGEN.Builder
902  * @param {URBGEN.Generator} generator - The generator that owns this builder.
903  */
904 URBGEN.Builder.PlotBuilder = function (generator) {
905     URBGEN.Builder.call(this, generator);
906     /**
907      * The paths representing the inner edges of the plots produced by this
908      * builder.
909      * @type URBGEN.Point[][]
910      */
911     this.innerPaths = [];
912     /**
913      * The paths representing the outer edges of the plots produced by this
914      * builder.
915      * @type URBGEN.Point[][]
916      */
917     this.outerPaths = [];
918     /**
919      * The minimum length of an edge produced by this builder.
920      * @type number
921      */
922     this.minEdgeLength = 0;
923 };
924 URBGEN.Builder.PlotBuilder.prototype = Object.create(URBGEN.Builder.prototype);
925 URBGEN.Builder.PlotBuilder.prototype.constructor = URBGEN.Builder.PlotBuilder;
926 /**
927  * Sets the inner and outer paths that define this builder's plots.
928  */
929 URBGEN.Builder.PlotBuilder.prototype.setUp = function () {
930     var innerInset = 10;
931     var innerPoly = URBGEN.Util.insetPoly(this.poly, innerInset);
932     innerPoly.makeSimple();
933     // Get the inner edges
934     var innerEdges = [
935         [innerPoly.corners[0], innerPoly.corners[1]],
936         [innerPoly.corners[1], innerPoly.corners[3]],
937         [innerPoly.corners[0], innerPoly.corners[2]],
938         [innerPoly.corners[2], innerPoly.corners[3]]
939     ];
940     // get the outer edges
941     var outerEdges = [
942         [this.poly.corners[0], this.poly.corners[1]],
943         [this.poly.corners[1], this.poly.corners[3]],
944         [this.poly.corners[0], this.poly.corners[2]],
945         [this.poly.corners[2], this.poly.corners[3]],
946     ];
947     // shorter the outer edges to match the inner edges
948     for(var i = 0; i < innerEdges.length; i++) {
949         var angle = URBGEN.Util.getAngle(innerEdges[i][0], innerEdges[i][1]);
950         angle = URBGEN.Util.addAngle(angle, 0.5);
951         var outerAngle = URBGEN.Util.getAngle(outerEdges[i][0],
952             outerEdges[i][1]);
953         var l = URBGEN.Util.getLineSegmentLength(innerEdges[i][0],
954             innerEdges[i][1]);
955         var start = URBGEN.Util.getIntersect(innerEdges[i][0], angle,
956             outerEdges[i][0], outerAngle);
957         var end = URBGEN.Util.linearInterpolateByLength(start,
958             outerEdges[i][1], l);
959         outerEdges[i][0] = start;
960         outerEdges[i][1] = end;
961     }
962     // set neighbor relations of the edge's start and end points
963     var direction = 2;
964     var oppDirection = (direction + 2) % 4;
965     for(var j = 0; j < outerEdges.length; j++) {
966         var p = outerEdges[j][0];
967         var q = outerEdges[j][1];
968         p.neighbors[direction] = q;
969         q.neighbors[oppDirection] = p;
970         if(direction === 2) {
971             direction = 3;
972         } else {
973             direction = 2;
974         }
975         oppDirection = (direction + 2) % 4;
976     }
977     // Get the paths
978     var innerPaths = [];
979     var outerPaths = [];
980     for(var k = 0; k < outerEdges.length; k++) {
981         var length = 10;
982         innerPaths.push(URBGEN.Util.divideLine(innerEdges[k][0],
983             innerEdges[k][1], length));
984         outerPaths.push(URBGEN.Util.divideLine(outerEdges[k][0],
985             outerEdges[k][1], length));
986     }
987     this.innerPaths = innerPaths;
988     this.outerPaths = outerPaths;
989 };
990 /**
991  * Sets this builder's current new points.
992  */
993 URBGEN.Builder.PlotBuilder.prototype.setNewPoints = function () {
994     var newPoints = [];
995     for(var i = 0; i < this.innerPaths.length; i++) {
996         for(var j = 0; j < this.innerPaths[i].length - 1; j++) {
997             newPoints.push([this.outerPaths[i][j], this.outerPaths[i][j + 1],
998                 this.innerPaths[i][j], this.innerPaths[i][j + 1]
999             ]);
1000         }
1001     }
1002     // add the corner plots
1003     newPoints.push([this.poly.corners[0], this.outerPaths[0][0],
1004         this.outerPaths[2][0], this.innerPaths[0][0]
1005     ]);
1006     newPoints
1007         .push([this.outerPaths[0][this.outerPaths[0].length - 1],
1008             this.poly.corners[1], this.innerPaths[1][0],
1009             this.outerPaths[1][0]
1010         ]);
1011     newPoints.push([this.outerPaths[2][this.outerPaths[2].length - 1],
1012         this.innerPaths[2][this.innerPaths[2].length - 1],
1013         this.poly.corners[2], this.outerPaths[3][0]
1014     ]);
1015     newPoints.push([this.innerPaths[1][this.innerPaths[1].length - 1],
1016         this.outerPaths[1][this.outerPaths[1].length - 1],
1017         this.outerPaths[3][this.outerPaths[3].length - 1],
1018         this.poly.corners[3]
1019     ]);
1020 
1021     this.newPoints = newPoints;
1022 };
1023 /**
1024  * Represents a director.
1025  * @constructor
1026  */
1027 URBGEN.Director = function () {
1028 
1029 };
1030 /**
1031  * Invokes the specified builder's build methods.
1032  * @param {URBGEN.Builder} builder - The builder this director should execute on.
1033  * @return {URBGEN.Poly[]} The result of the builder's buildPolys() method.
1034  */
1035 URBGEN.Director.prototype.execute = function (builder) {
1036     builder.setUp();
1037     builder.setNewPoints();
1038     return builder.buildPolys();
1039 };
1040 /**
1041  * @namespace holds utility functions.
1042  */
1043 URBGEN.Util = {};
1044 /**
1045  * Returns the length of the line segment p0p1.
1046  * @param {URBGEN.Point} p0 - the start point of the line segment.
1047  * @param {URBGEN.Point} p1 - the end point of the line segment.
1048  * @return {number} The length of the line segment.
1049  */
1050 URBGEN.Util.getLineSegmentLength = function (p0, p1) {
1051     return Math.sqrt(Math.pow((p1.x - p0.x), 2) + Math.pow((p1.y - p0.y), 2));
1052 };
1053 /**
1054  * Returns a point on the line segment p0p1 which is the specified length along
1055  * the line.
1056  * @param {URBGEN.Point} p0 - The start point of the line.
1057  * @param {URBGEN.Point} p1 - The end point of the line.
1058  * @param {number} length - The length along the line of the new point.
1059  * @return {URBGEN.Point} The new point.
1060  */
1061 URBGEN.Util.linearInterpolateByLength = function (p0, p1, length) {
1062     var totalLength = URBGEN.Util.getLineSegmentLength(p0, p1);
1063     if(length > totalLength) {
1064         return p1;
1065     }
1066     var r = length / totalLength;
1067     return URBGEN.Util.linearInterpolate(p0, p1, r);
1068 };
1069 /**
1070  * Finds a point on the line segment p0p1 using the r value (ratio of the line).
1071  * @param {URBGEN.Point} p0 - The start point of the line.
1072  * @param {URBGEN.Point} p1 - The end point of the line.
1073  * @param {number} r - The r value of the new point.
1074  * @return {URBGEN.Point} The new point.
1075  */
1076 URBGEN.Util.linearInterpolate = function (p0, p1, r) {
1077     var x = (1 - r) * p0.x + r * p1.x;
1078     var y = (1 - r) * p0.y + r * p1.y;
1079     var z = (1 - r) * p0.z + r * p1.z;
1080     return new URBGEN.Point(x, y, z);
1081 };
1082 /**
1083  * Returns the angle of the line segment p0p1 in radians.
1084  * @param {URBGEN.Point} p0 - The start point of the line segment.
1085  * @param {URBGEN.Point} p1 - The end point of the line segment.
1086  * @return {number} The angle in radians of the line segment.
1087  */
1088 URBGEN.Util.getAngle = function (p0, p1) {
1089     var x1 = p0.x;
1090     var x2 = p1.x;
1091     var y1 = p0.y;
1092     var y2 = p1.y;
1093     if(y1 === y2) {
1094         if(x2 > x1) {
1095             return 0;
1096         } else {
1097             return Math.PI;
1098         }
1099     }
1100     var angle = Math.atan2((y2 - y1), (x2 - x1));
1101     if(y2 > y1) {
1102         return angle;
1103 
1104     } else {
1105         return(2 * Math.PI) + angle;
1106     }
1107 };
1108 /**
1109  * Adds the specified dA (dA * Pi) to the specified angle. The result is
1110  * normalized to a value between 0 and 2 * Pi radians.
1111  * @param {number} angle - The angle in radians.
1112  * @param {number} dA - The factor of PI to add to the angle.
1113  * @return {number} The resultant angle in radians.
1114  */
1115 URBGEN.Util.addAngle = function (angle, dA) {
1116     var newAngle = (angle + dA * Math.PI) % (2 * Math.PI);
1117     if(newAngle < 0) {
1118         newAngle += 2 * Math.PI;
1119     }
1120     return newAngle;
1121 
1122 };
1123 /**
1124  * Returns a value that represents the specified point's location on the line
1125  * through p0 and p1, relative to the line segment p0p1.
1126  * @param {URBGEN.Point} point - The point.
1127  * @param {URBGEN.Point} p0 - A point on the line.
1128  * @param {URBGEN.Point} p1 - a different point on the line.
1129  * @return {number} The r value (ratio) of the point on the line.
1130  */
1131 URBGEN.Util.getPointAsRatio = function (point, p0, p1) {
1132     var d1;
1133     var d2;
1134     // If the line is parallel with the y-axis, use the difference in y values
1135     if(p0.x === p1.x) {
1136         d1 = point.y - p0.y;
1137         d2 = p1.y - p0.y;
1138     } else { // otherwise, use the difference in x values
1139         d1 = point.x - p0.x;
1140         d2 = p1.x - p0.x;
1141     }
1142     return d1 / d2;
1143 };
1144 /**
1145  * Returns the area of the specified polygon.
1146  * @param {URBGEN.Poly} poly - The polygon.
1147  * @return {number} The polygon's area.
1148  */
1149 URBGEN.Util.areaPoly = function (poly) {
1150     var x0 = poly.corners[3].x - poly.corners[0].x;
1151     var y0 = poly.corners[3].y - poly.corners[0].y;
1152     var x1 = poly.corners[1].x - poly.corners[2].x;
1153     var y1 = poly.corners[1].y - poly.corners[2].y;
1154     var area = Math.abs((x0 * y1 - x1 * y0) / 2);
1155     return area;
1156 };
1157 /**
1158  * Returns an array of points representing a path from p0 to p1 in the specified
1159  * direction. If p1 is not found in maxSteps iterations, returns false. If
1160  * maxSteps is not specified, defaults to 1000.
1161  * @param {URBGEN.Point} p0 - The start point of the path.
1162  * @param {URBGEN.Point} p1 - The end point of the path.
1163  * @param {number} direction - The direction of the path.
1164  * @param {number} maxSteps - The maximum number of iterations.
1165  * @return {URBGEN.Point[]} The path from p0 t0 p1.
1166  */
1167 URBGEN.Util.getDirectedPath = function (p0, p1, direction, maxSteps) {
1168     if (maxSteps === undefined) {
1169         maxSteps = 1000;
1170     }
1171     var points = [p0];
1172     var i = 0;
1173     while(points[i] !== p1) {
1174         points.push(points[i].neighbors[direction]);
1175         i++;
1176         if(i === maxSteps)
1177             return undefined;
1178     }
1179     return points;
1180 };
1181 /**
1182  * Given two lines, defined by a point on the line and the angle of the line,
1183  * returns the point at which the two lines intersect. If the lines are colinear,
1184  * returns p0.
1185  * @param {URBGEN.Point} p0 - The start point of the first line.
1186  * @param {number} a0 - The angle in radians of the first line.
1187  * @param {URBGEN.Point} p1 - The start point of the second line.
1188  * @param {number} a1 - The angle in radians of the second line.
1189  * @return {URBGEN.Point} The intersection of the two lines.
1190  */
1191 URBGEN.Util.getIntersect = function (p0, a0, p1, a1) {
1192     var m0 = Math.tan(a0);
1193     var m1 = Math.tan(a1);
1194     var x;
1195     var y;
1196     var point;
1197     // Check if the lines are colinear
1198     if(m0 === m1)
1199         return p0;
1200     // Check if either line is colinear with the y axis
1201     if(m0 === Infinity) {
1202         x = p0.x;
1203         y = x * m1 + (p1.y - m1 * p1.x);
1204     } else if(m1 === Infinity) {
1205         x = p1.x;
1206         y = x * m0 + (p0.y - m0 * p0.x);
1207         // Otherwise, find the intersection point
1208     } else {
1209         x = (p1.y - p0.y + (m0 * p0.x) - (m1 * p1.x)) / (m0 - m1);
1210         y = m1 * (x - p1.x) + p1.y;
1211     }
1212     point = new URBGEN.Point(x, y, 0);
1213     return point;
1214 };
1215 /**
1216  * Returns a path of equidistant points on the linesegment p0p1. Note that the
1217  * distance between the second last point and the end point (p1) can be of
1218  * any length.
1219  * @param {URBGEN.Point} p0 - The start point of the line segment.
1220  * @param {URBGEN.Point} p1 - The end point of the line segment.
1221  * @param {number} length - The distance between each point in the path.
1222  * @return {URBGEN.Point[]} The path of equidistant points.
1223  * @throws {URBGEN.Exception.PointsNotNeighborsException}
1224  */
1225 URBGEN.Util.divideLine = function (p0, p1, length) {
1226     if(p0.neighbors.indexOf(p1) === -1) {
1227         throw new URBGEN.Exception.PointsNotNeighborsException();
1228     }
1229     var points = [p0];
1230     var i = 0;
1231     var currentLineLength = URBGEN.Util.getLineSegmentLength(points[i], p1);
1232     while(length * 2 <= currentLineLength) {
1233         points.push(URBGEN.Util
1234             .linearInterpolateByLength(points[i], p1, length));
1235         i++;
1236         currentLineLength = URBGEN.Util.getLineSegmentLength(points[i], p1);
1237     }
1238     points.push(p1);
1239     return points;
1240 };
1241 /**
1242  * Returns a point representing the unit vector from p0 in the specified angle.
1243  * @param {URBGEN.Point} p0 - The start point of the unit vector.
1244  * @param {number} angle - The anlge in radians of the unit vector.
1245  * @return {URBGEN.Point} The unit vector.
1246  */
1247 URBGEN.Util.unitVectorByAngle = function (p0, angle) {
1248     var dY = Math.tan(angle);
1249     var point = new URBGEN.Point(p0.x + 1, p0.y + dY);
1250     return URBGEN.Util.unitVector(p0, point);
1251 };
1252 /**
1253  * Returns a point representing the unit vector for the line segment p0p1.
1254  * @param {URBGEN.Point} p0 - The start point of the line segment.
1255  * @param {URBGEN.Point} p1 - The end point of the line segment.
1256  * @return {URBGEN.Point} The unit vector.
1257  */
1258 URBGEN.Util.unitVector = function (p0, p1) {
1259     var point = URBGEN.Util.linearInterpolateByLength(p0, p1, 1);
1260     var unit = new URBGEN.Point(point.x - p0.x, point.y - p0.y, 0);
1261     return unit;
1262 
1263 };
1264 /**
1265  * Returns the unit normal for the line segment p0p1.
1266  * @param {URBGEN.Point} p0 - The start point of the line segment.
1267  * @param {URBGEN.Point} p1 - The end point of the line segment.
1268  * @return {URBGEN.Point} The unit normal.
1269  */
1270 URBGEN.Util.unitNormal = function (p0, p1) {
1271     var unitVector = URBGEN.Util.unitVector(p0, p1);
1272     var unitNormal = new URBGEN.Point(-unitVector.y, unitVector.x, 0);
1273     return unitNormal;
1274 };
1275 /**
1276  * Returns a path representing the (right) offset of the line segment p0p1.
1277  * @param {URBGEN.Point} p0 - The start point of the line segment.
1278  * @param {URBGEN.Point} p1 - The end point of the line segment.
1279  * @param {number} distance - The distance to offset the line to the right.
1280  * @return {URBGEN.Point[]} Array containing the start and end points of
1281  *     the offset line segment.
1282  */
1283 URBGEN.Util.offsetLineSegment = function (p0, p1, distance) {
1284     var unitNormal = URBGEN.Util.unitNormal(p0, p1);
1285     var p0Offset = new URBGEN.Point();
1286     p0Offset.setValues(p0);
1287     p0Offset.x += unitNormal.x * distance;
1288     p0Offset.y += unitNormal.y * distance;
1289     var p1Offset = new URBGEN.Point();
1290     p1Offset.setValues(p1);
1291     p1Offset.x += unitNormal.x * distance;
1292     p1Offset.y += unitNormal.y * distance;
1293     return [p0Offset, p1Offset];
1294 };
1295 /**
1296  * Returns an inward offset of the specified polygon. That is, the returned
1297  * polygon is formed by insetting the edges of the specified polygon.
1298  * @param {URGBEN.Poly} poly - The poly to offset.
1299  * @param {number} length - The distance of the inward offset.
1300  * @return {URBGEN.Poly} The offset polygon.
1301  */
1302 URBGEN.Util.insetPoly = function (poly, length) {
1303     // Get the edges
1304     var edges = [
1305         [poly.corners[0], poly.corners[1]],
1306         [poly.corners[1], poly.corners[3]],
1307         [poly.corners[3], poly.corners[2]],
1308         [poly.corners[2], poly.corners[0]]
1309     ];
1310     // Get the offset edges and angles
1311     var offsetEdges = [];
1312     var angles = [];
1313     for(var i = 0; i < edges.length; i++) {
1314         offsetEdges.push(URBGEN.Util.offsetLineSegment(edges[i][0],
1315             edges[i][1], length));
1316         angles.push(URBGEN.Util.getAngle(offsetEdges[i][0], offsetEdges[i][
1317             1
1318         ]));
1319     }
1320     // Find the new corners
1321     var tl = URBGEN.Util.getIntersect(offsetEdges[0][0], angles[0],
1322         offsetEdges[3][0], angles[3]);
1323     var tr = URBGEN.Util.getIntersect(offsetEdges[1][0], angles[1],
1324         offsetEdges[0][0], angles[0]);
1325     var bl = URBGEN.Util.getIntersect(offsetEdges[3][0], angles[3],
1326         offsetEdges[2][0], angles[2]);
1327     var br = URBGEN.Util.getIntersect(offsetEdges[2][0], angles[2],
1328         offsetEdges[1][0], angles[1]);
1329     return new URBGEN.Poly(tl, tr, bl, br);
1330 };
1331 /**
1332  * Sets the neighbor relations of p0 and p1 with the newPoint. If p0 and p1 are
1333  * not neighbors, returns false, otherwise true.
1334  * @param {URBGEN.Point} newPoint - The new point.
1335  * @param {URBGEN.Point} p0 - The first neighbor point.
1336  * @param {URNGEN.Point} p1 - The second neighbor point.
1337  * @return {boolean} True if successful, false otherwise.
1338  */
1339 URBGEN.Util.insertPoint = function (newPoint, p0, p1) {
1340     var direction = p0.neighbors.indexOf(p1);
1341     var oppDirection = (direction + 2) % 4;
1342     p1.neighbors[oppDirection] = newPoint;
1343     p0.neighbors[direction] = newPoint;
1344     newPoint.neighbors[direction] = p1;
1345     newPoint.neighbors[oppDirection] = p0;
1346     return true;
1347 };
1348 /**
1349  * Returns the two points closest in opposite directions to the
1350  * specified point.
1351  * @param {URBGEN.Point} point - The point to find neighbors for.
1352  * @param {URBGEN.Point[]} - The path of potential neighbors.
1353  * @return {Object} The prev and nxt points to the specified point.
1354  * @throws {URBGEN.Exception.PointOutOfRangeException}
1355  */
1356 URBGEN.Util.getNeighbors = function (point, points) {
1357     var neighbors = {
1358         prev: undefined,
1359         nxt: undefined
1360     };
1361     if(points.length === 2) {
1362         neighbors.prev = points[0];
1363         neighbors.nxt = points[1];
1364         return neighbors;
1365     }
1366     // Find the point as a ratio of the line
1367     var pointR = URBGEN.Util.getPointAsRatio(point, points[0],
1368         points[points.length - 1]);
1369     // if the point lies beyond either end of the path, throw error
1370     if(pointR <= 0 || pointR >= 1) {
1371         throw new URBGEN.Exception.PointOutOfRangeException();
1372     }
1373     for(var i = 1; i < points.length; i++) {
1374         var currPoint = points[i];
1375         var r = URBGEN.Util.getPointAsRatio(currPoint, points[0],
1376             points[points.length - 1]);
1377         //TODO what if r === pointR? ie, the point is identical to one on the path?
1378         if(r > pointR) {
1379             neighbors.prev = points[i - 1];
1380             neighbors.nxt = points[i];
1381             return neighbors;
1382         }
1383     }
1384     return false;
1385 };
1386 /**
1387  * Returns a point on the specified edge that is within the specified distance
1388  * of the specified point. If includeEnds is true, then the start and end points
1389  * of the edge will be included in the search. If no such point exists, returns
1390  * the original point.
1391  * @param {URBGEN.Point} point - The point to find near points for.
1392  * @param {URBGEN.Point[]} - The path of potential near points.
1393  * @param {number} distance - The distance within which near points can be found.
1394  * @param {boolean} includeEnds - true if the start and end points should be
1395  *     included, false if not.
1396  * @return {URBGEN.Point} The closest point to the specified point, or the
1397  *     original point is no such near point exists.
1398  */
1399 URBGEN.Util.checkNearPoints = function (point, points, distance, includeEnds) {
1400     var neighbors = URBGEN.Util.getNeighbors(point, points);
1401     var d0 = Math.abs(URBGEN.Util.getLineSegmentLength(neighbors.prev,
1402         point));
1403     var d1 = Math.abs(URBGEN.Util.getLineSegmentLength(point, neighbors.nxt));
1404     if(d0 < distance && d0 <= d1) {
1405         if(neighbors.prev === points[0]) {
1406             if(includeEnds) {
1407                 return points[0];
1408             }
1409         } else {
1410             return neighbors.prev;
1411         }
1412     } else if(d1 < distance) {
1413         if(neighbors.nxt === points[points.length - 1]) {
1414             if(includeEnds) {
1415                 return points[points.length - 1];
1416             }
1417         } else {
1418             return neighbors.nxt;
1419         }
1420     }
1421     return point;
1422 };
1423 /**
1424  * Returns the point in points that has the shortest straight line distance to
1425  * target. If any points have equal distances to target, returns the point which
1426  * comse first in points.
1427  * @param {URBGEN.Point[]} points - The points in which to look for the
1428  *     closest point.
1429  * @param {URBGEN.Point} target - The target point.
1430  * @return {URBGEN.Point} The point that is closest to the target.
1431  */
1432 URBGEN.Util.nearest = function (points, target) {
1433     var index = 0;
1434     var shortest = URBGEN.Util.getLineSegmentLength(points[0], target);
1435     for(var i = 1; i < points.length; i++) {
1436         var length = URBGEN.Util.getLineSegmentLength(points[i], target);
1437         if(length < shortest) {
1438             index = i;
1439             shortest = length;
1440         }
1441     }
1442     return points[index];
1443 };
1444 /**
1445  * @namespace holds math functions.
1446  */
1447 URBGEN.Math = {};
1448 /**
1449  * Represents a psuedorandom number generator with the specified seed.
1450  * @constructor
1451  * @param {number} seed - This random number generator's seed value.
1452  */
1453 URBGEN.Math.Random = function (seed) {
1454     /**
1455      * This random number generator's seed value.
1456      * @type number
1457      */
1458     this.seed = seed || Math.random();
1459 };
1460 /**
1461  * Returns the next psuedorandom number (0 - 1) for this psuedorandom number
1462  * generator.
1463  * @return {number} The next pseudorandom number for this generator.
1464  */
1465 URBGEN.Math.Random.prototype.next = function () {
1466     this.seed = (this.seed * 9301 + 49297) % 233280;
1467     return this.seed / 233280;
1468 };
1469 /**
1470  * @namespace holds constants.
1471  */
1472 URBGEN.Constants = {};
1473 /**
1474  * @type number
1475  */
1476 URBGEN.Constants.MAX_BLOCK_SIZE = 50000;
1477 /**
1478  * @type number
1479  */
1480 URBGEN.Constants.MIN_BLOCK_SIZE = 15000;
1481 /**
1482  * @type number
1483  */
1484 URBGEN.Constants.MAX_REGULARITY = 0.6;
1485 /**
1486  * @type number
1487  */
1488 URBGEN.Constants.MIN_REGULARITY = 0.4;
1489 /**
1490  * @type number
1491  */
1492 URBGEN.Constants.MAX_CITY_WIDTH = 2000;
1493 /**
1494  * @type number
1495  */
1496 URBGEN.Constants.MIN_CITY_WIDTH = 400;
1497 /**
1498  * @type number
1499  */
1500 URBGEN.Constants.MAX_CITY_DEPTH = 2000;
1501 /**
1502  * @type number
1503  */
1504 URBGEN.Constants.MIN_CITY_DEPTH = 400;
1505 /**
1506  * @type number
1507  */
1508 URBGEN.Constants.MAX_THROUGH_ROADS = 50;
1509 /**
1510  * @type number
1511  */
1512 URBGEN.Constants.MIN_THROUGH_ROADS = 0;
1513 /**
1514  * @type number
1515  */
1516 URBGEN.Constants.MAX_STREET_WIDTH = 30;
1517 /**
1518  * @type number
1519  */
1520 URBGEN.Constants.MIN_STREET_WIDTH = 10;
1521 /**
1522  * @type number
1523  */
1524 URBGEN.Constants.MAX_RANDOM_SEED = 1;
1525 /**
1526  * @type number
1527  */
1528 URBGEN.Constants.MIN_RANDOM_SEED = 0;
1529 /**
1530  * @type number
1531  */
1532 URBGEN.Constants.MAX_LOCAL_GRIDS = 1;
1533 /**
1534  * @type number
1535  */
1536 URBGEN.Constants.MIN_LOCAL_GRIDS = 0;
1537 /**
1538  * @type number
1539  */
1540 URBGEN.Constants.MAX_GLOBAL_ANGLE = 1;
1541 /**
1542  * @type number
1543  */
1544 URBGEN.Constants.MIN_GLOBAL_ANGLE = 0;
1545 /**
1546  * @type number
1547  */
1548 URBGEN.Constants.MIN_EDGE_LENGTH = 80;
1549 /**
1550  * @namespace holds exceptions.
1551  */
1552 URBGEN.Exception = {};
1553 /**
1554  * Represents an illegal argmument exception.
1555  * @constructor
1556  * @param {string} message This exceptions's message.
1557  */
1558 URBGEN.Exception.IllegalArgumentException = function (message) {
1559     /**
1560      * This exception's name.
1561      * @type string
1562      */
1563     this.name = "IllegalArgumentException";
1564     /**
1565      * This exception's message.
1566      * @type string
1567      */
1568     this.message = message || "Illegal Argument Exception";
1569 };
1570 URBGEN.Exception.IllegalArgumentException.prototype = new Error();
1571 URBGEN.Exception.IllegalArgumentException.prototype.constructor = URBGEN.Exception
1572     .IllegalArgumentException;
1573 /**
1574  * Represents an edge too short exception.
1575  * @constructor
1576  * @param {string} message This exceptions's message.
1577  */
1578 URBGEN.Exception.EdgeTooShortException = function (message) {
1579     /**
1580      * This exception's name.
1581      * @type string
1582      */
1583     this.name = "EdgeTooShortException";
1584     /**
1585      * This exception's message.
1586      * @type string
1587      */
1588     this.message = message || "Edge too short to divide";
1589 };
1590 URBGEN.Exception.EdgeTooShortException.prototype = new Error();
1591 URBGEN.Exception.EdgeTooShortException.prototype.constructor = URBGEN.Exception
1592     .EdgeTooShortException;
1593 /**
1594  * Represents an InvalidParamException.
1595  * @constructor
1596  * @param {string} message This exceptions's message.
1597  */
1598 URBGEN.Exception.InvalidParamException = function (message) {
1599     /**
1600      * This exception's name.
1601      * @type string
1602      */
1603     this.name = "InvalidParamException";
1604     /**
1605      * This exception's message.
1606      * @type string
1607      */
1608     this.message = message || "Invalid parameters";
1609 };
1610 URBGEN.Exception.InvalidParamException.prototype = new Error();
1611 URBGEN.Exception.InvalidParamException.prototype.constructor = URBGEN.Exception
1612     .InvalidParamException;
1613 /**
1614  * Represents a Points not neighbors exception.
1615  * @constructor
1616  * @param {string} message This exceptions's message.
1617  */
1618 URBGEN.Exception.PointsNotNeighborsException = function (message) {
1619     /**
1620      * This exception's name.
1621      * @type string
1622      */
1623     this.name = "PointsNotNeighborsException";
1624     /**
1625      * This exception's message.
1626      * @type string
1627      */
1628     this.message = message || "Points are not neighbors";
1629 };
1630 URBGEN.Exception.PointsNotNeighborsException.prototype = new Error();
1631 URBGEN.Exception.PointsNotNeighborsException.prototype.constructor = URBGEN.Exception
1632     .PointsNotNeighborsException;
1633 /**
1634  * Represents a Point out of range exception.
1635  * @constructor
1636  * @param {string} message This exceptions's message.
1637  */
1638 URBGEN.Exception.PointOutOfRangeException = function (message) {
1639     /**
1640      * This exception's name.
1641      * @type string
1642      */
1643     this.name = "PointOutOfRangeException";
1644     /**
1645      * This exception's message.
1646      * @type string
1647      */
1648     this.message = message || "Points lies outside allowable range";
1649 };
1650 URBGEN.Exception.PointOutOfRangeException.prototype = new Error();
1651 URBGEN.Exception.PointOutOfRangeException.prototype.constructor = URBGEN.Exception
1652     .PointOutOfRangeException;
1653