圆和三角形的问题

Question

我有一个有趣的问题,我一直试图解决最后一段时间:

我在2D xy平面上有3个圆圈,每个圆圈具有相同的已知半径.我知道三个中心的坐标(它们是任意的,可以在任何地方).

可以绘制的最大三角形是什么,使得三角形的每个顶点位于一个单独的圆上,这些顶点的坐标是什么？

我一直在看这个问题好几个小时并问了一堆人,但到目前为止只有一个人能够提出一个合理的解决方案(虽然我无法证明这一点).

我们提出的解决方案包括首先创建一个关于三个圆心的三角形.接下来,我们分别查看每个圆,并计算穿过圆的中心并垂直于相对边的线的方程.然后我们计算圆的两个交点.然后对接下来的两个圆进行,结果为6个点.我们迭代这6个点创建的8个可能的3个点三角形(限制是大三角形的每个点必须在一个单独的圆上)并找到最大尺寸.

结果看起来很合理(至少在纸上绘制时),它通过了圆的中心全部落在一条直线上的特殊情况(给出一个已知的最大三角形).不幸的是,我无法证明这是否正确.

我想知道是否有人遇到类似这样的问题,如果有的话,你是怎么解决的？

注意:我知道这主要是一个数学问题,而不是编程,但是它将在代码中实现,并且必须进行优化才能非常快速有效地运行.事实上,我已经在代码中进行了上述解决方案并进行了测试工作,如果您想看看,请让我知道,我选择不发布它因为它全部采用矢量形式而且几乎无法弄清楚到底是怎么回事(因为它被浓缩得更有效率).

最后,是的,这是为了学校的工作,虽然它不是一个家庭作业问题/任务/项目.这是我毕业论文的一部分(非常非常小的部分,但在技术上仍然是其中的一部分).

谢谢你的帮助.

编辑:这是我刚才想出的一种新算法.

从圆圈的中心开始,画一条线到另外两个中心.计算将所创建的角度平分的线,并计算圆与穿过圆心的线之间的交点.你将得到2个结果.对其他两个圆圈重复此操作以获得总共6个点.迭代这6个点,得到8个可能的解决方案.找到8种解决方案中的最大值.

如果您在三个点的一个"方向"上绘制线条,此算法将处理共线情况.

从我尝试使用CAD软件为我计算几何形状的少数随机试验来看,这种方法似乎优于之前所述的所有其他方法.但是,已经证明它不是Victor的反例之一的最佳解决方案.

我明天会对此进行编码,出于某种原因,我已经失去了对大学计算机的远程访问权限,而且大部分内容都在其上.

Answer 1

我创建了一个HTML5画布应用程序,可能对人们有用.这是很基本的(和代码是不漂亮),但它可以让你移动半径相等的三个圆圈,然后使用渐变/最速下降计算的最大的三角形.您还可以保存图表的位图.该图还显示了顶点为圆心的三角形,以及其中一个高度.编辑1:"高度"实际上只是通过其中一个圆心并垂直于连接中心的三角形的相对边缘的线段.它就在那里,因为一些建议的构造使用它. Edit2:最陡的下降方法有时会陷入局部最大值.您可以通过移动圆圈直到黑色三角形翻转然后将圆圈移回其原始位置来超出该最大值.研究如何找到全局最大值.

这在IE中不起作用,因为它不支持画布,但大多数其他"现代"浏览器应该可以工作.

我这样做,部分原因是我发现的一些论点此页面上有问题,部分是因为我从来没有编程的最速下降,想看看如何工作.无论如何,我希望这会有所帮助,我希望稍后再说一些评论.

编辑:我更多地看了几何,并在一个单独的答案中写了我的发现.

Answer 2

我冒昧地提交了第二个答案,因为我的原始答案提到了一个人们可以玩的在线应用程序以获得洞察力.这里的答案更像是一个几何论点.

下面的图表阐述了我希望发生的事情.其中大部分都是受到@Federico Ramponi观察到的启发,即最大三角形的特征在于每个顶点的切线平行于相对侧.

该图片是使用优秀桌面程序Geometry Expressions的试用版生成的.该图显示了在点为中心的三个圆A,E和C.它们具有相等的半径,但图像并不真正取决于半径相等,因此解决方案推广到不同半径的圆.线MN,NO以及OM是相切的圆,并在点触摸的圆圈I,H和G分别.后面的点形成内三角形IHG,这是我们想要最大化的三角形.

还有一个外部三角形MNO,它 与内部三角形相连,意味着它的两侧平行于IHG.

@Federico观察到IHG具有最大面积,因为沿着相应的圆移动其任何顶点将产生具有相同基部但较少高度的三角形,因此具有较小的面积.为了把它略多技术术语,如果三角形是由角参数t1,t2,t3在三圈(由@Charles斯图尔特指出,和我最速下降的画布应用程序使用),那么该地区的WRT梯度(t1,t2,t3)是(0,0,0),并且该区域是极值的(图中最大).

那么这个图是如何计算的？我事先承认我并不完整,但这是一个开始.给定三个圆圈,选择一个点M.将切线绘制到以E和为中心的圆C,并将切点指定为G和I.绘制与OHN中心A平行的圆的切线GI.这些是代数和几何上相当简单的操作.

但我们还没有完成.到目前为止,我们只有OHN与之平行的条件GI.我们无法保证与MGO您平行IH或MIN平行GH.所以我们必须回过头来进行改进M.在交互式几何程序中,设置它然后移动M直到满足后面的平行条件(通过眼球,无论如何)都没有什么大不了的. 几何表达式创建了图表,但我使用了一些作弊来实现它,因为它的约束求解器显然不够强大,无法完成这项工作.对于代数表达式G,I和H是相当简单,所以它应该是可以解决的M基础上,事实MIHG是平行四边形,任何明示或数字.

我应该指出,一般来说,如果你从构造开始M,你有两个切线选择每个圆,因此有八个可能的解决方案.正如在问题的其他尝试答案中一样,除非你有一个好的启发式方法来帮助你提前选择要计算的切线,你应该计算所有八个可能的三角形并找到具有最大面积的三角形.在最小面积或鞍点的意义上,其他七个将是极端的.

而已.这个答案并不完全,因为它使M的最终计算有点开放.但是它被缩减为2D搜索空间或者是一个ornery的解决方案,而不是一个非常大的方程式.

最后,我不同意@ Federico的结论,即这证实了OP提出的解决方案是最优的.确实,如果你从圆心到中心三角形的相对边缘绘制垂线,那些垂线与圆相交给你三角形顶点.例如,它H位于通过A垂直于GI)的线上,但这与原始提出的解决方案(通过线A和垂直线EC- 通常EC不平行GI)不同.