CODEWITHSUNDEEP
javascriptalgorithmgeometry
user1778856
user1778856

Reputation: 641

How to check if line segment intersects square

I have a line segment determined by two points a and b. I also have a square determined by x0 < x < x1 and y0 < y < y1 where x1-x0 = y1-y0. I'm trying to check if any part of the segment intersects the region inside the square. (If the segment just touches the sides that doesn't count as an intersection).

My idea was using this picture

pic

function(a, b, x0, x1, y0, y1) {
  if (a or b is inside square)
    return true;
  else {
    switch (which quadrant is a in) {
      case 1: return (ab intersects top of square);
      case 2: return (ab intersects left of square);
      case 3: return (ab intersects bottom of square);
      case 4: return (ab intersects right of square);
    }
  }
}

I was wondering if there is a better way to approach this problem.

Upvotes: 1

Views: 4983

Answers (3)

shole
shole

Reputation: 4094

A short answer I think of is just test segment intersection with your line and the 4 lines of the square using standard computational geom cross product.

This is a quick tutorial http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf

Define ccw(A,B,C) = (B-A) X (C-A) where A,B,C is some point ccw(A,B,C) < 0 means C lies on the left side of line AB ccw(A,B,C) > 0 means C lies on the right side of line AB

So testing segment intersection is just like, giving two lines AB (your segment) and CD (any side of the square)

They intersect properly (i.e. not including touch case) iff

ccw(A,B,C) * ccw(A,B,D) < 0 AND ccw(C,D,A) * ccw(C,D,B) < 0

which simply means "C and D lies on different side of line AB, while A and B lies on different side of line CD" --> intersection

Upvotes: 3

user1196549
user1196549

Reputation:

You can solve this problem analytically using inequalities and the parametric equation of the line segment (we use dx/dy to denote xb-xa/yb-ya):

    x0 < xa + t.dx < x1
    y0 < xb + t.dy < y1
     0 <      t    < 1

Then rewrite to let three bracketings of the same term appear:

    (x0 - xa).dy < t.dx.dy < (x1 - xa).dy
    (y0 - ya).dx < t.dx.dy < (y1 - ya).dx
               0 < t.dx.dy < dx.dy

Caution: when multiplying by a negative d, the members of the inequalities must be swapped; thus there are four cases. (Actually 9 as the d's can also be 0. These cases are easy and ignored here.)

Finally, express that these bracketings are compatible, i.e. there is at least one possible tvalue:

    Max((x0 - xa).dy, (y0 - ya).dx, 0) < Min(x1 - xa).dy, (y1 - ya).dx, dx.dy)

Looking closely, you can recognize elements of your approach: for instance 0 < (x1 - xa).dy is a comparison against the right side, and (x0 - xa).dy < (y1 - ya).dx is a comparison against a diagonal.

This approach takes 2 - to compute dx/dy, then 4 <> (comparisons) for the discussion of the 9 cases, then for the oblique segments, 4 -, 5 * and 5 <> to conclude.

Something like this (caution, unchecked !):

dx= xb - xa; dy= yb - ya;
if (dx > 0)
{
    if (dy > 0) return Max((x0 - xa).dy, (y0 - ya).dx, 0) < Min(x1 - xa).dy, (y1 - ya).dx, dx.dy);
    else if (dy < 0) return Max((x1 - xa).dy, (y0 - ya).dx, 0) < Min(x0 - xa).dy, (y1 - ya).dx, dx.dy);
    else return Max(y0 - ya, 0) < Min(y1 - ya, dy);
}
else if (dx < 0)
{
    if (dy > 0) return Max((x0 - xa).dy, (y1 - ya).dx, 0) < Min(x1 - xa).dy, (y0 - ya).dx, dx.dy);
    else if (dy < 0) return Max((x1 - xa).dy, (y1 - ya).dx, 0) < Min(x0 - xa).dy, (y0 - ya).dx, dx.dy);
    else return Max(y1 - ya, 0) < Min(y0 - ya, dy);
}
else
{
    if (dy > 0) return Max(x0 - xa, 0) < Min(x1 - xa, 0);
    else if (dy < 0) return Max(x1 - xa, 0) < Min(x0 - xa, 0);
    else return false;
}

Upvotes: 1

benji
benji

Reputation: 606

You only need to check 2 cases.

If the line is above line 1 in the upper vertices or below line 3 in the bottom vertices. If either of these conditions returns true, there's no intersection.

For example, to check against line 1 you would calculate y=mx+n for your line determined by a,b and check if y(x0) > y1 and similarly that y(x1) > y1

Upvotes: 0

Related Questions