文件名称：Farthest-Points-in-a-Set:生成一组点，并使用旋转卡尺和凸包算法找到彼此之间最远距离的一对点
文件大小：31KB
文件格式：ZIP
更新时间：2024-06-06 04:52:12
Java
一组中最远的点 目的是确定两点之间的距离最远。 解决该问题的一种明显但效率不高的方法是扫描每个点并计算其与集合中每个其他点的距离。 这将以O（n ^ 2）的效率运行。 解决该问题的一种更有效的方法是形成一个凸包，并使用一种算法分析该包以找到最远的两个点。 凸包是形成多边形的点集，该多边形包含集合中的所有点，而仅形成外部反射角。 下图显示了一组点的凸包，其中红点在凸包集中，白线形成多边形： 凸包很有用，因为最远的两个点始终在凸包集中。 与旋转卡尺结合使用时，此方法效率更高，因为与蛮力方法相比，查找最远的对所需的迭代次数更少。 这是因为礼品包装方法的效率为O（nh），其中n是集合中的点数，h是凸包中的点数。 然后，当在凸包中搜索最远的对时，蛮力算法是O（h）而不是O（n）。 此外，使用旋转卡尺时，凸包方法更为有效。
【文件预览】：
Farthest-Points-in-a-Set-master
----LICENSE(18KB)
----src()
--------com()
----.idea()
--------uiDesigner.xml(9KB)
--------scopes()
--------misc.xml(514B)
--------vcs.xml(164B)
--------description.html(97B)
--------copyright()
--------modules.xml(266B)
--------encodings.xml(164B)
--------compiler.xml(739B)
--------workspace.xml(36KB)
--------project-template.xml(89B)
----FarthestPoint.iml(425B)
----out()
--------production()
----README.md(1KB)