2
$\begingroup$

Suppose I have a rectangle with its center point located on the circumference of a disk or circle.

How can I move the rectangle along the radius just enough so that it does not overlap the disk anymore? That is, how to calculate the new center point of the rectangle or (x′,y′)?

The image illustrating the problem

I have these parameters available:

  • r: radius of the circle (maybe irrelevant)
  • θ: angle of radius
  • w, h: width and height of the rectangle
  • (x,y): coordinates of the current center point of the rectangle (starting yellow dot)

I tried the following but it does not result in what I want:

$$x' = x + \frac{w}{2} * \cos \theta$$ $$y' = y + \frac{h}{2} * \sin \theta$$

It should work for any angle. Another example:

Another example image

$\endgroup$
0
6
$\begingroup$

You actually have two constraints:

  1. The center of the rectangle (yellow dot) must remain on the ray from the circle's center that makes an angle $\theta$ with the positive $x$-axis.
  2. The point(s) on the boundary of the rectangle nearest to the center of the circle must lie on the circle's circumference.

As a result, you cannot first locate the yellow dot and then translate it outward by the half-width and half-height of the rectangle (as suggested by another answer), because for a rectangle of general dimensions, this will change the position of the yellow dot in such a way that it no longer necessarily meets criterion (1) above.

To simplify the problem, let us consider without loss of generality the case $0 \le \theta \le \pi/2$ and $r = 1$, since the other quadrants behave similarly via symmetry about the coordinate axes, and $w, h$ can be rescaled for $r \ne 1$. Also, let us assume that $h^2 + w^2 < 4$ as suggested by your diagrams (the case where $h^2 + w^2 > 4$ will need separate treatment).

Then, the first thing to observe is that there is a critical interval for which the nearest point as described in constraint (2) is the lower left vertex of the rectangle, and there are two other intervals such that the nearest point is actually located on a side of the rectangle. You show one of these cases in your second diagram, where $\theta = 0$ and the nearest point is located on the left side of the rectangle.

Indeed, it is not difficult to see that it is when the bottom edge of the rectangle coincides with the $x$-axis that the nearest point on the rectangle to the circle's center will transition from a point on the left edge, to the lower left vertex. That is to say, when $$\sin \theta = \frac{h}{2},$$ this is where the transition occurs. Similarly, another transition occurs when $$\cos \theta = \frac{w}{2},$$ where the nearest point changes from the lower left vertex to the bottom edge of the rectangle. So we must consider these three cases separately: $$\theta \in \left[0, \arcsin \frac{h}{2} \right), \\ \theta \in \left[\arcsin \frac{h}{2}, \arccos \frac{w}{2} \right], \\ \theta \in \left(\arccos \frac{w}{2}, \frac{\pi}{2}\right].$$

In all three cases, we first let the yellow point be $(x,y) = (\cos \theta, \sin \theta)$. Then in the first case, the point nearest to the center is $$(p,q) = (\cos \theta - w/2, 0),$$ because among all points on the left edge of the rectangle, the one that minimizes the distance to the center is the one with zero $y$-coordinate. We must then find a translation $$(x',y') = (x,y) + (a,b), \\ (p', q') = (p,q) + (a,b)$$ such that $(x',y')$ has angle $\theta$ (i.e., $\frac{y'}{x'} = \tan \theta$), and $(p')^2 + (q'^2) = 1$--that is, the translation puts $(p,q)$ on the circumference. This results in the system $$\frac{b + \sin \theta }{a + \cos \theta} = \tan \theta, \\ (\cos \theta - w/2 + a)^2 + b^2 = 1.$$ Although it is only quadratic, the result is lengthy so we will show it without proof: $$(a,b) = \left(\frac{1}{2} \cos^2 \theta \left(\sqrt{\tan^2 \theta \left(4 w \cos \theta - w^2 + 4\right) + 4 \cos ^2 \theta } - 2 \cos \theta + w \right), \\ \frac{1}{2} \sin \theta \cos \theta \left(\sqrt{\tan^2 \theta \left(4 w \cos \theta - w^2 + 4 \right) + 4 \cos^2 \theta } - 2 \cos \theta + w \right)\right).$$ Then the new center of the rectangle is $(x',y') = (x,y) + (a,b)$.

For the second case, the vertex $(\cos \theta - w/2, \sin \theta - h/2)$ is the nearest point, and the system we need to solve is $$\frac{b + \sin \theta }{a + \cos \theta} = \tan \theta, \\ (\cos \theta - w/2 + a)^2 + (\sin \theta - h/2 + b)^2 = 1.$$ This yields

