algorithm - 找到多边形最小边数的算法

Question

如何设计一种算法来找到位于两个同心圆之间的多边形的最小边数？

与此类似：

Answer 1

首先考虑最简单的情况：内圈在显微镜下很小。只要内圆的半径不为零，最小边数为 3。

多边形什么时候开始需要 4 条边？画一个与圆内接的等边三角形。当内圆的半径到达三角形边的中心点时，多边形开始需要 4 条边。

如果将一个 N 边的正多边形内接在外圆中，则可以使用余弦规则计算从每条边的中点到圆心的距离：

distance_to_midpoint = cos ( 360 / (N * 2) ) * radius_of_outer_circle

（说明：如果你用圆的中心点到有问题的一边做一个等腰三角形，半径的角度为 360 / N。在边的中点将三角形分成两半，形成一个带斜边的直角三角形等于外圆的半径，然后使用余弦规则）

现在distance_to_midpoint需要大于或等于内圆的半径，所以求解N：

radius_of_inner_circle = cos(360 / (N * 2)) * radius_of_outer_circle
cos(360 / (N*2)) = radius_of_inner_circle / radius_of_outer_circle
360 / (N*2) = acos(radius_i / radius_o)
N = 180 / (acos(radius_i / radius_o))

（我还没有仔细检查这个数学，真的很晚了）。

Answer 2

用 表示多边形的半径，即多边形外接圆的半径R。内接圆的半径为

r = R*Cos[180°/n]

解决这个问题n，消除给出否定结果的虚假解决方案，你有

n = 180°/ArcCos[r/R]

你必须摆弄一下才能得到 的整数值n，我把它留给你。

Answer 3

1. 绘制内圆的切线，标记 A，B - 切线与外圆的交点。
2. 从 B 点画一条内圆的切线（不同），标记与外圆 C 的交点。
3. 重复过程 (2) 直到新切线穿过第一个切线 AB。

该算法将确保您在每一步都覆盖最大径向截面，从而最大限度地减少生成的多边形中的边数。

如果您只想找到边数，只需找到从外圆上的同一点到内圆的 2 个切线之间的角度，并计算有多少个这样的角度构成完整的 360 度（如果有，则加 1其余） - 就像评论中建议的@cheeken