| /******************************************************************************* |
| * Copyright (c) 2005, 2010 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| * Alexander Shatalin (Borland) - Contribution for Bug 238874 |
| *******************************************************************************/ |
| package org.eclipse.draw2d.geometry; |
| |
| /** |
| * A Utilities class for geometry operations. |
| * |
| * @author Pratik Shah |
| * @author Alexander Nyssen |
| * @since 3.1 |
| */ |
| public class Geometry { |
| |
| /** |
| * Determines whether the two line segments p1->p2 and p3->p4, given by |
| * p1=(x1, y1), p2=(x2,y2), p3=(x3,y3), p4=(x4,y4) intersect. Two line |
| * segments are regarded to be intersecting in case they share at least one |
| * common point, i.e if one of the two line segments starts or ends on the |
| * other line segment or the line segments are collinear and overlapping, |
| * then they are as well considered to be intersecting. |
| * |
| * @param x1 |
| * x coordinate of starting point of line segment 1 |
| * @param y1 |
| * y coordinate of starting point of line segment 1 |
| * @param x2 |
| * x coordinate of ending point of line segment 1 |
| * @param y2 |
| * y coordinate of ending point of line segment 1 |
| * @param x3 |
| * x coordinate of the starting point of line segment 2 |
| * @param y3 |
| * y coordinate of the starting point of line segment 2 |
| * @param x4 |
| * x coordinate of the ending point of line segment 2 |
| * @param y4 |
| * y coordinate of the ending point of line segment 2 |
| * |
| * @return <code>true</code> if the two line segments formed by the given |
| * coordinates share at least one common point. |
| * |
| * @since 3.1 |
| */ |
| public static boolean linesIntersect(int x1, int y1, int x2, int y2, |
| int x3, int y3, int x4, int y4) { |
| |
| // calculate bounding box of segment p1->p2 |
| int bb1_x = Math.min(x1, x2); |
| int bb1_y = Math.min(y1, y2); |
| int bb2_x = Math.max(x1, x2); |
| int bb2_y = Math.max(y1, y2); |
| |
| // calculate bounding box of segment p3->p4 |
| int bb3_x = Math.min(x3, x4); |
| int bb3_y = Math.min(y3, y4); |
| int bb4_x = Math.max(x3, x4); |
| int bb4_y = Math.max(y3, y4); |
| |
| // check if bounding boxes intersect |
| if (!(bb2_x >= bb3_x && bb4_x >= bb1_x && bb2_y >= bb3_y && bb4_y >= bb1_y)) { |
| // if bounding boxes do not intersect, line segments cannot |
| // intersect either |
| return false; |
| } |
| |
| // If p3->p4 is inside the triangle p1-p2-p3, then check whether the |
| // line p1->p2 crosses the line p3->p4. |
| long p1p3_x = (long) x1 - x3; |
| long p1p3_y = (long) y1 - y3; |
| long p2p3_x = (long) x2 - x3; |
| long p2p3_y = (long) y2 - y3; |
| long p3p4_x = (long) x3 - x4; |
| long p3p4_y = (long) y3 - y4; |
| if (productSign(crossProduct(p2p3_x, p2p3_y, p3p4_x, p3p4_y), |
| crossProduct(p3p4_x, p3p4_y, p1p3_x, p1p3_y)) >= 0) { |
| long p2p1_x = (long) x2 - x1; |
| long p2p1_y = (long) y2 - y1; |
| long p1p4_x = (long) x1 - x4; |
| long p1p4_y = (long) y1 - y4; |
| return productSign(crossProduct(-p1p3_x, -p1p3_y, p2p1_x, p2p1_y), |
| crossProduct(p2p1_x, p2p1_y, p1p4_x, p1p4_y)) <= 0; |
| } |
| return false; |
| } |
| |
| private static int productSign(long x, long y) { |
| if (x == 0 || y == 0) { |
| return 0; |
| } else if (x < 0 ^ y < 0) { |
| return -1; |
| } |
| return 1; |
| } |
| |
| private static long crossProduct(long x1, long y1, long x2, long y2) { |
| return x1 * y2 - x2 * y1; |
| } |
| |
| /** |
| * @see PointList#polylineContainsPoint(int, int, int) |
| * @since 3.5 |
| */ |
| public static boolean polylineContainsPoint(PointList points, int x, int y, |
| int tolerance) { |
| int coordinates[] = points.toIntArray(); |
| /* |
| * For each segment of PolyLine calling isSegmentPoint |
| */ |
| for (int index = 0; index < coordinates.length - 3; index += 2) { |
| if (segmentContainsPoint(coordinates[index], |
| coordinates[index + 1], coordinates[index + 2], |
| coordinates[index + 3], x, y, tolerance)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * @return true if the least distance between point (px,py) and segment |
| * (x1,y1) - (x2,y2) is less then specified tolerance |
| */ |
| private static boolean segmentContainsPoint(int x1, int y1, int x2, int y2, |
| int px, int py, int tolerance) { |
| /* |
| * Point should be located inside Rectangle(x1 -+ tolerance, y1 -+ |
| * tolerance, x2 +- tolerance, y2 +- tolerance) |
| */ |
| Rectangle lineBounds = Rectangle.SINGLETON; |
| lineBounds.setSize(0, 0); |
| lineBounds.setLocation(x1, y1); |
| lineBounds.union(x2, y2); |
| lineBounds.expand(tolerance, tolerance); |
| if (!lineBounds.contains(px, py)) { |
| return false; |
| } |
| |
| /* |
| * If this is horizontal, vertical line or dot then the distance between |
| * specified point and segment is not more then tolerance (due to the |
| * lineBounds check above) |
| */ |
| if (x1 == x2 || y1 == y2) { |
| return true; |
| } |
| |
| /* |
| * Calculating square distance from specified point to this segment |
| * using formula for Dot product of two vectors. |
| */ |
| long v1x = x2 - x1; |
| long v1y = y2 - y1; |
| long v2x = px - x1; |
| long v2y = py - y1; |
| long numerator = v2x * v1y - v1x * v2y; |
| long denominator = v1x * v1x + v1y * v1y; |
| long squareDistance = numerator * numerator / denominator; |
| return squareDistance <= tolerance * tolerance; |
| } |
| |
| /** |
| * One simple way of finding whether the point is inside or outside a simple |
| * polygon is to test how many times a ray starting from the point |
| * intersects the edges of the polygon. If the point in question is not on |
| * the boundary of the polygon, the number of intersections is an even |
| * number if the point is outside, and it is odd if inside. |
| * |
| * @see PointList#polygonContainsPoint(int, int) |
| * @since 3.5 |
| */ |
| public static boolean polygonContainsPoint(PointList points, int x, int y) { |
| boolean isOdd = false; |
| int coordinates[] = points.toIntArray(); |
| int n = coordinates.length; |
| if (n > 3) { // If there are at least 2 Points (4 ints) |
| int x1, y1; |
| int x0 = coordinates[n - 2]; |
| int y0 = coordinates[n - 1]; |
| |
| for (int i = 0; i < n; x0 = x1, y0 = y1) { |
| x1 = coordinates[i++]; |
| y1 = coordinates[i++]; |
| if (!segmentContaintPoint(y0, y1, y)) { |
| // Current edge has no intersection with the point by Y |
| // coordinates |
| continue; |
| } |
| int crossProduct = crossProduct(x1, y1, x0, y0, x, y); |
| if (crossProduct == 0) { |
| // cross product == 0 only if this point is on the line |
| // containing selected edge |
| if (segmentContaintPoint(x0, x1, x)) { |
| // This point is on the edge |
| return true; |
| } |
| // This point is outside the edge - simply skipping possible |
| // intersection (no parity changes) |
| } else if ((y0 <= y && y < y1 && crossProduct > 0) |
| || (y1 <= y && y < y0 && crossProduct < 0)) { |
| // has intersection |
| isOdd = !isOdd; |
| } |
| } |
| return isOdd; |
| } |
| return false; |
| } |
| |
| /** |
| * @return true if segment with two ends x0, x1 contains point x |
| */ |
| private static boolean segmentContaintPoint(int x0, int x1, int x) { |
| return !((x < x0 && x < x1) || (x > x0 && x > x1)); |
| } |
| |
| /** |
| * Calculating cross product of two vectors: 1. [ax - cx, ay - cx] 2. [bx - |
| * cx, by - cy] |
| */ |
| private static int crossProduct(int ax, int ay, int bx, int by, int cx, |
| int cy) { |
| return (ax - cx) * (by - cy) - (ay - cy) * (bx - cx); |
| } |
| |
| } |