2

In an application I am developing I have a number of lines represented by Latitude and Longitude values. I want to check if another line intersects any of these lines at any point.

enter image description here

Say I have the line A-B I want to know if it intersects the line C-D at any point. The first and second examples above would lead to no intersection whereas the third example would.

For my scenario the actual intersection point is not necassary for the application to function, so a simple yes/no to the intersection is all that is needed.

I understand that working with Latitude and Longitude values is not strictly accurate seeing as the world is an ellipsoid so the values would need converting first. However, to prove the concept I am working on, a line intersection algorithm that works for any orientation of line segments is what I am looking for.

I have seen several algorithms but have not managed to get any to work in practice.

Currently I have been looking at the method mentioned here How to compute line segment intersections on a map

I am using the code below and just using simple coordinates to prove it works, but from my testing it returns points of intersection even if they do not exist. 

double lineABxLength = bX - aX;
double lineCDxLength = dX - cX;
double lineAByLength = bY - aY;
double lineCDyLength = dY - cY;

double lineDenomiter = (lineABxLength * lineCDyLength) - (lineAByLength * lineCDxLength);

double a = (aX * aY) - (bY * aX);
double b = (dX * cY) - (dY * cX);

double xIntersection = ((a * lineCDxLength) - (b * lineABxLength)) / lineDenomiter;
double bIntersection = ((a * lineCDyLength) - (b * lineAByLength)) / lineDenomiter;
Community
  • 1
  • 1
Tom smith
  • 670
  • 2
  • 15
  • 31
  • possible duplicate of [How to check whether 2 lines segments intersect?](http://stackoverflow.com/questions/16333650/how-to-check-whether-2-lines-segments-intersect) – MarsAtomic Oct 29 '14 at 21:13
  • 1
    Remember to do your due diligence before posting. An internet search, even restricted to SO has a very high ratio of reward to caloric expenditure. – MarsAtomic Oct 29 '14 at 21:13
  • Thank you, that is definitely an option in regards to using a library rather than performing the calculation manually. This follows on to the next question of how I would account for the elipsoide shape the lat and long values represent. – Tom smith Oct 29 '14 at 21:29
  • I found this one, as well: http://stackoverflow.com/questions/16314069/calculation-of-intersections-between-line-segments No Java 2D involved. It's worth following the breadcrumb trail of references to other questions. – MarsAtomic Oct 29 '14 at 22:04

0 Answers0