0
$\begingroup$

How can I calculate if a rectangle with a specific height and width fits in an arc-formed slice, centered around a certain point?

Context: I have to determine if there's enough space in the slice to show a (centered) text.

The attached image is probably self-explanatory, but just in case:

  • Red dot: center of the slice and rect/text.
  • Blue rect: Max rect available given fixed height and center.
  • Black arcs: The slices.

I basically need to calculate the blue rects in order to know if the text fits.

enter image description here

Edit:

I think the problem can be simplified as follows:

enter image description here

After re-thinking this, I noticed that the arcs are actually irrelevant. The programmer of the chart can decide the radius at which the label is displayed, so if the label happens so overflow the arcs they can just change the radius (or the size (outer radius - inner radius) of the arcs).

I only need the width and height of the yellow area as displayed in image above to know if the label fits in or not. Looks like something that can be solved with trigonometry?

Edit 2: Solved!

With amd's orientation and some additions I was able to solve it (the last problem - the arcs are not considered).

(Actually, I should have been able to solve this on my own, but when I opened the question I thought the arcs were relevant and after it went lazy mode ;))

enter image description here

Essentially:

  1. Determine if h/2 < i1.y distance and i2.y distance, if h doesn't fit calculation ends here. To calculate y of i1 and i2 I use $y=x\tan\phi$. I of course have to translate my coord system to center and invert the angle (to counter-clock).

  2. Calculate i1, i2, i3 and i4 using $x=y\cot\phi$.

  3. Select min x distance to center of i1, i2, i3 and i4

  4. Multiply result of 3. with 2, this is rect's width. Together with h, I get the rect I'm looking for. Now I only have to check if my label's rect fits inside of this rect.

Result after being implemented:

enter image description here

This causes the desired effect for the labels:

enter image description here

$\endgroup$
17
  • $\begingroup$ wow, you've got some major skillz $\endgroup$ – Yorch Dec 27 '16 at 21:38
  • 2
    $\begingroup$ @JorgeFernándezHidalgo yeah I drew the grey circle, the rest was computer generated ;) $\endgroup$ – User Dec 27 '16 at 21:40
  • $\begingroup$ how is your arc parametrized? $\endgroup$ – Yorch Dec 27 '16 at 21:42
  • $\begingroup$ I have start angle, end angle, inner radius and outer radius. $\endgroup$ – User Dec 27 '16 at 21:43
  • 1
    $\begingroup$ oh ok, let me try :) $\endgroup$ – Yorch Dec 27 '16 at 22:12
1
$\begingroup$

Based on your comments to the question, it appears that what you’re really trying to find out is whether or not a rectangle of fixed dimensions will fit in the region when centered on the “center” of the region given by $$\begin{align}x_c&={r_{\text{inner}}+r_{\text{outer}}\over2}\cos{\phi_1+\phi_2\over2} \\ y_c&={r_{\text{inner}}+r_{\text{outer}}\over2}\sin{\phi_1+\phi_2\over2}. \end{align}$$ For the rectangle to fit, its corners must lie within the annulus defined by the two arcs and also within the sector defined by the two angles. This can be determined with a few straightforward tests. There’s also a slight complication due to convexity of the inner arc, but that’s also easily dealt with.

I’m assuming a left-handed Cartesian coordinate system with angles increasing counterclockwise. First, translate so that the center of the arcs is at the origin. Label the two angles so that the region is swept out counterclockwise from $\phi_1$ to $\phi_2$. Let the width and height of the rectangle be $2w$ and $2h$, respectively, so that its corners are $(x_c\pm w,y_c\pm h)$.

We want the corners to be counterclockwise of $\phi_1$ and clockwise of $\phi_2$. This can be determined by examining the signs of certain determinants or cross products. Taking $u_1=(\cos\phi_1,\sin\phi_1)$, a unit vector in direction of $\phi_1$, compute the “cross product” of each corner with this vector: $x\sin\phi_1-y\cos\phi_1$. If this is positive, then that corner is clockwise of that side of the region and so the rectangle doesn’t fit. Do the same for $\phi_2$, except this time the test fails if the cross product is negative. If you happen to have the corners of the region handy, you can use them instead of computing unit vectors for the two angles.

