/**
* Copyright Franson Technology AB, Sweden, 2009
* <br />
* http://gpsgate.com, http://franson.com
* <br />
* author Fredrik Blomqvist
* <br />
* @module Geometry
*
*/
var Franson = Franson || {};
Franson.Geometry = Franson.Geometry || {}; // namespace. documented below
/**
* similar to Google's <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds">GBounds</a>
* todo: be able to take points[] as input also? (or Iterable)
* @param {number} x
* @param {number} y
* @param {number} w width
* @param {number} h height
* @class Franson.Geometry.Bounds
* @extends Bounds
* @constructor
*/
Franson.Geometry.Bounds = function(x, y, w, h)
{
// expose raw properties to interplay smoothly with low-level code only expecting literals
/**
* @type number
*/
this.x = x || null;
/**
* @type number
*/
this.y = y || null;
/**
* width
* @type number
*/
this.w = w || null;
/**
* height
* @type number
*/
this.h = h || null;
};
// methods
Franson.Geometry.Bounds.prototype =
{
/**
* @method isEmpty
* @return {boolean}
*/
isEmpty: function()
{
return this.x == null || this.y == null || this.w == null || this.h == null;
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.extend">GBounds.extend()</a>
* @method extend
* @param {(x,y)} point
* @return {self}
* @chainable
*/
extend: function(point)
{
if (this.isEmpty())
{
this.x = point.x;
this.y = point.y;
this.w = 0;
this.h = 0;
}
else
{
this.x = Math.min(this.x, point.x);
this.y = Math.min(this.y, point.y);
this.w = Math.max(this.w, Math.abs(point.x - this.x));
this.h = Math.max(this.h, Math.abs(point.y - this.y));
}
return this; // enable chaining. ok? (GBounds doesn't do this)
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.containsPoint">GBounds.containsPoint()</a>
* @method containsPoint
* @param {(x,y)} pos
* @return {boolean}
*/
containsPoint: function(pos)
{
return (
!this.isEmpty() &&
(this.x <= pos.x && pos.x < (this.x + this.w)) &&
(this.y <= pos.y && pos.y < (this.y + this.h))
);
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.containsBounds">GBounds.containsBounds()</a>
* @method containsBounds
* @param {Franson.Geometry.Bounds} bounds
* @return {boolean}
*/
containsBounds: function(bounds)
{
return (
!(this.isEmpty() || bounds.isEmpty()) &&
(bounds.min().x >= this.min().x) && (bounds.max().x < this.max().x) &&
(bounds.min().y >= this.min().y) && (bounds.max().y < this.max().y)
);
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.min">GBounds.min()</a>
* @method min
* @return {(x,y)}
*/
min: function()
{
return { x: this.x, y: this.y };
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.max">GBounds.max()</a>
* @method max
* @return {(x,y)}
*/
max: function()
{
return { x: this.x + this.w, y: this.y + this.h };
},
/**
* see <a href="http://code.google.com/apis/maps/documentation/reference.html#GBounds.mid">GBounds.mid()</a>
* @method getCenter
* @return {Point}
*/
getCenter: function() // and/or add a mid() function?
{
return { x: this.x + this.w / 2, y: this.y + this.h / 2 };
},
/**
* @method intersects
* @param {Franson.Geometry.Bounds} bounds
* @return {boolean}
*/
intersects: function(bounds)
{
return (
!(this.isEmpty() || bounds.isEmpty()) &&
(this.min().x < bounds.max().x) && (this.max().x >= bounds.min().x) &&
(this.min().y < bounds.max().y) && (this.max().y >= bounds.min().y)
);
},
/**
* most functions needing (x,y) input should be able to take the
* entire bounds as input. but might sometimes be useful to isolate x,y
* @method getPosition
* @return {(x,y)}
*/
getPosition: function()
{
return this.min();
},
/**
* most functions needing (w,h) input should be able to take the
* entire bounds as input. but might sometimes be useful to isolate w,h
* @method getSize
* @return {(w,h)}
*/
getSize: function()
{
return { w: this.w, h: this.h };
}
}; // Franson.Geometry.Bounds.prototype
/**
* namespace (ok name? or just geom?)
* @class Franson.Geometry
* @static
*/
MochiKit.Base.update(Franson.Geometry,
{
/**
* todo: create a fromRawBounds constructor method also? (most low-level code uses literals)
* @method createBounds
* @param {Iterable[(x,y)]} points
* @return {Franson.Geometry.Bounds}
*/
createBounds: function(points)
{
var bounds = new Franson.Geometry.Bounds();
forEach(points, method(bounds, bounds.extend));
return bounds;
},
/**
* @method createBoundsFromCenterSpan
* @param {(x,y)} center
* @param {(w,h)} span
* @return {Franson.Geometry.Bounds}
*/
createBoundsFromCenterSpan: function(center, span)
{
return new Franson.Geometry.Bounds(center.x - span.w / 2, center.y - span.h / 2, span.w, span.h);
},
/**
* @method lineSegmentIntersection
* @param {Array[(x,y)](2)} segmentA line segment
* @param {Array[(x,y)](2)} segmentB line segment
* @return {(x, y)} null if no intersection
*/
lineSegmentIntersection: function(segmentA, segmentB)
{
if (!Franson.Geometry.createBounds(segmentA).intersects(Franson.Geometry.createBounds(segmentB)))
return null;
// alias
var p0 = segmentA[0]; var p1 = segmentA[1];
var v0 = Franson.Vec2.sub(p1, p0);
var p2 = segmentB[0]; var p3 = segmentB[1];
var v1 = Franson.Vec2.sub(p3, p2)
var n0 = Franson.Vec2.ortho(v0);
var t0 = Franson.Vec2.dot(n0, Franson.Vec2.sub(p0, p2)) / Franson.Vec2.dot(n0, v1); // watch for div-by-0?
if (!(0 < t0 && t0 < 1))
return null;
// same as above but with ray/line roles reversed
var n1 = Franson.Vec2.ortho(v1);
var t1 = Franson.Vec2.dot(n1, Franson.Vec2.sub(p2, p0)) / Franson.Vec2.dot(n1, v0);
if (!(0 < t1 && t1 < 1))
return null;
return Franson.Vec2.add(p0, Franson.Vec2.scale(t1, v0)); // == p2 + t0*v1
},
/**
* O(N) brute force scan for the closest (x, y) point in the list
* todo: very close points, "fat points", can result in degenerate segments of 0-length, need to be handled somehow since they generate false positives..
* todo: should perhaps return two indices? to be able to identify the closest segment.
* todo: this doesn't really need random-access to the data (just a pair-view)
* @method findClosestPoint
* @param {object[]} points
* @param {Vec2} p
* @param {literal} [options] defaults to plain Array interface: { get: function(points, index) { return points[index] }, length: function(points) { return points.length; } }
* @return {integer} index into points
*/
findClosestPoint: function(points, p, options)
{
options = MochiKit.Base.setdefault(options, {
// this interface allows the getter to do range-offset and value-transforms
get: function(range, i) { return range[i]; },
length: function(range) { return range.length; },
epsilon: Franson.Vec2.getEpsilon()
});
var get = options.get; // alias
var minDist = Number.MAX_VALUE; // Not the real distance, just a metric
var closestIndex = -1;
for (var i = 0, len = options.length(points); i < len - 1; ++i)
{
var p0 = get(points, i);
var p1 = get(points, i+1);
var v = Franson.Vec2.sub(p1, p0);
// try to guard against "fat-points"
// todo: what's the best epsilon? (should be scale dependent I guess)
if (Franson.Vec2.equals(v, Franson.Vec2.zero, options.epsilon))
continue;
var u0 = Franson.Vec2.sub(p, p0);
var dot0 = Franson.Vec2.dot(u0, v);
if (dot0 < 0)
continue;
var u1 = Franson.Vec2.sub(p, p1);
var dot1 = Franson.Vec2.dot(u1, Franson.Vec2.negate(v));
if (dot1 < 0)
continue;
var n = Franson.Vec2.ortho(v);
var n2 = Franson.Vec2.dot(n, n);
if (n2 <= 0) // guard (as above)
continue;
// note: don't need full normalization here (could also use double mul instead of abs. perhaps faster?)
// (real distance calc would be: d = dot(normalize(n), u0) )
var d = Math.abs(Franson.Vec2.dot(n, u0)) / n2;
if (d < minDist)
{
minDist = d;
closestIndex = dot0 < dot1 ? i+0 : i+1;
}
}
return closestIndex;
}
});