Geom.java
/*
* @(#)Geom.java
*
* Project: JHotdraw - a GUI framework for technical drawings
* http://www.jhotdraw.org
* http://jhotdraw.sourceforge.net
* Copyright: © by the original author(s) and all contributors
* License: Lesser GNU Public License (LGPL)
* http://www.opensource.org/licenses/lgpl-license.html
*/
package CH.ifa.draw.util;
import java.awt.Rectangle;
import java.awt.Point;
/**
* Some geometric utilities.
*
* @version <$CURRENT_VERSION$>
*/
public class Geom {
private Geom() {} // never instantiated
/**
* Tests if a point is on a line.
*/
static public boolean lineContainsPoint(int x1, int y1,
int x2, int y2,
int px, int py) {
Rectangle r = new Rectangle(new Point(x1, y1));
r.add(x2, y2);
r.grow(2, 2);
if (! r.contains(px,py)) {
return false;
}
double a, b, x, y;
if (x1 == x2) {
return (Math.abs(px - x1) < 3);
}
if (y1 == y2) {
return (Math.abs(py - y1) < 3);
}
a = (double)(y1 - y2) / (double)(x1 - x2);
b = (double)y1 - a * (double)x1;
x = (py - b) / a;
y = a * px + b;
return (Math.min(Math.abs(x - px), Math.abs(y - py)) < 4);
}
static public final int NORTH = 1;
static public final int SOUTH = 2;
static public final int WEST = 3;
static public final int EAST = 4;
/**
* Returns the direction NORTH, SOUTH, WEST, EAST from
* one point to another one.
*/
static public int direction(int x1, int y1, int x2, int y2) {
int direction = 0;
int vx = x2 - x1;
int vy = y2 - y1;
if (vy < vx && vx > -vy) {
direction = EAST;
}
else if (vy > vx && vy > -vx) {
direction = NORTH;
}
else if (vx < vy && vx < -vy) {
direction = WEST;
}
else {
direction = SOUTH;
}
return direction;
}
static public Point south(Rectangle r) {
return new Point(r.x + r.width /2, r.y + r.height);
}
static public Point center(Rectangle r) {
return new Point(r.x + r.width /2, r.y + r.height/2);
}
static public Point west(Rectangle r) {
return new Point(r.x, r.y + r.height/ 2);
}
static public Point east(Rectangle r) {
return new Point(r.x+r.width, r.y + r.height/ 2);
}
static public Point north(Rectangle r) {
return new Point(r.x+r.width/2, r.y);
}
/**
* Constains a value to the given range.
* @return the constrained value
*/
static public int range(int min, int max, int value) {
if (value < min) {
value = min;
}
if (value > max) {
value = max;
}
return value;
}
/**
* Gets the square distance between two points.
*/
static public long length2(int x1, int y1, int x2, int y2) {
return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
/**
* Gets the distance between to points
*/
static public long length(int x1, int y1, int x2, int y2) {
return (long)Math.sqrt(length2(x1, y1, x2, y2));
}
/**
* Gets the angle of a point relative to a rectangle.
*/
static public double pointToAngle(Rectangle r, Point p) {
int px = p.x - (r.x + r.width/2);
int py = p.y - (r.y + r.height/2);
return Math.atan2(py*r.width, px*r.height);
}
/**
* Gets the point on a rectangle that corresponds to the given angle.
*/
static public Point angleToPoint(Rectangle r, double angle) {
double si = Math.sin(angle);
double co = Math.cos(angle);
double e = 0.0001;
int x= 0, y= 0;
if (Math.abs(si) > e) {
x= (int) ((1.0 + co/Math.abs(si))/2.0 * r.width);
x= range(0, r.width, x);
}
else if (co >= 0.0) {
x= r.width;
}
if (Math.abs(co) > e) {
y= (int) ((1.0 + si/Math.abs(co))/2.0 * r.height);
y= range(0, r.height, y);
}
else if (si >= 0.0) {
y= r.height;
}
return new Point(r.x + x, r.y + y);
}
/**
* Converts a polar to a point
*/
static public Point polarToPoint(double angle, double fx, double fy) {
double si = Math.sin(angle);
double co = Math.cos(angle);
return new Point((int)(fx*co+0.5), (int)(fy*si+0.5));
}
/**
* Gets the point on an oval that corresponds to the given angle.
*/
static public Point ovalAngleToPoint(Rectangle r, double angle) {
Point center = Geom.center(r);
Point p = Geom.polarToPoint(angle, r.width/2, r.height/2);
return new Point(center.x + p.x, center.y + p.y);
}
/**
* Standard line intersection algorithm
* Return the point of intersection if it exists, else null
**/
// from Doug Lea's PolygonFigure
static public Point intersect(int xa, // line 1 point 1 x
int ya, // line 1 point 1 y
int xb, // line 1 point 2 x
int yb, // line 1 point 2 y
int xc, // line 2 point 1 x
int yc, // line 2 point 1 y
int xd, // line 2 point 2 x
int yd) { // line 2 point 2 y
// source: http://vision.dai.ed.ac.uk/andrewfg/c-g-a-faq.html
// eq: for lines AB and CD
// (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
// r = ----------------------------- (eqn 1)
// (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
//
// (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
// s = ----------------------------- (eqn 2)
// (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
// XI = XA + r(XB-XA)
// YI = YA + r(YB-YA)
double denom = ((xb - xa) * (yd - yc) - (yb - ya) * (xd - xc));
double rnum = ((ya - yc) * (xd - xc) - (xa - xc) * (yd - yc));
if (denom == 0.0) { // parallel
if (rnum == 0.0) { // coincident; pick one end of first line
if ((xa < xb && (xb < xc || xb < xd)) ||
(xa > xb && (xb > xc || xb > xd))) {
return new Point(xb, yb);
}
else {
return new Point(xa, ya);
}
}
else {
return null;
}
}
double r = rnum / denom;
double snum = ((ya - yc) * (xb - xa) - (xa - xc) * (yb - ya));
double s = snum / denom;
if (0.0 <= r && r <= 1.0 && 0.0 <= s && s <= 1.0) {
int px = (int)(xa + (xb - xa) * r);
int py = (int)(ya + (yb - ya) * r);
return new Point(px, py);
}
else {
return null;
}
}
/**
* compute distance of point from line segment, or
* Double.MAX_VALUE if perpendicular projection is outside segment; or
* If pts on line are same, return distance from point
**/
// from Doug Lea's PolygonFigure
public static double distanceFromLine(int xa, int ya,
int xb, int yb,
int xc, int yc) {
// source:http://vision.dai.ed.ac.uk/andrewfg/c-g-a-faq.html#q7
//Let the point be C (XC,YC) and the line be AB (XA,YA) to (XB,YB).
//The length of the
// line segment AB is L:
//
// ___________________
// | 2 2
// L = \| (XB-XA) + (YB-YA)
//and
//
// (YA-YC)(YA-YB)-(XA-XC)(XB-XA)
// r = -----------------------------
// L**2
//
// (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
// s = -----------------------------
// L**2
//
// Let I be the point of perpendicular projection of C onto AB, the
//
// XI=XA+r(XB-XA)
// YI=YA+r(YB-YA)
//
// Distance from A to I = r*L
// Distance from C to I = s*L
//
// If r < 0 I is on backward extension of AB
// If r>1 I is on ahead extension of AB
// If 0<=r<=1 I is on AB
//
// If s < 0 C is left of AB (you can just check the numerator)
// If s>0 C is right of AB
// If s=0 C is on AB
int xdiff = xb - xa;
int ydiff = yb - ya;
long l2 = xdiff * xdiff + ydiff * ydiff;
if (l2 == 0) {
return Geom.length(xa, ya, xc, yc);
}
double rnum = (ya - yc) * (ya - yb) - (xa - xc) * (xb - xa);
double r = rnum / l2;
if (r < 0.0 || r > 1.0) {
return Double.MAX_VALUE;
}
double xi = xa + r * xdiff;
double yi = ya + r * ydiff;
double xd = xc - xi;
double yd = yc - yi;
return Math.sqrt(xd * xd + yd * yd);
/*
for directional version, instead use
double snum = (ya-yc) * (xb-xa) - (xa-xc) * (yb-ya);
double s = snum / l2;
double l = Math.sqrt((double)l2);
return = s * l;
*/
}
}