« Idiots | Main | Winter's Day On The West Coast »
August 8, 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.
Posted by roc at August 8, 2009 10:21 AM
Comments
Let p = (a,b) and q = (c,d); then by expanding dot(tp-q, tp-q) = r^2, and rearranging, we get t^2x - 2ty + z = 0, where x = (a^2 + b^2 - r^2), y = (bd + ac), and z = (c^2 + d^2). Apply the quadratic formula to get t = (2*y +- sqrt(4*y^2 - 4*x*z))/(2x).
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...
Posted by: Ben Karel at August 8, 2009 4:00 PM
I really like the second one: intuitive, but a bit tricky to prove.
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?
Posted by: MauricioC at August 8, 2009 4:51 PM
Ah, this reminds me of mathletes...
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...
Posted by: James Napolitano at August 8, 2009 5:25 PM
Haven't done some of this stuff for awhile. I tried the first one.
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? :)
Posted by: Jeff Schiller at August 8, 2009 5:44 PM
For the rectangle one, I think you want to transform your coordinates into the uv plane, where u is orthogonal to v. Then you might do something like order the rectangles by the v coordinates of their corners, and when 2 rectangles have overlapping v coordinates, go by the u coordinate. But it's too late here to work out the details now. And I hope you're not allowing for infinite sequences of rectangles... ;)
Posted by: James Napolitano at August 8, 2009 6:25 PM
It's been a while since I did a nice maths problem. Let me give this a go:
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"?
Posted by: Damian at August 9, 2009 12:33 AM
For the first one, I got as far as noticing that Ct is described in terms of an angle θ as (tpx + tsinθ, tpy + tcosθ) = t(px + sinθ, py + cosθ) and therefore if Q lies on Ct then the line OQ crosses C1 at a point OQ/t.
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.
Posted by: Neil Rashbrook at August 9, 2009 3:02 AM
Assuming I typed the question in correctly, Wolfram Alpha says t = (ax + by + √(r²(x² + y²) - (ay - bx)²))/(a² + b² - r²) where p = (a, b) and q = (x, y).
Posted by: Neil Rashbrook at August 9, 2009 5:52 AM
I worked out a simplified case of the first problem in my head last night as I was falling asleep. I started to think about the more general case, but my thoughts faded out before I could think about it clearly...
Not a bad way to fall asleep.
Posted by: Bo at August 9, 2009 8:24 AM
The solution to problem 2, I think, is this. First, note that if moving a rectangle A causes it to overlap another rectangle B, rectangle B must be in its original position. If it were not, A and B would be overlapping in their original positions, which is contrary the original constraint. We therefore only have to consider the rectangles not yet moved.
We will assume that v does not have 0 in one of its positions--if it does, we can find the order of rectangles by merely ordering them by their leading edges (the ones most in the direction of v).
Restrict the rectangles to consider moving out to those along the two edges of the containing rectangle in the direction of v (e.g., if v has positive x and y, look at the edges where x is a positive number and y is a positive number, assuming the origin to be the center of the containing rectangle). If you move one of these rectangles, at most two of its vertices will remain with the containing rectangle of that which remains.
Assume without loss of generality that v's coordinates are positive (just reflect everything if not), and that we pick among the rectangles with maximum x. I will also refer to the sides of the rectangle with higher x and higher y as "leading edges."
If none remain, then the rectangle is clearly not overlapping any of the existing rectangles, so its move was safe. Since it intersects another rectangle, the other rectangle's leading y coordinate is greater than the moved rectangle's. Without loss of generality, we will assume that among the rectangles with a maximum x coordinate, we chose the one with the maximum y. So the overlapping rectangle must be less than the moved rectangle in the x coordinate.
Consider moving the overlapped rectangle instead. Either this causes you to break free, or it overlaps a rectangle. If it overlaps a rectangle, that one's leading edge's x coordinate must be greater than the one we tried instead. We could try moving this again, but we should first see if there will be a guaranteed end to our frustrations.
If moving the rectangle with the highest x leading edge along the outer rectangle's leading y edge overlaps another rectangle, and if moving the rectangle with highest y leading edge along the outer rectangle's leading x edge overlaps another rectangle, the overlapped rectangle(s) must be at least partially within the region defined by the leading edges of the upper (higher y), more right (higher x), and the outer rectangle. If both overlap with a rectangle wihtin this inner region, one of these rectangles must lie wholly within the region. So we can see that clearing this region out will cause you to be able to move at least one of the outer rectangles. We can move these recursively until we find a single rectangle in the defined region, which is safe to move.
We can therefore guarantee an order, but the more important question is being able to easily find this. The simplest solution is to try to move a rectangle and see if it overlaps. This solution is O(n*f(n)), where f(n) is the cost of seeing if a rectangle overlaps another. The naïve implementation for f(n) is O(n), but a clever pre-sorting algorithm might be able to do it in O(lg n).
In looking at this problem, I believe there exists an elementary function f(p, d, v) (p being the position of one point on the rectangle, d being a diagonal of the rectangle, and v as specified) which will return values such that, when listed in decreasing order, will specify the order of the rectangles to move. An algorithm using this will be O(n lg n + n), i.e. a sort and then a simple iteration.
As for the definition of function f, my intuition is telling me that it is computed as the v-coordinate (in a transformed basis) of some metric of the rectangle. However, I have found counter examples to my guesses of certain corners and the center. I know believe that it may be related to the diagonals: I'm guessing now that it is the v-coordinate of where the line formed by extending diagonal formed by the leading edges (i.e., if you look at the leading edges and pick this diagonal, you get a triangle, not a point with three line segments) intersects the v-axis. I put the origin at the center of the region-defining rectangle, but any point will do, since you're merely looking at relative values. I welcome anybody to prove me wrong.|
Posted by: Joshua Cranmer at August 9, 2009 12:31 PM
Also it should be noted that the assumption clearly needs to be stronger than: |p| < r.
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).
Posted by: Damian at August 10, 2009 12:03 AM
Sorry, ignore my last post, for some reason I'd got the inequality the wrong way around in my head. Obviously if |p| < r then for t=1 the origin will always be encompassed...
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.
Posted by: Damian at August 10, 2009 12:09 AM
"consider the family of circles Ct, where t is a positive real number,...." "...find the smallest value of t such that the circle Ct...."
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.
Posted by: VanillaMozilla at August 10, 2009 3:46 AM
If I get this correctly, we have to find the smallest t such that |tp - q| = tr. This can be simplified to finding the biggest s such that |p - sn| = r with s = |q| / t and n = q / |q|.
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.
Posted by: Sjoerd Visscher at August 11, 2009 12:00 AM
Second problem.
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.
Posted by: Charles at August 11, 2009 4:59 AM
Oh, never mind, I see it. It's a typography thing, not very visible on my monitor. Arghh. p is a vector, so tp is also a vector. I like Sjoerd Visscher's vector approach. Will post my solution on the other thread.
Posted by: VanillaMozilla at August 11, 2009 6:01 AM