tag:blogger.com,1999:blog-71141318914133781.post5027290482604149650..comments2022-08-17T22:58:19.983+12:00Comments on Eyes Above The Waves: HomeworkRoberthttp://www.blogger.com/profile/01801341049800948737noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-71141318914133781.post-39985638693971369922009-08-11T18:01:36.000+12:002009-08-11T18:01:36.000+12:00Oh, never mind, I see it. It's a typography t...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.<br>VanillaMozillanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-49392251549235626902009-08-11T16:59:34.000+12:002009-08-11T16:59:34.000+12:00Second problem.1) Create vector line A perpendicul...Second problem.<br>1) Create vector line A perpendicular to V.<br>2) Translate out of range of rects (large positive away from origin.)<br>3) step offset of A toward origin and check for intersection with any rect.<br>4) if intersection, translate rect by V.<br>5) repeat 3 -4 until done.<br>Lots of details but it is a "proof" of sorts that there is always an solution and an order.<br>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.<br>It's a start.<br>Charlesnoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-13014017160907400342009-08-11T12:00:02.000+12:002009-08-11T12:00:02.000+12:00If I get this correctly, we have to find the small...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|.<br>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.<br>Solving for t, and multiplying with |q|/|q| gives<br>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.<br>Sjoerd Visscherhttp://w3future.com/weblog/noreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-65127052759549171022009-08-10T15:46:07.000+12:002009-08-10T15:46:07.000+12:00"consider the family of circles Ct, where t i..."consider the family of circles Ct, where t is a positive real number,...." "...find the smallest value of t such that the circle Ct...."<br>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"?<br>Must be an interesting problem. Evidently other people are better at guessing than I am.<br>VanillaMozillanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-47516159558117903002009-08-10T12:09:43.000+12:002009-08-10T12:09:43.000+12:00Sorry, ignore my last post, for some reason I'...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...<br>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.<br>Damiannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-82637599848368380212009-08-10T12:03:53.000+12:002009-08-10T12:03:53.000+12:00Also it should be noted that the assumption clearl...Also it should be noted that the assumption clearly needs to be stronger than: |p| < r.<br>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).<br>Damiannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-26715418464754693212009-08-09T20:24:20.000+12:002009-08-09T20:24:20.000+12:00I worked out a simplified case of the first proble...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...<br>Not a bad way to fall asleep.<br>Bonoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-18043764758826627972009-08-09T17:52:41.000+12:002009-08-09T17:52:41.000+12:00Assuming I typed the question in correctly, Wolfra...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).<br>Neil Rashbrookhttp://neil.rashbrook.org/noreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-47261502181378084242009-08-09T15:02:54.000+12:002009-08-09T15:02:54.000+12:00For the first one, I got as far as noticing that C...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.<br>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.<br>Neil Rashbrookhttp://neil.rashbrook.org/noreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-63921975376155970992009-08-09T12:33:40.000+12:002009-08-09T12:33:40.000+12:00It's been a while since I did a nice maths pro...It's been a while since I did a nice maths problem. Let me give this a go:<br>I assume all of this exists in R^2? Let p = (m,n). Then the family of circles is:<br>C_t = {x - tm)^2 + (y - tn)^2 = t^2 r^2 | for all real solutions of (x,y)}<br>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:<br>t = (mu + nv +/- Sqrt[(-n^2 + r^2) u^2 +<br>2mnuv + (-m^2 + r^2) v^2])/(m^2 + n^2 - r^2)<br>And the assumption made is:<br>2mnuv + r^2(u^2 + v^2) > n^2u^2 + m^2v^2<br>or more simply:<br>r^2|q| > (nu - mv)^2<br>Geometry was never my strongest subject, did I make a mistake somewhere or did you find a simpler way of expressing this :)?<br>As for the other one, what is the definition of "axis-aligned rectangles"?<br>Damiannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-87189631143219618882009-08-09T06:25:10.000+12:002009-08-09T06:25:10.000+12:00For the rectangle one, I think you want to transfo...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... ;)<br>James Napolitanonoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-35817382865051436302009-08-09T05:44:29.000+12:002009-08-09T05:44:29.000+12:00Haven't done some of this stuff for awhile. I...Haven't done some of this stuff for awhile. I tried the first one.<br>Eqn for Circle Ct is:<br>(x - t * px)^2 + (y - t * py)^2 = t * r^2<br>Solving for t we get a quadratic equation. I get:<br>A * t^2 + B * t + C = 0<br>where A = (px^2 + py^2)<br>B = - (2* qx * py + 2 * qy * py + r^2)<br>C = (qx^2 + qy^2)<br>The minima of this quadratic curve occurs when the tangent is zero, so take derivative:<br>2 * A *tmin + B = 0<br>tmin = -B / 2 * A<br>thus:<br>tmin = (2 * qx * px + 2 * qy * py + r^2) / 2 * (px^2 + py^2)<br>Was I even close? :)<br>Jeff Schillerhttp://blog.codedread.com/noreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-8807871951103105772009-08-09T05:25:09.000+12:002009-08-09T05:25:09.000+12:00Ah, this reminds me of mathletes...For the circle ...Ah, this reminds me of mathletes...<br>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...<br>James Napolitanonoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-25115813682153135622009-08-09T04:51:20.000+12:002009-08-09T04:51:20.000+12:00I really like the second one: intuitive, but a bit...I really like the second one: intuitive, but a bit tricky to prove.<br>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?<br>MauricioCnoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-20987172317112462042009-08-09T04:00:32.000+12:002009-08-09T04:00:32.000+12:00Let p = (a,b) and q = (c,d); then by expanding dot...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).<br>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.<br>That would probably be slower in practice than a simple heuristic and collision testing the translated rectangles to guarantee no overlaps.<br>I don't see any situation in which such an order couldn't be found...<br>Ben Karelhttp://eschew.org/noreply@blogger.com