Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (754) Games in Android Showcase (229) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Fastest linesIntersect method  (Read 27227 times) 0 Members and 1 Guest are viewing this topic.
CommanderKeith
 « Posted 2010-06-09 13:14:25 »

Hi,

I've been really getting into computer geometry lately and done lots of research on the fastest way to do various 2D linear geometry things, and surprisingly it's quite hard to find the fastest methods to do basic things like line intersections. So I thought I'd share the fastest methods that I've come across, which might save you some time

The fastest way to test if 2 line segments intersect. Tests if the line segment from (x1, y1) to (x2, y2) intersects the line segment from (x3, y3) to (x4, y4). My tests showed that this method was about 25% faster than java.awt.geom.Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4):

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58 `   public static boolean linesIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4){      // Return false if either of the lines have zero length      if (x1 == x2 && y1 == y2 ||            x3 == x4 && y3 == y4){         return false;      }      // Fastest method, based on Franklin Antonio's "Faster Line Segment Intersection" topic "in Graphics Gems III" book (http://www.graphicsgems.org/)      double ax = x2-x1;      double ay = y2-y1;      double bx = x3-x4;      double by = y3-y4;      double cx = x1-x3;      double cy = y1-y3;      double alphaNumerator = by*cx - bx*cy;      double commonDenominator = ay*bx - ax*by;      if (commonDenominator > 0){         if (alphaNumerator < 0 || alphaNumerator > commonDenominator){            return false;         }      }else if (commonDenominator < 0){         if (alphaNumerator > 0 || alphaNumerator < commonDenominator){            return false;         }      }      double betaNumerator = ax*cy - ay*cx;      if (commonDenominator > 0){         if (betaNumerator < 0 || betaNumerator > commonDenominator){            return false;         }      }else if (commonDenominator < 0){         if (betaNumerator > 0 || betaNumerator < commonDenominator){            return false;         }      }      if (commonDenominator == 0){         // This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.         // The lines are parallel.         // Check if they're collinear.         double y3LessY1 = y3-y1;         double collinearityTestForP3 = x1*(y2-y3) + x2*(y3LessY1) + x3*(y1-y2);   // see http://mathworld.wolfram.com/Collinear.html         // If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4         if (collinearityTestForP3 == 0){            // The lines are collinear. Now check if they overlap.            if (x1 >= x3 && x1 <= x4 || x1 <= x3 && x1 >= x4 ||                  x2 >= x3 && x2 <= x4 || x2 <= x3 && x2 >= x4 ||                  x3 >= x1 && x3 <= x2 || x3 <= x1 && x3 >= x2){               if (y1 >= y3 && y1 <= y4 || y1 <= y3 && y1 >= y4 ||                     y2 >= y3 && y2 <= y4 || y2 <= y3 && y2 >= y4 ||                     y3 >= y1 && y3 <= y2 || y3 <= y1 && y3 >= y2){                  return true;               }            }         }         return false;      }      return true;   }`

This method calculates the intersection point of two lines, or returns null if they're parallel. Note that the line segments may not actually intersect, but the intersection point will still be returned, so long as the lines aren't parallel. This method treats the lines as never-ending lines, not line segments. Use 'linesIntersect' to test for intersection.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23 `   public static KPoint getLineLineIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {      double det1And2 = det(x1, y1, x2, y2);      double det3And4 = det(x3, y3, x4, y4);      double x1LessX2 = x1 - x2;      double y1LessY2 = y1 - y2;      double x3LessX4 = x3 - x4;      double y3LessY4 = y3 - y4;      double det1Less2And3Less4 = det(x1LessX2, y1LessY2, x3LessX4, y3LessY4);      if (det1Less2And3Less4 == 0){         // the denominator is zero so the lines are parallel and there's either no solution (or multiple solutions if the lines overlap) so return null.         return null;      }      double x = (det(det1And2, x1LessX2,            det3And4, x3LessX4) /            det1Less2And3Less4);      double y = (det(det1And2, y1LessY2,            det3And4, y3LessY4) /            det1Less2And3Less4);      return new KPoint(x, y);   }   protected static double det(double a, double b, double c, double d) {      return a * d - b * c;   }`

I've also got fast code for a few other things like polygon.contains(point). Let me know if it'd be useful.

Keith

appel

JGO Wizard

Medals: 80
Projects: 4

I always win!

 « Reply #1 - Posted 2010-06-09 15:16:05 »

May be something here: http://www.java-gaming.org/topics/utils-essentials/22144/view.html
CommanderKeith
 « Reply #2 - Posted 2010-07-14 12:06:47 »

Hi,

Just an apology and a code fix - I made an error in the above for the edge-case of parallel but non-intersecting lines. The code above is now correct. I was making the false assumption that parallel lines were always collinear and overlapping which is obviously wrong. Sorry! The above code now works.

CommanderKeith
 « Reply #3 - Posted 2010-07-21 12:44:05 »

Oops I made another error in the linesIntersect method, this is getting embarrassing

It was in the corner-case where lines are parallel and collinear. Now it's fixed, fingers crossed!

counterp

Senior Devvie

