检查三个圆是否适合一个三角形
我花了一些时间考虑编写一个程序，告诉我三个给定直径的圆是否可以放入一个给定边长的三角形内，而不会彼此重叠（接触是可以的）。
人们会如何考虑这样做？
I have thought some time about writing a program that tells me if three circles with given diameters can fit inside a triangle with given side lengths without overlapping (touching is ok) each other.
How would one think about doing that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我会尝试找到某种方法来枚举三个圆圈的可能配置，然后测试每个配置，直到找到三个圆圈适合的配置，或者直到所有配置都经过测试并被拒绝。
（在下文中，我假设已知每个圆都可以自行适合三角形。显然，如果任何圆无法自行适合，那么它就无法适合三个圆的任何配置。）
配置（1）涉及放置一个圆在三角形的每个角上。 （这是每个人都发现的配置。）
有六种排列圆圈的方法，对于每种排列，足以检查圆圈是否成对匹配：
距离 AS1 为 r1/tan(½α)，距离 S2B 为 r2/tan(1/2β)，距离 S1S2 为 √((r1+r2)2 − (r₁− r2)2) = 2√r₁r2
如果 AS₁+ S₁S2+ S2B ≤ AB，则圆拟合。
在配置（2）中，我们将两个圆放置在三角形的两个角上，并将第三个圆放置在这两个圆之间以及不接触两个圆的两个边之一：
弄清楚这些是否适合有点复杂：
要找到长度 AS₁，我们必须从角 C 经点 T 绕三角形走一圈。我将把这个细节保留为锻炼。
有十八种方法可以将圆排列成这种配置。
有配置（3）吗？我看了看，但找不到一个不能变成我给的两个之一的。例如，如果所有三个圆圈都接触同一侧，则始终有空间将中间的圆圈交换到另一侧，从而获得配置 (2)。然而，几何构型的枚举总是很棘手，我很容易就会错过其中一个。
I would try to find some way to enumerate the possible configurations for the three circles, and then test each configuration until one is found where the three circles fit, or until all configurations have been tested and rejected.
(In what follows I am assuming that each circle is known to fit in the triangle by itself. Obviously if any circle fails to fit by itself then it fails to fit in any configuration of three circles.)
Configuration (1) involves putting a circle in each corner of the triangle. (This is the configuration that everyone spotted.)
There are six ways to arrange the circles, and for each arrangement it sufficient to check whether the circles will fit pairwise:
The distance AS₁ is r₁/tan(½α), the distance S₂B is r₂/tan(½β), and the distance S₁S₂ is √((r₁ + r₂)² − (r₁ − r₂)²) = 2√r₁r₂
The circles fit if AS₁ + S₁S₂ + S₂B ≤ AB.
In configuration (2) we place two circles into two of the corners of the triangle, and the third circle between these two and one of the two edges that's not touching both circles:
Figuring out whether these will fit is a bit more complex:
To find the length AS₁ we have to walk round the triangle from corner C via the point T. I'll leave the details of this as an exercise.
There are eighteen ways to arrange the circles into this configuration.
Is there a configuration (3)? I looked but couldn't find one that couldn't be turned into one of the two I gave. For example, if all three circles touch the same side then there's always room to swap the middle circle over to the opposite side, getting configuration (2). However, enumeration of geometric configurations is always tricky and I could easily have missed one.
只是猜测：您的问题可能与阿波罗尼乌斯圈子的问题有关。
我在尝试在第四个圆中递归地拟合 3 个圆时遇到了这个问题，对于一些分形动画没有任何交集，所以它可能值得一试。
您会发现 Wolfram 对其进行了详细解释（这个问题直到 1968 年才得到解决）：
http://mathworld.wolfram.com/ApolloniusProblem.html
Just a guess: your problem could be related to that of Appolonius's circles.
I ran into it while trying to fit recursively 3 circles within a 4th one without any intersection for some fractal animation, so it may be worth a try.
You'll find it explained in length at Wolfram (this problem was solved only in 1968):
http://mathworld.wolfram.com/ApolloniusProblem.html
这似乎是一个棘手而有趣的问题。通过Los和Zalgaller在1994年解决Marble Problem（与Malfatti's Circles相关），您可能会繁琐地提取一个存在于具有指定边长的三角形内具有给定半径的三个不重叠圆的配置的必要条件。如果可以将它们放在三角形内，则它们的面积之和最多将是圆内三个三角形的最大可能面积。大理石问题是确定给定三角形内三个不重叠圆的最大面积的问题。目前，我认为这也足够。
也许值得一开始，在问题中引入一个 ε，然后寻找一种算法，在有限数量的步骤中，可以确定一个配置是否至多“由 ε 决定”（在一些合理的定义中定义）方式）存在。
一些世界顶级数学家定期参加 stackoverflow 的兄弟网站，
mathoverflow.org，所以你可以尝试在那里发布这个问题。
感谢您发布此内容。
this seems to be a tough and interesting problem. Through the solution of the Marble Problem (related to Malfatti's Circles) by Los and Zalgaller in 1994, it might be possible for you to tediously extract a necessary condition for existence of a configuration of three non-overlapping circles with given radii inside a triangle with prescribed side lengths. If you can place them inside the triangle, the sum of their areas will be at most the maximal possible area for three triangles inside a circle. The Marble Problem is the problem of determining the maximal area of three non-overlapping circles inside a given triangle. Right now, I can't see that this is also sufficient.
Perhaps it would be worth, as a start, to introduce an ε to the problem and then look for an algortihm that in a finite number of steps, could determine if a configuration which is at most "bad by ε" (defined in some sensible way) exists.
Some of the World's top mathematicians participate regularly at stackoverflow's sibling,
mathoverflow.org, so you could try posting this problem over there.
Thanks for posting this.
我认为尝试所有 6 种可能的排列（A1 B2 C3、A2 B1 C3、A1 B3 C2、A3 B1 C2、A2 B3 C1、A3 B2 C1）就足够了。如果一个圆与三角形的两条边不相切，那么它的放置在某种意义上不是最佳的，您可以通过将其滑入角落来为另外两个圆腾出更多空间。如果可以将三个圆圈粘成三角形而不重叠，那么就可以将它们滑入角落（对于它们全部卡在边缘的情况，将它们全部抬起并旋转 60 度）。当然，这不是一个严格的证明，但我很确定它是有效的。
此外，我认为解决方案始终是将最大的圆放置在最宽的角度，因为这些圆可能会占据最中心的三角形空间。
I think it's sufficient to try all 6 possible permutations (A1 B2 C3, A2 B1 C3, A1 B3 C2, A3 B1 C2, A2 B3 C1, A3 B2 C1). If a circle isn't tangent to two edges of the triangle, then it's placement is suboptimal in some sense and you could make more space for the other two by sliding it into a corner. If it's possible to stick three circles in a triangle without them overlapping then it's probably possible to slide them into the corners (for the case in which they're all jammed against the edges, lift them all up together and rotate by 60 degrees). Of course, this isn't a rigorous proof, but I'm pretty sure it works.
Furthermore, I imagine the solution will always be to place the largest circles at the widest angles, because those are the ones that could potentially take up the most central triangle space.