Take the 2-minute tour ×

I have:

  1. axis-aligned rectangle R;
  2. non-vertical line A (specified by two points);
  3. vertical line B (specified by x-coordinate).

All objects above is specified by integer coordinates.

I need to check, if result of crossing A and B is in the R. But I can't just calculate result of crossing A and B because it may be unpresentable in integer coordinates. Also I can't convert it to doubles because I need to get absolutely accurate result without any inaccuracy.

So, how can I check it?

share|improve this question
why do you think using double will be less accurate than using integers? –  Alnitak May 8 '12 at 12:00
The y coordinate of the crossing is a rational number, so what you want can be done. Note that you only need to check the y coordinate, since whether B intersects R or not is sufficient for checking the x one. The potential problem is integer overflow. –  Alexandre C. May 8 '12 at 12:18
add comment

3 Answers 3

up vote 1 down vote accepted

If lines are specified by integer coordinates, then their crossing point has rational coordinates, which may be compared with absolutely precision.

Let's A goes through points (ax0, ay0) and (ax1, ay1), and B is at X0 coordinate. Then crossing point Y-coordinate is (ay0*(ax1-ax0)+(X0-ax0)*(ay1-ay0))/(ax1-ax0) = p/q, where p and q are integer, and q is positive (negate nominator if needed).

Then p may be compared with R.Top*q and R.Bottom*q

share|improve this answer
add comment

[let's ignore not interesting case when B does not intersect R]

R cuts a segment from B, let's call it S. Intersection of B and A lies inside of R if and only if A crosses S.

Finding points of S is trivial.

To check whether a line crosses a segment, you should check that ends of S lie on different sides from A - this can be checked by signed angles.

share|improve this answer
add comment

Let's say that the 2 points on A are (x0, y0) and (x1, y1), with 'x0 < x1'.

The rectangle is determined by a x-coordinate xR and a y-coordinate yR

The B line is determined by the x-coordinate xB

The point you're looking for is (xB, yB), where yB is to be determined somehow, by manipulating integers only :

So first, you need to check

  1. if xB * xR >= 0 (same side of the x-coordinate)
  2. if abs(xB) <= abs(xR) (the B line cuts the rectangle)

If it's ok, then you need to check that this integer (which is equal to (x1-x0)yB)

Y = (y1-y0)(xB-x0)+(x1-x0)y0


  1. Y * yR >=0 (same side of the y-coord)
  2. abs(Y) <= (x1-x0) * abs(yR) (meaning that your intersection point is in the R area regarding its y-coord)

Your point is inside R if and only if the 4 conditions are true. Hope it helps.

share|improve this answer
add comment

Your Answer


