算法 - 找到最大周长的三角形

Question

我在2D平面中给出一组N个点，表示为（x，y）坐标对。什么是选择三个点的快速算法，以便这些点形成的三角形具有最大周长？

Answer 1

这是先发制人的

• 选择距离鸡群最远的一点，我们称之为A点。
• 绘制一条假想的直线，切入A到羊群的其余部分。
• 选择另一个相反的点，它的偏差（从假想的直线）是从最高到右。
• 选择另一个相反的点，即偏离（从假想的直线）最高的左边。

检查是否可以制作三角形？如果没有检查另一个轴的另一个最高点

Answer 2

这是一个粗略的想法（我不太熟悉计算几何）。具有固定周长和基部的三角形可以生成椭圆。例如，这里B和C是固定的，椭圆上的任何点A都会保持三角形边界相同：

对于连接两个点的每个段，在我们的集合中选择一个随机的第三个点。生成相关的椭圆，然后从我们的椭圆外部的集合中选择另一个随机点。每个椭圆将排除生成相同或更小周长的三角形的点，直到我们找到最大的点为止。当然，我们需要一些有效的方法来找到相关点（可能使用空间分区？）。