If the corners have passed both of those tests, compare their distances from the origin to the inner and outer radii. I assume that you know how to do this.

Finally, if the rectangle crosses a coordinate axis, there’s a possibility that a side passes inside the inner arc even though the corners are outside of it. Most cases of this will have been caught already by the angle test, but one case still remains: the region and rectangle both cross an axis. So, check to see if either the $x$- or $y$-coordinates (or both) of the rectangle’s corners have opposite signs. If they do, and the inner arc also crosses the same axis, which you can determine by examining the two angles, compare the coordinate of the appropriate inner edge of the rectangle to the inner radius. For example, if $y_c-h\le0\le y_c+h$ and $\phi_1\le\pi\le\phi_2$, then check that $x_c-w\ge r_{\text{inner}}$ if $x_c>0$, or $x_c+w\le-r_{\text{inner}}$ if $x_c<0$. If it isn’t, the rectangle doesn’t fit despite passing the other tests. If you don’t want to do a case-by-case test, apply a couple of reflections so that the center point is in the first quadrant. Then you only have to check the left and/or bottom edges for $\ge r_{\text{inner}}$, if necessary.


For the related problem of finding how much horizontal space is available for a rectangle vertically centered on $y=y_c$, you’re going to be computing intersections of horizontal lines with rays originating in the origin. Finding these intersection points is simple: the line $y=b$ intersects a line with angle $\phi$ that passes through the origin at $x=b\cot\phi$. When $\phi$ is a multiple of $\pi$, the ray is parallel to the given line, so it’s not going to provide a left or right bound for the rectangle, but you do need to check for sufficient vertical space in that case.

As with the convexity check above, I suggest flipping the $y$-axis if necessary so that $y_c>=0$. This will reduce the number of cases to consider and clearly won’t affect the horizontal calculations. As before, label the two angles so that the region is swept out counterclockwise from $\phi_1$ to $\phi_2$.

Let’s look at the top of the rectangle first, since that’s simpler. The ray at $\phi_1$ will bound the rectangle on the right if $0\lt\phi_1\lt\pi$. Similarly, the ray at $\phi_2$ will bound the rectangle on the left when $0\lt\phi_2\lt\pi$.

The bottom of the rectangle requires a bit more care. If $y_c-h\ge0$, we have the same situation as above. If $y_c-h\lt0$, on the other hand, the $\phi_1$ ray can’t provide a right-side bound, but it does give a left bound if $\pi\lt\phi_1\lt2\pi$. Similarly, the $\phi_2$ ray gives a right bound when $\pi\lt\phi_2\lt2\pi$. When both $\phi_1$ and $\phi_2$ are between $0$ and $\pi$ with the bottom of the rectangle at or below the $x$-axis, no rectangle will fit.

Take the largest left bound and the smallest right bound that you get from the above. If you end up with a left bound that’s not less than the right bound, then there’s no rectangle that will fit and the radii will have to be adjusted. If you end up with no bound on one side or the other, you’ll need to look at intersections with the bounding arcs to see what fits. Finally, if you want the box to be horizontally centered on $(x_c,y_c)$, then you’ll of course need to trim the longer side.

$\endgroup$
3
  • $\begingroup$ Quick note: I added a new image (was doing this while I got the notification of your post) to express the problem a bit better. Just in case that the first description is not understandable enough. I'll come back to this soon when I have time again, thanks! $\endgroup$ – User Dec 28 '16 at 0:52
  • $\begingroup$ P.S. Very sorry for simplifying the problem belatedly. I'll select your answer in any case if I can solve the basic problem with it. $\endgroup$ – User Dec 28 '16 at 1:11
  • $\begingroup$ I was able to solve it, thanks a lot! (see edited question). I may come back i the future to check the arcs part ;), thanks also for this $\endgroup$ – User Dec 29 '16 at 14:22

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.