Medals: 11

 « Reply #4 - Posted 2011-07-19 08:41:38 »

Maybe it's a bit of a gravedig, but I see you're still active on forums.

Would you be willing to share more of your geometric math? Specifically rectangles intersecting lines/other rectangles. Everything is useful though.

Thanks.
avm1979
 « Reply #5 - Posted 2011-07-19 19:40:59 »

I've found this: http://paulbourke.net/geometry/ to be extremely useful.

Dx4

Junior Devvie

Medals: 5

 « Reply #6 - Posted 2011-07-20 04:02:09 »

here

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74 `   public static boolean doesIntersect(LineSegment line, double x1, double y1, double x2, double y2) {      return doesIntersect(line.getStart().x, line.getStart().y, line.getEnd().x, line.getEnd().y, x1, y1, x2, y2);   }   public static boolean doesIntersect(double l1x1, double l1y1, double l1x2, double l1y2, double l2x1, double l2y1, double l2x2,         double l2y2) {      double denom = ((l2y2 - l2y1) * (l1x2 - l1x1)) - ((l2x2 - l2x1) * (l1y2 - l1y1));      if (denom == 0.0f) {         return false;      }      double ua = (((l2x2 - l2x1) * (l1y1 - l2y1)) - ((l2y2 - l2y1) * (l1x1 - l2x1))) / denom;      double ub = (((l1x2 - l1x1) * (l1y1 - l2y1)) - ((l1y2 - l1y1) * (l1x1 - l2x1))) / denom;      return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));   }   public static boolean doesIntersect(LineSegment ln1, LineSegment ln2) {      float denom = ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getEnd().x - ln1.getStart().x))            - ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getEnd().y - ln1.getStart().y));      if (denom == 0.0f) {         return false;      }      double ua = ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getStart().y - ln2.getStart().y))            - ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;      double ub = ((ln1.getEnd().x - ln1.getStart().x) * (ln1.getStart().y - ln2.getStart().y))            - ((ln1.getEnd().y - ln1.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;      return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));   }   public static Point getIntersection(LineSegment line, double x1, double y1, double x2, double y2) {      double denom = ((line.getEnd().y - line.getStart().y) * (x2 - x1))            - ((line.getEnd().x - line.getStart().x) * (y2 - y1));      double nume_a = ((line.getEnd().x - line.getStart().x) * (y1 - line.getStart().y))            - ((line.getEnd().y - line.getStart().y) * (x1 - line.getStart().x));      double nume_b = ((x2 - x1) * (y1 - line.getStart().y)) - ((y2 - y1) * (x1 - line.getStart().x));      if (denom == 0.0f) {         return null;      }      double ua = nume_a / denom;      double ub = nume_b / denom;      if ((ua >= 0.0f) && (ua <= 1.0f) && (ub >= 0.0f) && (ub <= 1.0f)) {         // Get the intersection point.         int intersectX = (int) (line.getStart().x + ua * (line.getEnd().x - line.getStart().x));         int intersectY = (int) (line.getStart().y + ua * (line.getEnd().y - line.getStart().y));         return new Point(intersectX, intersectY);      }      return null;   }   public static Point lineIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {      double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);      if (denom == 0.0) { // Lines are parallel.         return null;      }      double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;      double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;      if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {         // Get the intersection point.         return new Point((int) (x1 + ua * (x2 - x1)), (int) (y1 + ua * (y2 - y1)));      }      return null;   }`

hth
Dx4

Junior Devvie

Medals: 5

 « Reply #7 - Posted 2011-07-20 04:03:30 »

Maybe it's a bit of a gravedig, but I see you're still active on forums.

Would you be willing to share more of your geometric math? Specifically rectangles intersecting lines/other rectangles. Everything is useful though.

