Hi all,
I have been searching for something like this for a while, finally
made what I think is a decent solution on my own, and wanted to share
it with the community. Comments would be appreciated, I think I may
have some small bugs in the equality checking if the lines are
parallel (I might need a <= where I have a < in case the last point is
the overlap). Hopefully there are no glaring errors.
Also, please note that this is a solution for line segments, not for
lines! There are a bunch of easily found, really similar solutions for
lines.
Thanks,
Hamy
Problem: Given 4 points, that define 2 line segments, return true/
false based on if they intersect. Could be easily modified to return
the point of intersection.
Note that a precision point is simply a point that stores the x/y
values as floats or doubles. I made it because I needed it for other
stuff, you can just cast all of the int's to doubles yourself and it
should work just as well.
private boolean intersects(PrecisionPoint start1,
PrecisionPoint end1, PrecisionPoint start2,
PrecisionPoint end2) {
// First find Ax+By=C values for the two lines
double A1 = end1.y - start1.y;
double B1 = start1.x - end1.x;
double C1 = A1 * start1.x + B1 * start1.y;
double A2 = end2.y - start2.y;
double B2 = start2.x - end2.x;
double C2 = A2 * start2.x + B2 * start2.y;
double det = (A1 * B2) - (A2 * B1);
if (det == 0) {
// Lines are either parallel, are collinear (the exact
same
// segment), or are overlapping partially, but not fully
// To see what the case is, check if the endpoints of
one line
// correctly satisfy the equation of the other (meaning
the two
// lines have the same y-intercept).
// If no endpoints on 2nd line can be found on 1st,
they are
// parallel.
// If any can be found, they are either the same
segment,
// overlapping, or two segments of the same line,
separated by some
// distance.
// Remember that we know they share a slope, so there
are no other
// possibilities
// Check if the segments lie on the same line
// (No need to check both points)
if ((A1 * start2.x) + (B1 * start2.y) == C1) {
// They are on the same line, check if they are
in the same
// space
// We only need to check one axis - the other
will follow
if ((Math.min(start1.x, end1.x) < start2.x)
&& (Math.max(start1.x, end1.x)
> start2.x))
return true;
// One end point is ok, now check the other
if ((Math.min(start1.x, end1.x) < end2.x)
&& (Math.max(start1.x, end1.x)
> end2.x))
return true;
// They are on the same line, but there is
distance between them
return false;
}
// They are simply parallel
return false;
} else {
// Lines DO intersect somewhere, but do the line
segments intersect?
double x = (B2 * C1 - B1 * C2) / det;
double y = (A1 * C2 - A2 * C1) / det;
// Make sure that the intersection is within the
bounding box of
// both segments
if ((x > Math.min(start1.x, end1.x) && x <
Math.max(start1.x,
end1.x))
&& (y > Math.min(start1.y, end1.y) && y
< Math.max(
start1.y, end1.y))) {
// We are within the bounding box of the first
line segment,
// so now check second line segment
if ((x > Math.min(start2.x, end2.x) && x <
Math.max(start2.x,
end2.x))
&& (y > Math.min(start2.y,
end2.y) && y < Math.max(
start2.y,
end2.y))) {
// The line segments do intersect
return true;
}
}
// The lines do intersect, but the line segments do not
return false;
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
-~----------~----~----~----~------~----~------~--~---