$$(a,b) = K(h,w,\theta) (\cos \theta, \sin \theta)$$ where $$K(h,w,\theta) = \frac{1}{2} \left( -2 + h \sin \theta + \cos \theta \left(w + \sqrt{4 - h^2 + 2 h w \tan \theta - (w^2 - 4) \tan^2 \theta } \right) \right). \tag{1}$$

The remaining case is just more of the same kind of calculation, so I have omitted it here. As you can see, the result is not trivial. We could have saved some effort by solving the second case first to obtain the general solution for $K$, then recognized that the (literally!) edge cases correspond to the choices $h = 2 \sin \theta$ or $w = 2 \cos \theta$. We can put it all together in an animation. This is for $r = 1$, $w = 1/2$, $h = 1/4$:

enter image description here

$\endgroup$
2
  • $\begingroup$ Great. Thank you very much. Could you please account for the r in the calculations? I mean assuming it is not equal to 1. $\endgroup$ – Mahozad May 27 at 8:49
  • 2
    $\begingroup$ @Mahozad For a circle of radius r, replace $K(h,w,\theta)$ with $r\cdot K(h/r,w/r,\theta)$. $\endgroup$ – Maxence1402 May 27 at 9:09
0
$\begingroup$

This is nowhere near as elegant as heropup's answer, but leads to a simple, robust, easily implemented, and most importantly extremely efficient algorithm; and may be preferable for programmers.

The downside is that the way the solution was derived is not explained step by step. (This is because it was a combination of geometric examination and software engineering techniques, and involves a single "mathematical" observation (which is described). Consider it an ugly case of how nice, clean math gets applied in real life.)

Instead of a disk, first consider the concept of the distance $d$ from a rectangle to origin: Illustration of three rectangles If $a$ is the signed distance between the rectangle and the $y$ axis, and $b$ is the signed distance between the rectangle and the $x$ axis, both positive if the rectangle is outside that axis, and negative if the axis is within the rectangle, then the distance $d$ between origin and the closest point to origin on the perimeter of the rectangle is $$d = \begin{cases} \sqrt{a^2 + b^2}, & a \ge 0 ~ \text{ and } ~ b \ge 0 \\ \max(0, a, b), & \text{otherwise} \\ \end{cases} \tag{1}\label{G1}$$

If we use polar coordinates $(r, \theta)$ for the center of the rectangle, $$\left\lbrace \begin{aligned} x &= r \cos\theta \\ y &= r \sin\theta \\ \end{aligned} \right. \quad \iff \quad \left\lbrace \begin{aligned} r &= \sqrt{x^2 + y^2} \\ \theta &= \operatorname{atan2}(y, x) \\ \end{aligned} \right.$$ If the rectangle width is $2 w$ and height $2 h$, then $a = r \lvert \cos\theta \rvert - w$, and $b = r \lvert \sin\theta \rvert - h$. Thus, we can write $\eqref{G1}$ as $$d = \begin{cases} \sqrt{ \bigl( r \lvert \cos\theta \rvert - w \bigr)^2 + \bigl( r \lvert \sin\theta \rvert - h \bigr)^2 }, & a \ge w ~\text{ and }~ b \ge h \\ r \lvert \cos\theta \rvert - w, & a \ge w ~\text{ and }~ b \lt h \\ r \lvert \sin\theta \rvert - h, & a \lt w ~\text{ and }~ b \ge h \\ 0, & a \lt w ~\text{ and }~ b \lt h \\ \end{cases} \tag{2}\label{G2}$$ It is important to notice that $d$ is a monotonically increasing function in $r$, for any (constant) $\theta$. This means that if $\theta$ stays constant for a specific rectangle, we can always find the $r$ when given a positive $d$, and the $d$ when given a large enough positive $r$ (so that origin is outside the rectangle).

The following simple algorithm will find $r$ when given $d \gt 0$ (d), $\lvert\cos\theta\rvert$ (abscos), $\lvert \sin\theta\rvert$ (abssin), $w$ (halfwidth), and $h$ (halfheight); returning $r = 0$ if the origin is inside the rectangle:

Function CenterDistance(d, abscos, abssin, halfwidth, halfheight):
    Let cross = abscos*halfheight - abssin*halfwidth
    If d*d >= cross*cross Then
        Let r = abscos*halfwidth + abssin*halfheight + sqrt(d*d - cross*cross)
        Let a = r*abscos - halfwidth
        Let b = r*abssin - halfheight
        If a > 0 And b > 0 Then
            Return r
        Else If a > 0 Then
            Return (d + halfwidth) / abscos
        Else If b > 0 Then
            Return (d + halfheight) / abssin
        Else
            Return 0
        End If
    Else
        If cross > 0 Then
            Return (d + halfwidth) / abscos
        Else if cross < 0 Then
            Return (d + halfheight) / abssin
        Else
            Return 0
    End If
