Raphael, It's been a while since I was doing this kind of math, mind telling me why that would be advantageous here?
Thanks! Hamy On May 14, 7:02 pm, Raphael <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
