一个扇区的2D边界框？

Question

我用谷歌搜索直到我脸色发青,除非我遗漏了一些非常明显的东西,否则我找不到任何算法来计算2D扇区的边界框.

给定封闭圆的中心点,半径和扇区范围的角度,计算该扇区的轴对齐边界矩形的最佳算法是什么？

Answer 1

• 生成以下几点:
  • 圆圈的中心
  • 两个半径在圆上的位置
  • 两个之间每个角度的圆上的点除以90 ^o(最多4个点)
• 从上述点计算最小值和最大值x和y.这是你的边界框

Answer 2

我要改写yairchu的答案,以便更清楚(对我来说,无论如何).

暂时忽略中心坐标并在原点绘制圆.说服自己以下内容:

1. 弧与轴相交的任何地方都是最大值或最小值.
2. 如果圆弧不与轴相交,则中心将是边界矩形的一个角,这是唯一的情况.
3. 该部门唯一需要考虑的其他可能的极点是半径的终点.

您现在最多可以找到4 + 1 + 2个点.找到绘制矩形的坐标的最大值和最小值.

通过将原始圆心的坐标添加到矩形的坐标,可以将矩形轻松转换为原始圆.

Answer 3

首先，如果我犯了写作错误，我深表歉意，但英语不是我的母语，西班牙语实际上是！

\n\n

我遇到了这个问题，我想我找到了一个有效的解决方案。

\n\n

首先让我们看一下情况的图像

\n\n

\n\n

所以我们有一个椭圆（实际上是一个圆）和两个点 ( C, D) 表示我们的扇区。\n我们还有圆的中心 ( B) 和圆弧的角度alpha。

\n\n

现在，在这种情况下，我让它通过360\xc2\xba鼠海豚，看看它是否有效。

\n\n

比方说alpha -> -251.1\xc2\xba（它是负数，因为它是顺时针方向），现在让我们将其转换为正值，360\xc2\xba - 251.1\xc2\xba = 108.9\xc2\xba我们的目标是找到该角度的平分角，这样我们就可以找到边界框的最大点（E在图像中），实际上，正如您可能已经意识到的那样，线段的长度BE等于圆的半径，但我们必须有角度才能获得该E点的实际坐标。

\n\n

现在108.9\xc2\xba / 2 -> 54.45\xc2\xba我们有了角度。

\n\n

为了找到 E 的坐标，我们使用极坐标，所以

\n\n

x = r * Cos(theta)\ny = r * Sin(theta)\n

\n\n

我们有r，theta所以我们可以计算 x 和 y

\n\n

在我的示例中r = 2.82\xe2\x80\xa6 （实际上它是无理数的，但我为了方便起见取了前两位小数）

\n\n

我们知道我们的第一个半径是87.1\xc2\xbaθ 是87.1 - 54.45\xc2\xba -> 32.65\xc2\xba

\n\n

我们知道 *theta *32.65\xc2\xba所以让我们做一些数学计算

\n\n

x = 2.82 * Cos(32.65\xc2\xba) -> 2.37552\ny = 2.82 * Sin(32.65\xc2\xba) -> 1.52213\n

\n\n

现在我们需要将这些值调整到圆的实际中心，以便

\n\n

x = x + centerX\ny = y + centerY \n

\n\n

在示例中，圆的中心位于(1.86, 4.24)

\n\n

x -> 4.23552\ny -> 5.76213\n

\n\n

在这个阶段我们应该使用一些微积分。我们知道边界框的一条边将是穿过我们刚刚计算的点的弧的切线，因此让我们找到该切线（红线）。

\n\n

我们知道切线穿过我们的点，(4.23, 5.76)现在我们需要一个斜率。

\n\n

正如您所看到的，斜率与穿过半径的矩形的斜率相同，因此我们必须找到该斜率。

\n\n

为此，我们需要获取半径的坐标（从极坐标快速转换为笛卡尔坐标）。

\n\n

x = r * Cos(theta)\ny = r * Sin(theta)\n

\n\n

所以

\n\n

