1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Martigan Nov 10 '14 at 13:20
  • $\begingroup$ 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. $\endgroup$ – John Hughes Nov 10 '14 at 13:21
  • $\begingroup$ @Martigan The square sides are perpendicular to the x and y axis, Edited $\endgroup$ – Gioelelm Nov 10 '14 at 13:25
  • $\begingroup$ @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". $\endgroup$ – Gioelelm Nov 10 '14 at 13:30
  • $\begingroup$ 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. $\endgroup$ – John Hughes Nov 10 '14 at 13:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.