| WhiteDragon |
07-17-2011 03:17 AM |
Geometry function pack
Geometry function pack
Some functions for common geometry tasks when doing game-related things.
Note, this depends on quicksort.
Documentation: http://classicgraal.net/geometry.html
Source:
PHP Code:
this.join("algorithm_quicksort_func");
//#CLIENTSIDE
/**
* Give the three points of the triangle in {x,y} form, then the point.
*
* Uses barycentric coordinates.
*
* @param array(float) Point one of triangle.
* @param array(float) Point two of triangle.
* @param array(float) Point three of triangle.
* @param array(float) Point.
* @return int 0 if it is not in the triangle, 1 if it is.
*/
function pointInTriangle(temp.a, temp.b, temp.c, temp.p) {
temp.v0 = this.vsubtract(temp.c, temp.a);
temp.v1 = this.vsubtract(temp.b, temp.a);
temp.v2 = this.vsubtract(temp.p, temp.a);
temp.d00 = this.vdot(temp.v0, temp.v0);
temp.d01 = this.vdot(temp.v0, temp.v1);
temp.d02 = this.vdot(temp.v0, temp.v2);
temp.d11 = this.vdot(temp.v1, temp.v1);
temp.d12 = this.vdot(temp.v1, temp.v2);
temp.invDenom = 1 / (temp.d00 * temp.d11 - temp.d01 * temp.d01);
temp.u = (temp.d11 * temp.d02 - temp.d01 * temp.d12) * temp.invDenom;
temp.v = (temp.d00 * temp.d12 - temp.d01 * temp.d02) * temp.invDenom;
return (temp.u > 0) && (temp.v > 0) && (temp.u + temp.v < 1);
}
/**
* Internal function... 2d dot product.
*/
function vdot(temp.v0, temp.v1) {
return temp.v0[0]*temp.v1[0] + temp.v0[1]*temp.v1[1];
}
/**
* Internal function... 2d vector subtraction.
*/
function vsubtract(temp.v0, temp.v1) {
return {temp.v1[0] - temp.v0[0], temp.v1[1] - temp.v0[1]};
}
/**
* Point in polygon.
*
* @param array(array(float)) An array of {x,y} pairs.
* @param array(float) An {x,y} pair.
* @return int If the point is in the polygon.
*/
function pointInPolygon(temp.poly, temp.pt) {
temp.npol = temp.poly.size();
temp.i;
temp.j;
temp.c = 0;
for (temp.i = 0, temp.j = temp.npol-1; temp.i < temp.npol; temp.j = temp.i++) {
if ((((temp.poly[temp.i][1] <= temp.pt[1]) && (temp.pt[1] < temp.poly[temp.j][1])) ||
((temp.poly[temp.j][1] <= temp.pt[1]) && (temp.pt[1] < temp.poly[temp.i][1]))) &&
(temp.pt[0] < (temp.poly[temp.j][0] - temp.poly[temp.i][0]) * (temp.pt[1] - temp.poly[temp.i][1]) / (temp.poly[temp.j][1] - temp.poly[temp.i][1]) + temp.poly[temp.i][0])) {
temp.c = !temp.c;
}
}
return temp.c;
}
/**
* Convex hull... given an array of points, form a convex polygon which contains all of them.
* Uses the gift wrap algorithm.
*
* @param array(array(float)) An array of {x,y} pairs.
* @return array(array(float)) An array of {x,y} pairs forming the convex polygon around the input pairs.
*/
function convexHull(temp.points) {
temp.ordered.copyfrom(temp.points);
this.lexographicOrder(temp.ordered);
temp.hull = {temp.ordered[0]};
for (temp.p : temp.hull) {
temp.q = this.convexHullNext(temp.points, temp.p);
if ((@temp.q) != (@temp.hull[0])) {
temp.hull.add(temp.q);
}
}
return temp.hull;
}
// internal
function convexHullDist(temp.p, temp.q) {
temp.dx = temp.q[0] - temp.p[0];
temp.dy = temp.q[1] - temp.p[1];
return temp.dx * temp.dx + temp.dy * temp.dy;
}
// internal
function convexHullNext(temp.points, temp.p) {
temp.q = temp.p;
for (temp.r : temp.points) {
temp.t = this.convexHullTurn(temp.p, temp.q, temp.r);
if (temp.t == -1 || temp.t == 0 && this.convexHullDist(temp.p, temp.r) > this.convexHullDist(temp.p, temp.q)) {
temp.q = temp.r;
}
}
return temp.q;
}
// internal
function convexHullTurn(temp.p, temp.q, temp.r) {
temp.a = (temp.q[0] - temp.p[0])*(temp.r[1] - temp.p[1]) - (temp.r[0] - temp.p[0])*(temp.q[1] - temp.p[1]);
if (temp.a < 0) {
return -1;
} else if (temp.a == 0) {
return 0;
} else {
return 1;
}
}
// internal
function lexographicOrder(temp.ps) {
temp.cmp = function (temp.a, temp.b) {
if (temp.a[0] < temp.b[0]) {
return -1;
} else if (temp.a[0] == temp.b[0] && temp.a[1] <= temp.b[1]) {
return -1;
} else {
return 1;
}
};
this.quicksort(temp.ps.link(), temp.cmp);
}
/**
* Bounding rectangle.
* Get a rectangle that inscribes the given polygon.
*
* @param array(array(float)) An array of {x,y} points that form a polygon.
* @return array(float) A {x,y,w,h} array describing the rectangle inscribing the polygon.
*/
function boundingRectangle(temp.ps) {
temp.lowestX = temp.ps[0][0];
temp.lowestY = temp.ps[0][1];
temp.highestX = temp.ps[0][0];
temp.highestY = temp.ps[0][1];
temp.pss = temp.ps.size();
for (temp.i = 0; temp.i < temp.pss; temp.i++) {
temp.p = temp.ps[temp.i];
temp.lowestX = min(temp.lowestX, temp.p[0]);
temp.lowestY = min(temp.lowestY, temp.p[1]);
temp.highestX = max(temp.highestX, temp.p[0]);
temp.highestY = max(temp.highestY, temp.p[1]);
}
temp.x = temp.lowestX;
temp.y = temp.lowestY;
temp.width = temp.highestX - temp.lowestX;
temp.height = temp.highestY - temp.lowestY;
return {temp.x, temp.y, temp.width, temp.height};
}
|
