圆和三角形问题
我有一个有趣的问题，我在过去的一段时间里一直在努力解决：
我在2D xy平面上有3个圆，每个圆都具有相同的已知半径。我知道三个中心的坐标(它们是任意的，可以在任何地方)。
可以画的最大的三角形是什么，使得三角形的每个顶点都位于一个单独的圆上，这些顶点的坐标是什么？
我已经研究这个问题好几个小时了，问了很多人，但到目前为止，只有一个人能提出一个合理的解决方案(尽管我没有办法证明这一点)。
我们提出的解决方案包括首先创建一个围绕三个圆心的三角形。接下来，我们分别查看每个圆，并计算通过该圆的中心并垂直于相对边的直线的方程。然后我们计算圆的两个交点。然后，对接下来的两个圆执行此操作，结果为6点。我们迭代这6个点创建的8个可能的3点三角形(限制是大三角形的每个点必须在一个单独的圆上)，并找到最大尺寸。
结果看起来是合理的(至少当绘制在纸上时是这样)，并且它通过了当圆的中心都落在一条直线上的特殊情况(给出了一个已知的最大三角形)。不幸的是，我无法证明这是正确的还是错误的。
我想知道是否有人遇到过类似的问题，如果有，你是如何解决的？
注意:我理解这主要是一个数学问题，而不是编程，但它将在代码中实现，它必须进行优化，以非常快和有效的运行。事实上，我已经有了上面的解决方案的代码，并且测试是有效的，如果你想看一看，请让我知道，我选择不张贴它，因为它都是矢量形式的，几乎不可能弄清楚到底发生了什么(因为它已经被压缩以提高效率)。
最后，是的，这是为了学校作业，尽管它不是一个家庭作业问题/作业/项目。这是我的毕业论文的一部分(我想这是非常非常小的一部分，但从技术上讲仍然是其中的一部分)。
谢谢你的帮助。
编辑:这是我不久前想出的一个新算法。
从一个圆的中心开始，画一条线到另外两个中心。计算将创建的角度一分为二的直线，并计算圆与通过圆中心的直线之间的交点。您将获得2个结果。对其他两个圆重复此操作，总共得到6个点。迭代这6个点，得到8个可能的解决方案。找到8个解决方案中的最大值。
如果你在围绕这三个点的一个“方向”上画线，这个算法将处理共线的情况。
从我尝试使用CAD软件为我找出几何形状的几次随机试验中，这种方法似乎优于前面提到的所有其他方法，然而，它已经被维克多的一个反例证明不是最佳解决方案。
我将在明天编写代码，由于某些原因，我失去了对我的大学计算机的远程访问，大多数东西都在上面。
回答 6
Stack Overflow用户
发布于 2010-04-08 13:25:53
我已经创建了一个可能对人们有用的HTML5 canvas app。这是非常基本的(代码并不美观)，但它允许你移动三个等半径的圆，然后使用梯度/最陡峭下降来计算一个最大的三角形。您还可以保存图表的位图。该图还显示了顶点为圆中心的三角形，以及其中的一个高度。Edit1：“高度”实际上只是通过其中一个圆心的线段，垂直于连接圆心的三角形的相对边缘。它之所以存在，是因为一些建议的构造使用了它。Edit2：最陡下降法有时会陷入局部最大值。您可以通过移动一个圆，直到黑色三角形翻转，然后将圆带回其原始位置，以达到最大值。研究如何找到全局最大值。
这在IE中是行不通的，因为它不支持canvas，但是大多数其他的“现代”浏览器应该可以工作。
我这样做的部分原因是我发现这个页面上的一些论点是有问题的，部分是因为我从来没有编写过最陡峭的下降程序，并想看看它是如何工作的。无论如何，我希望这对我有所帮助，我希望稍后会有更多的评论。
编辑：我已经看了更多的几何图形，并在separate answer中写下了我的发现。
Stack Overflow用户
发布于 2010-04-08 04:16:32
假设A，B，C是三角形的顶点，并假设它们的位置与解中的位置相同。请注意，构造的关键属性是每个顶点都位于其圆的切线上，该圆平行于三角形的另一侧。显然，圆本身完全位于切线的一侧，并且在最佳解决方案中，每条切线将其圆留在与其他顶点相同的一侧。
假设AB是三角形的“底”，让C在它的圆中浮动。如果你将C移动到圆内的另一个位置C‘，你将获得另一个具有相同底数但高度较小的三角形ABC’，因此也具有较小的面积：
figure 1 http://control.ee.ethz.ch/~ramponif/stuff/circles1.png
出于同样的原因，您可以很容易地看到，任何不遵循您的构造的顶点位置都不是最优的。例如，假设顶点A'，B'，C‘中的每一个都不在与连接其他两个顶点的边平行的切线上。
然后，构造与包含(比方说) C‘的圆的切线，该圆与A'B’平行，并使圆与A'B‘在同一条边，并将C’移动到切点C，始终可以构造一个具有相同底数但更高的三角形A'B'C，因此也有更大的面积：
figure 2 http://control.ee.ethz.ch/~ramponif/stuff/circles2.png
因为任何不遵循你的构造的三角形都不可能是最优的，所以我相信你的构造是最优的。在圆心对齐的情况下，我有点困惑，但我猜可以证明沿着相同的线是最优的。
Stack Overflow用户
发布于 2010-04-07 08:35:40
我相信这是一个凸优化问题(不是，见下文)，因此可以使用众所周知的方法有效地解决。
你实际上想要解决这个问题：
maximize: area(v1,v2,v3) ~ |cross((v2-v1), (v3-v1))|
such that: v1 in C1, v2 in C2, v3 in C3 (i.e., v_i-c_i)^2 - r_i^2 <= 0)每个约束都是凸的，面积函数也是凸的。现在，我不知道是否有更有效的公式，但你至少可以使用带有导数的内点法，因为面积相对于每个顶点位置的导数可以解析地计算出来(我在某个地方写下了它...)。
编辑：grad(v1(v1，v2，v3))(v_i) = rot90(vec(vj，vk))，其中vec(a，b)是从a开始到b结束的2D向量，rot90表示正方向旋转90度，假设(vi，vj，vk)是正方向。
编辑2:问题不是凸的，考虑到共线的情况，这一点应该是显而易见的；两个退化的解是非凸性的确定标志。然而，从圆心开始的配置应该是全局最优的局部最大值。
https://stackoverflow.com/questions/2588943
复制相似问题
腾讯云开发者
