Because of this: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
On Thu, May 14, 2009 at 5:05 PM, Hamy <[email protected]> wrote: > > 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; >> > } >> > } > > > -- Romain Guy Android framework engineer [email protected] Note: please don't send private questions to me, as I don't have time to provide private support. All such questions should be posted on public forums, where I and others can see and answer them --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
