Awesome, updated appropriately!
On May 14, 7:07 pm, Romain Guy <[email protected]> wrote:
> Because of
> this:http://www.cygnus-software.com/papers/comparingfloats/comparingfloats...
>
>
>
> 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
-~----------~----~----~----~------~----~------~--~---
