Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (548)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Fastest linesIntersect method  (Read 12735 times)
0 Members and 1 Guest are viewing this topic.
Offline 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  Cool

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

Offline appel

JGO Wizard


Medals: 50
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

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline 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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2010-07-21 12:44:05 »

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

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

Offline counterp

Senior Member


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.
Offline avm1979
« Reply #5 - Posted 2011-07-19 19:40:59 »

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

Offline Dx4

Junior Member


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
Offline Dx4

Junior Member


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
Offline 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:
http://code.google.com/p/straightedge/downloads/detail?name=src_straightedge-0.3.zip&can=2&q=

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

Offline counterp

Senior Member


Medals: 11



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

Thank you, very useful Smiley
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

atombrot (27 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!