End Function

As you can see, the function needs no trigonometric functions, only the magnitudes of the unit direction vector along which the rectangle may move ($\lvert\cos\theta\rvert$ and $\lvert\sin\theta$ as abscos and abssin, respectively). When implemented in a computer program, this function is extremely fast – the square root is the "slowest" operation in here.

Mathematically, it is a straightforward case-by-case inverse of $\eqref{G2}$, with the only "trick" being that when $d^2 \lt \left( \lvert \cos\theta \rvert h - \lvert\sin\theta\rvert w \right)^2$, $\lvert \cos\theta \rvert h - \lvert \sin\theta \rvert w$ is positive if $a$ is positive and $b$ negative, negative if $a$ is negative and $b$ positive, and zero if both $a$ and $b$ are negative.

I wish I could explain the algorithm in better mathematical terms, but I'm not a mathematician; apologies.

I can, however, show you the following simple Python 3 implementation licensed under Creative Commons Zero 1.0 Universal license, that generates randomly sized axis-aligned rectangles, finds their distance $d$ from origin, and for those for which $d \gt 0$, computes the distance $r$ along the given direction where the rectangle center should be based on the $d$ using the exact algorithm described above, and finally compares the $r$ to the actual distance from the center of the rectangle to origin. Since the absolute error in $r$ stays within rounding error, the program "proves" (in the numerical sense) that the algorithm works correctly.

#!/bin/env python3 -B
# -*- encoding: utf-8 -*-
# SPDX-License-Identifier: CC0-1.0

from math import sqrt
from random import Random

def distance(centerx, centery, halfwidth, halfheight):
    a = abs(centerx) - halfwidth
    b = abs(centery) - halfheight
    if a > 0 and b > 0:
        return sqrt(a*a + b*b)
    else:
        return max(0, a, b)

def radius(d, abscos, abssin, halfwidth, halfheight):
    cross = abscos*halfheight - abssin*halfwidth
    if d*d >= cross*cross:
        r = abscos*halfwidth + abssin*halfheight + sqrt(d*d - cross*cross)
        a = r*abscos - halfwidth
        b = r*abssin - halfheight
        if a > 0 and b > 0:
            return r
        elif a > 0:
            return (d + halfwidth) / abscos
        elif b > 0:
            return (d + halfheight) / abssin
        else:
            return 0
    else:
        if cross > 0:
            return (d + halfwidth) / abscos
        elif cross < 0:
            return (d + halfheight) / abssin
        else:
            return 0
    endif

uniform = Random().uniform
n = 0
rmaxerr = 0

while True:
    try:
        centerx = uniform(-5.0, 5.0)
        centery = uniform(-5.0, 5.0)
        halfwidth = uniform(0.0, 5.0)
        halfheight = uniform(0.0, 5.0)

        d = distance(centerx, centery, halfwidth, halfheight)
        if d <= 0.0:
            continue

        correct_r = sqrt(centerx*centerx + centery*centery)
        abscos = abs(centerx / correct_r)
        abssin = abs(centery / correct_r)

        r = radius(d, abscos, abssin, halfwidth, halfheight)

        rerr = abs(r - correct_r)
        if rmaxerr < rerr:
            print("x=%.6f, y=%.6f, w/2=%.6f, h/2=%.6f, d=%.6f, r=%.6f, calculated r=%.6f, absolute error %.9g" %
                  (centerx, centery, halfwidth, halfheight, d, correct_r, r, rerr))
            rmaxerr = rerr

        n += 1
        if n % 100000 == 0:
            print("After %d tests, maximum absolute error in r is %.9g" % (n, rmaxerr))
    except KeyboardInterrupt:
        print("After %d tests, maximum absolute error in r is %.9g" % (n, rmaxerr))
        break

When run (e.g.python3 -B test.py), it outputs each case that yields the new maximum absolute error in the position (distance along the ray we move the center of the rectangle along); and the current maximum error every 100,000 tests (rectangles for which $d \gt 0$). You can stop the process at any time via keyboard interrupt (Ctrl+C, or by sending the Python process a SIGINT signal in Linux, Mac OS, or BSDs).

$\endgroup$
1
  • $\begingroup$ It turns out that this can actually be extended to the case where the center of the rectangle is moved along an arbitrary line, not necessarily one through origin. In that case, the location is not continuous function, but has "jumps" where the distance is such that the rectangle needs to cross $x$ or $y$ coordinate axes. (So, technically, the line along which the rectangle is moved can be split into up to five line segments, with the two gaps having a single solution point in the middle of the gap.) $\endgroup$ – Glärbo Jun 10 at 7:03

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.