一组点中最大的三角形 [英] Largest triangle from a set of points

问题描述

可能重复:
如何在除蛮力搜索外的凸包

我有一组随机点，我想从这些随机点中找到面积最大的三角形，每个顶点的顶点都在这些点中的一个上.

I have a set of random points from which i want to find the largest triangle by area who's verticies are each on one of those points.

到目前为止，我已经知道最大的三角形的顶点将仅位于点云(或凸包)的外部点上，因此我编写了一个函数来做到这一点(在nlogn时间内使用Graham扫描)

So far I have figured out that the largest triangle's verticies will only lie on the outside points of the cloud of points (or the convex hull) so i have programmed a function to do just that (using Graham scan in nlogn time).

但是，这就是我被困住的地方.我可以弄清楚如何从这些点中找到最大的三角形的唯一方法是在n ^ 3时使用蛮力，这在一般情况下仍然可以接受，因为凸包算法通常会剔除绝大多数点.但是，在最坏的情况下，如果点在圆上，这种方法将惨遭失败.

However that's where I'm stuck. The only way I can figure out how to find the largest triangle from these points is to use brute force at n^3 time which is still acceptable in an average case as the convex hull algorithm usually kicks out the vast majority of points. However in a worst case scenario where points are on a circle, this method would fail miserably.

有人知道算法可以更有效地做到这一点吗?

Dose anyone know an algorithm to do this more efficiently?

注意:我知道CGAL在那里有此算法，但是他们没有详细介绍它是如何完成的.我不想使用库，我想学习它并自己编程(也可以让我根据我希望它的操作方式对其进行调整，就像graham扫描中其他实现在其中获取共线点一样)我不要).

Note: I know that CGAL has this algorithm there but they do not go into any details on how its done. I don't want to use libraries, i want to learn this and program it myself (and also allow me to tweak it to exactly the way i want it to operate, just like the graham scan in which other implementations pick up collinear points that i don't want).

推荐答案

不知道这是否有帮助，但是如果您从凸包中选择两个点并旋转壳的所有点，以便两者的连接线点平行于x轴，y坐标最大的点或y坐标最小的点与先选择的两个点一起形成面积最大的三角形.

Don't know if this help, but if you choose two points from the convex hull and rotate all points of the hull so that the connecting line of the two points is parallel to the x-Axis, either the point with the maximum or the one with the minimum y-coordinate forms the triangle with the largest area together with the two points chosen first.

当然，一旦为所有可能的基准线测试了一个点，就可以将其从列表中删除.

Of course once you have tested one point for all possible base lines, you can remove it from the list.

这篇关于一组点中最大的三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！