On Thu, May 14, 2009 at 4:42 PM, Hamilton Turner <[email protected]>wrote:
> 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) {
>
You might want to check |det| < epsilon rather than strick equality to 0.
R/
> // 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
-~----------~----~----~----~------~----~------~--~---
