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.



Posted by Robert at 10:21 PM
Labels:

15 comments:

  1. 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...
    ReplyDelete
  2. 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?
    ReplyDelete
  3. James NapolitanoAug 8, 2009 10:25 AM
    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...
    ReplyDelete
  4. 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? :)
    ReplyDelete
  5. James NapolitanoAug 8, 2009 11:25 AM
    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... ;)
    ReplyDelete
  6. 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"?
    ReplyDelete
  7. 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.
    ReplyDelete
  8. 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).
    ReplyDelete
  9. 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.
    ReplyDelete
  10. 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).
    ReplyDelete
  11. 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.
    ReplyDelete
  12. VanillaMozillaAug 9, 2009 08:46 PM
    "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.
    ReplyDelete
  13. 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.
    ReplyDelete
  14. 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.
    ReplyDelete
  15. VanillaMozillaAug 10, 2009 11:01 PM
    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.
    ReplyDelete

Subscribe to: Post Comments (Atom)