# Fraction of a square area within two lines

I have a general line $r: ax + by + c = 0$ and two parallel lines $s,t$ distant $d$ from $r$. And a square of side $l = 1$ centered at $(x_c,y_c)$. The square sides are perpendicular to the $x$ and $y$ axis.

I want a find a function $f(x_c,y_c,a,b,c,d)$ that finds the area of the square within the two lines $s,t$.

• The problem is: does the square have a fixed inclinaison, that is, are the sides of the square parallel to the axis or are they free? – Martigan Nov 10 '14 at 13:20
• Small improvement: Since $f(x_c, y_c, a, b, c, d) = f(0, 0, a, b, c + ax_c + by_c, d)$, you need only solve this for $x_c = y_c = 0$. My guess: you need to work out lots of cases, and it's going to be ugly. Further suggestion: you might do better to find the intersection of the COMPLEMENT of the wide-line with the square, since the areas of the two parts (either of which might be empty) can be computed individually and then summed. – John Hughes Nov 10 '14 at 13:21
• @Martigan The square sides are perpendicular to the x and y axis, Edited – Gioelelm Nov 10 '14 at 13:25
• @John It does not matter if it is ugly. I need it for computer image analysis, to draw exact lines. So that if I draw $n$ lines of width 1 next to each other I get exactly a line of width n. Using fast approximated algorithms I would get a "striped result". – Gioelelm Nov 10 '14 at 13:30
• All I meant was "the formula for each of the complementary parts is going to involve a "cases" type of function with about 5 cases (each of which is quadratic in $d$), and you probably just have to work these out for yourself, alas." There might be a clever trick involving splines...but I don't see if offhand. – John Hughes Nov 10 '14 at 13:33

Here's an answer (by reduction to a previously solved problem, namely, interpolating splines).

1. Scale your line equation so that $a^2 + b^2 = 1$. The vector $n = (a, b)$ is normal to your line.

2. Consider the line $\ell_c$, given by $ax + by + c = 0$. That line is offset from the origin, in the direction of $n$, by distance $-c$. So by adjusting $c$ to $c + d/2$ or $c - d/2$, you can get the two "sides" of your wide line. Let's look at $\ell_c$ for an arbitrary $c$.

3. There's a halfspace beyond this line ("beyond" in the direction that $n$ points) , whose intersection with the square might be empty, a triangle, various other polygonal shapes, or the whole square. The area $A_c$ of this cut-off piece depends on the value of $c$.

To handle one case, let's suppose that $a < 0$, $b > 0$, and $b \ge a$, so the line itself has slope between $0$ and $1$. As we vary $c$ from a large positive number to a large negative number, the line passes through each of the four corners of the square. If we call the lower-right corner $Q_1 = (1/2, -1/2)$, the lower left $Q_2 = (-1/2, -1/2)$, the upper right $Q_3 = (1/2, 1/2)$ and the upper left $Q_4 = (-1/2, 1/2)$, the order of intersection is $Q_1, Q_2, Q_3, Q_4$, where the intersections with $Q_2$ and $Q_3$ are simultaneous if the slope is $1$.

These intersections happen when $c$ takes on the values $c_i = -n \cdot Q_i$, which are in decreasing order (alas).

If we call $A(c)$ the area of the portion of the square that lines the halfplane determined by the line $\ell_c$ (on the side to which $n$ points), we have

\begin{align} A(c_1) &= 1 \\ A(c_2) &= d_2 \\ A(c_3) &= d_3 \\ A(c_4) &= 0 \end{align} for some numbers $d_2$ and $d_3$ that are determined either by the area of a triangle or one minus the area of a triangle, and I'm going to let you calculate those yourself.

Furthermore, $A$ is piecewise quadratic in $c$, with the "pieces" determined by the $c_i$s (i.e., between any two adjacent $c_i$s, it's given by a single quadratic; outside the $c_i$s, it's a constant (0 on one side, 1 on the other side). And it's differentiable, with the derivative at $c$ being exactly the length of the intersection of $\ell_c$ with the square, so the derivative is a continuous function of $c$.

There's a slight subtlety here: when the moving line passes through two corners simultaneously, the derivative is no longer continuous at that value of $c$. This can happen only for horizontal, vertical, or 45-degree diagonal lines.

Aside from these special cases, $A(c)$ is a piece-wise quadratic function that has the specified values at the breakpoints and has continuous derivative. Fortunately...that's exactly what you get when you make a quadratic B-spline with the $c_i$ as the knots and the $d_i$ as the control values. And when knots are duplicated (as in the subtle case mentioned above), B-spline continuity decreases! So in fact B-splines are the solution you're looking for in all cases.

Once you know the formula for $A(c)$ (using B-splines), you need only apply it to find $A(c + d/2) - A(c - d/2)$ and you've got your intersection area (where here "c" is the constant term for your original equation, after scaling so that $a^2 + b^2 = 1$, rather than some generic value of $c$).

Of course, you have three other cases to work out (slope greater than one, and negative slope less than or greater than $-1$). It's probably best to simplify by first multiplying through so that $b \ge 0$ in all cases, so that you only have four cases instead of 8.

In short: it's a bunch of work, and no fun at all.