Thanks.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154 `   public static boolean checkCollision(Rectangle rect1, Rectangle rect2) {      if ((rect1.getRotation() == 0x00) && (rect2.getRotation() == 0x00)) {    // see if we should just do standard collision checking         int tw = rect1.width;         int th = rect1.height;         int rw = rect2.width;         int rh = rect2.height;         if ((rw <= 0) || (rh <= 0) || (tw <= 0) || (th <= 0)) {            return false;         }         int tx = rect1.x;         int ty = rect1.y;         int rx = rect2.getX();         int ry = rect2.getY();         rw += rx;         rh += ry;         tw += tx;         th += ty;         return (((rw < rx) || (rw > tx)) && ((rh < ry) || (rh > ty)) && ((tw < tx) || (tw > rx))               && ((th < ty) || (th > ry)));      } else {         // First do a circle on circle collision test         int rectS1 = rect1.getWidth() / 2;         if (rectS1 > rect1.getHeight() / 2) {            rectS1 = rect1.getHeight() / 2;         }         int rectS2 = rect2.getWidth() / 2;         if (rectS2 > rect2.getHeight() / 2) {            rectS2 = rect2.getHeight() / 2;         }         int radiiSum = rectS1 + rectS2;         int rcw1 = rect1.getX() + rect1.getWidth() / 2;         int rch1 = rect1.getY() + rect1.getHeight() / 2;         int rcw2 = rect2.getX() + rect2.getWidth() / 2;         int rch2 = rect2.getY() + rect2.getHeight() / 2;         double dist = getDistanceSq(rcw1, rch1, rcw2, rch2);         if (dist > radiiSum * radiiSum) {    // The inner circles don't intersect - no collision is possible.            return false;         }         Vector2D a = new Vector2D(0, 0);         Vector2D b = new Vector2D(0, 0);         Vector2D c;         Vector2D bl, tr;         float ang = (float) (rect1.getRotation() - rect2.getRotation()), cosa = (float) Math.cos((double) ang),               sina = (float) Math.sin((double) ang);         float t_, x, a_;         float dx;         float vert1, vert2;         c = new Vector2D(rect2.getX() + rect2.getWidth() / 2, rect2.getY() + rect2.getHeight() / 2);         c.addX(-(rect1.getX() + rect1.getWidth() / 2));         c.addY(-(rect1.getY() + rect1.getHeight() / 2));         rotateVector2DClockwise(c, (float) rect2.getRotation());         bl = c.copy();         tr = c.copy();         bl.addX(-(rect2.getWidth() / 2));         bl.addY(-(rect2.getHeight() / 2));         tr.addX(rect2.getWidth() / 2);         tr.addY(rect2.getHeight() / 2);         a.setX(-rect1.getHeight() / 2 * sina);         b.setX(a.getX());         t_ = rect1.getWidth() / 2 * cosa;         a.setX(a.getX() + t_);         b.setX(b.getX() - t_);         a.setY(rect1.getHeight() / 2 * cosa);         b.setY(a.getY());         t_ = rect1.getHeight() / 2 * sina;         a.setY(a.getY() + t_);         b.setY(b.getY() - t_);         t_ = sina * cosa;         if (t_ < 0) {            t_ = a.getX();            a.setX(b.getX());            b.setX(t_);            t_ = a.getY();            a.setY(b.getY());            b.setY(t_);         }         if (sina < 0) {            b.setX(-b.getX());            b.setY(-b.getY());         }         if ((b.getX() > tr.getX()) || (b.getX() > -bl.getX())) {            return false;         }         if (t_ == 0) {            vert1 = a.getY();            vert2 = -vert1;         } else {            x = bl.getX() - a.getX();            a_ = tr.getX() - a.getX();            vert1 = a.getY();            if (a_ * x > 0) {               dx = a.getX();               if (x < 0) {                  dx -= b.getX();                  vert1 -= b.getY();                  x = a_;               } else {                  dx += b.getX();                  vert1 += b.getY();               }               vert1 *= x;               vert1 /= dx;               vert1 += a.getY();            }            x = bl.getX() + a.getX();            a_ = tr.getX() + a.getX();            vert2 = -a.getY();            if (a_ * x > 0) {               dx = -a.getX();               if (x < 0) {                  dx -= b.getX();                  vert2 -= b.getY();                  x = a_;               } else {                  dx += b.getX();                  vert2 += b.getY();               }               vert2 *= x;               vert2 /= dx;               vert2 -= a.getY();            }         }         if (vert1 > vert2) {            t_ = vert1;            vert1 = vert2;            vert2 = t_;         }         return !(((vert1 < bl.getY()) && (vert2 < bl.getY())) || ((vert1 > tr.getY()) && (vert2 > tr.getY())));      }   }`

rotated rect vs rotated rect collision detector
CommanderKeith
 « Reply #8 - Posted 2011-07-20 06:52:44 »

Maybe it's a bit of a gravedig, but I see you're still active on forums.

Would you be willing to share more of your geometric math? Specifically rectangles intersecting lines/other rectangles. Everything is useful though.

Thanks.

Sure, I've put all of the most useful 2D operations i've found and made in the straightedge.geom.KPolygon class here:

To do rectangle-rectangle you can make a rectangle polygon using the above code, and then easily do intersections with other polygons, lines, and so on. The hardest code to make fast and correct for me was polygon.contains(point), line intersection testing and the point of line-line intersection. But they're working well in that polygon class.

I've found this: http://paulbourke.net/geometry/ to be extremely useful.

Yes that stuff is great. So is
http://www.cs.princeton.edu/introcs/35purple/Polygon.java.html
and Joseph O'Rourke http://exaflop.org/docs/cgafaq/cga2.html

counterp

Senior Devvie

Medals: 11

 « Reply #9 - Posted 2011-07-21 13:13:06 »

Thank you, very useful
Pages: [1]
 ignore  |  Print

 DesertCoockie (21 views) 2018-05-13 18:23:11 nelsongames (69 views) 2018-04-24 18:15:36 nelsongames (66 views) 2018-04-24 18:14:32 ivj94 (750 views) 2018-03-24 14:47:39 ivj94 (80 views) 2018-03-24 14:46:31 ivj94 (596 views) 2018-03-24 14:43:53 Solater (96 views) 2018-03-17 05:04:08 nelsongames (169 views) 2018-03-05 17:56:34 Gornova (379 views) 2018-03-02 22:15:33 buddyBro (1039 views) 2018-02-28 16:59:18
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org