p0 = (centerX + 2.82 * Cos(87.1\xc2\xba), centerY + 2.82 * Sin(87.1\xc2\xba))\np1 = (centerX + 2.82 * Cos(-21.8\xc2\xba), centerY + 2.82 * Sin(-21.8\xc2\xba))\n

\n\n

（21.8\xc2\xba是从水平轴到其下方的半径顺时针测量的角度，因此我将其设为负值）

\n\n

p0 (2, 7.06)\np1 (4.48, 3.19)\n

\n\n

现在让我们找到斜率：

\n\n

m = (y - y0) / (x - x0)\n...\nm = (3.19 - 7.06) / (4.48-2) = -3.87 / 2.48 = -1.56048\n...\nm = -1.56 \n

\n\n

有了斜率，我们需要计算切线方程，基本上是一个具有已知斜率 ( m = -1.56) 的矩形，它穿过已知点 ( E -> (4.23, 5.76))

\n\n

所以我们有Y = mx + b哪里m = -1.56，y = 5.76所以x = 4.23一定b是

\n\n

b = 5.76 - (-1.56) * 4.23 = 12.36\n

\n\n

现在我们有了切线的完整方程 -> Y = -1.56X + 12.36\n我们必须知道的就是将点投影C到D该矩形上。

\n\n

我们需要矩形的方程CH，DI所以让我们计算它们

\n\n

让我们从以下开始CH：

\n\n

我们知道（从切线方程）我们的方向向量是(1.56, 1)

\n\n

我们需要找到一个穿过该点的矩形C -> (2, 7.06)

\n\n

(x - 2) / 1.56 = (y - 7.06) / 1\n

\n\n

做一些代数 ->y = 0.64x + 5.78

\n\n

我们知道有矩形的方程，CH我们必须计算点H。

\n\n

我们必须按如下方式求解线性系统

\n\n

y = -1.56x + 12.36\ny = 1.56x + 5.78\n

\n\n

解决这个问题我们就会找到重点H (3, 7.69)

\n\n

我们需要对矩形做同样的事情，DI所以让我们这样做

\n\n

我们的方向向量(1.56, 1)又是

\n\n

D -> (4.48, 3.19)\n\n(x - 4.48) / 1.56 = (y -3.19) / 1\n

\n\n

做一些代数 ->y = 0.64x + 0.32

\n\n

让我们来求解线性系统

\n\n

y = -1.56x + 12.36\ny = 0.64x + 0.32\n\nI (5.47, 3.82)\n

\n\n

在这个阶段，我们已经有了构成边界框的四个点 ->C, H, D , I

\n\n

以防万一您不知道或不记得如何用编程语言求解线性系统，我会给您一个小例子

\n\n

这是纯代数

\n\n

假设我们有以下系统

\n\n

Ax + By = C\nDx + Ey = F\n

\n\n

然后

\n\n

Dx = F - Ey\nx = (F - Ey) / D\nx = F/D - (E/D)y\n

\n\n

代入另一个方程

\n\n

A(F/D - (E/D)y) + By = C\nAF/D - (AE/D)y + By = C\n(AE/D)y + By = C - AF/D\ny(-AE/D + B) = C - AF/D\ny = (C - AF/D) / (-AE/D + B)\n  = ( (CD - AF) / D ) / ( (-AE + BD) / D) )\n

\n\n

所以

\n\n

y = (CD - AF) / (BD - AE)\n

\n\n

因为x我们也做同样的事

\n\n

Dx = F - Ey\nDx - F = -Ey\nEy = F - Dx\ny = F/E - (D/E)x\n

\n\n

代入另一个方程

\n\n

Ax + B(F/E - (D/E)x) = C\nAx + (BF/E - (DB/E)x) = C\nAx - (DB/E)x = C - BF/E\nx (A-(DB/E)) = C - BF/E\nx = (C - BF/E)/(A-(DB/E))\n  = ((CE - BF) / E) / ((AE-DB) / E)\n\nx = (CE - BF) / (AE - DB)\n

\n\n

我对我的回答的范围表示歉意，但我的意思是尽可能清楚，因此，我几乎一步一步地做到了。

\n