Saturday 8 August 2009
Homework
Two interesting problems I've had to solve this week...
Given a point p and a radius r, consider the family of circles Ct, where t is a positive real number, with centres tp and radii tr. Given a point q, find the smallest value of t such that the circle Ct contains q. You may assume |p| < r. This came up while I was optimizing repeating radial gradients for Mac.
Given a set of non-overlapping axis-aligned rectangles in the plane, and a 2D vector v, order the rectangles in a sequence so that translating each rectangle one by one by v does not have any overlapping rectangles in the intermediate states. Does such an order always exist? This came up while I worked on optimizing scrolling.
Comments
For the second one, I guess you can immediately narrow the candidates at each step of an iterative solution to those forming the convex hull around the as-yet-unmoved rectangles, and further to those forming v's "side" of the hull. I don't see any immediately elegant solution for choosing which one on the hull to move, except perhaps for smallest first. Perhaps this: choose the largest candidate rectangle, and sweep the line parallel to perp(v), in the direction of (-v), until you hit the second corner (or if v itself is axis aligned, the other side), marking any other rectangles that are touched by the line. Those should be (recursively?) moved first.
That would probably be slower in practice than a simple heuristic and collision testing the translated rectangles to guarantee no overlaps.
I don't see any situation in which such an order couldn't be found...
Do you have any geometric intuition for the formula for the first problem, though? Also, is binary searching for the answer numerically saner than using a closed formula?
For the circle problem, I introduced a variable theta for the angle between the x axis and the radius joining points tp and q. I set up formulas for the x and y coordinates of q, and with some trig identities I ended up with a quadratic equation for t. (then you could use t to solve for tan(theta)). And now I realize I could've gotten that much quicker by just using vector math from the start...
Eqn for Circle Ct is:
(x - t * px)^2 + (y - t * py)^2 = t * r^2
Solving for t we get a quadratic equation. I get:
A * t^2 + B * t + C = 0
where A = (px^2 + py^2)
B = - (2* qx * py + 2 * qy * py + r^2)
C = (qx^2 + qy^2)
The minima of this quadratic curve occurs when the tangent is zero, so take derivative:
2 * A *tmin + B = 0
tmin = -B / 2 * A
thus:
tmin = (2 * qx * px + 2 * qy * py + r^2) / 2 * (px^2 + py^2)
Was I even close? :)
I assume all of this exists in R^2? Let p = (m,n). Then the family of circles is:
C_t = {x - tm)^2 + (y - tn)^2 = t^2 r^2 | for all real solutions of (x,y)}
If q = (u,v) then the smallest t such that the circle encompasses q is such that (u,v) exists on the circumference of C_t, so we can substitute (x,y) for (u,v) and re-arrange for t? Gives me the rather awkward answer of:
t = (mu + nv +/- Sqrt[(-n^2 + r^2) u^2 +
2mnuv + (-m^2 + r^2) v^2])/(m^2 + n^2 - r^2)
And the assumption made is:
2mnuv + r^2(u^2 + v^2) > n^2u^2 + m^2v^2
or more simply:
r^2|q| > (nu - mv)^2
Geometry was never my strongest subject, did I make a mistake somewhere or did you find a simpler way of expressing this :)?
As for the other one, what is the definition of "axis-aligned rectangles"?
For the second one, if you can assume that it is impossible to have a cycle of potentially overlapping rectangles, then there is always one movable rectangle, and once moved, this rectangle plays no further part thus simplifying the problem and hence by induction the original problem is solved. This is trivially true for a single rectangle, but is also intuitively true for two rectangles R1 and R2; if R2 overlaps R1+v at a point P1 and R1 overlaps R2+v at a point P2+v then we also have R2-v overlaps R1 at a point P1-v and R1-v overlaps R2 at a point P2 so that R2 overlaps R1 at the point halfway between P1 and P2 (which is obviously in R2) or in terms of R1, halfway between P2+v and P1-v (which is obviously in R1). I wonder whether the original question is true for all convex polygons.
Not a bad way to fall asleep.
Let p = (1/2, 1/2) and r = 1/4. Then no matter how large t, the circle will never encompass the origin (0,0).
Obviously now it's clear that all points can be encompassed for a large enough t. As there exist points in all 4 quadrants encompassed by the circle and the circle carries on growing with the proportions between all 4 quadrants remaining equal.
You misstated the problem. You didn't define Ct in terms of a real number t. In fact, t is not mentioned anywhere else in the problem. Perhaps you meant that t is a vector (tp, tr)??? But then what do you mean by "the smallest value of t"?
Must be an interesting problem. Evidently other people are better at guessing than I am.
This gives me s = |p.n +/- sqrt((p.n)^2 + r^2 - p.p)|. If p.n > 0 then adding the sqrt gives the biggest s, else substracting does.
Solving for t, and multiplying with |q|/|q| gives
t = |q.q / (p.q +/- sqrt((p.q)^2 + (r^2 - p.p) * (q.q)))|, with again the choice of +/- depending on the sign of p.q.
1) Create vector line A perpendicular to V.
2) Translate out of range of rects (large positive away from origin.)
3) step offset of A toward origin and check for intersection with any rect.
4) if intersection, translate rect by V.
5) repeat 3 -4 until done.
Lots of details but it is a "proof" of sorts that there is always an solution and an order.
If there is a tie for the Intersection as long as the "step" (dx) is small enough, then it will still translate without intersection. Also, only check for intersection of non-translated rects.
It's a start.