球面上（经度，纬度）点的凸包
标准的凸包算法无法用于经纬度坐标点，因为标准算法假定您要计算笛卡尔坐标点集的凸包。经纬度点不是笛卡尔坐标系，因为经度在反子午线（+/- 180度）处“环绕”。也就是说，比经度179东两度的是-179。 因此，如果您的点集恰好跨越了反子午线，您将计算出伸展到错误位置的虚假凸包。 有没有什么技...
什么是寻找穿过大多数点的直线最有效的算法？
问题: 在二维平面上给定N个点，同一条直线上最多有多少个点？ 该问题有一个O(N2)的解决方案：遍历每个点，并找到与当前点具有相同dx / dy关系的点数。为了提高效率，可以将dx / dy关系存储在哈希映射中。 是否有比O（N2）更好的解决方案？
多边形内部嵌套多边形问题
我有一些简单多边形，它们之间不相交，但某些多边形可能嵌套在其他多边形中。 例如：+--------------------------------------------+ | | | +-------...
在对数时间内测试点相对于凸包的位置
我有一个2D点集合，需要测试输入点是否在的凸包内。由于这是一个二进制决策问题，理论上可以使用决策树实现O(log(N))。然而，我不知道如何组织数据和算法的实际实现，以便在O(log(N))内得到答案。在研究此想法时，我发现了以下内容： 我们如何更快地找到这两种情况呢？二分查找。只需在两个链...
在给定 n 个点 (x,y) 的情况下，是否可以在 O(n logn) 时间内找到负斜率对数？
给定一个平面上的一组n个点，表示为(x,y)，目标是找到所有点(xi,yi)和(xj, yj)的配对数量，使得连接两个点的直线具有负斜率。 假设没有两个xi的值相同。假设所有点都在[-100,100]或其他某个范围内。
本特利-奥特曼算法实现
有没有现成的Bentley-Ottmann算法实现/库在C#或Java中？
如何确定是否可以在一组点周围画一个圆，使得来自另一组点的点不在圆内？
我想了解一个算法，它能够返回true或false，告诉我是否可以在一组点A周围画一个圆，使得来自点集合B的任何点都不在其中，或者反过来（是否可以在一组点B周围画一个圆，使得来自点集合A的任何点都不在其中）。 基本上，输入两个点集，需要确定是否可能绘制一个圆形覆盖其中一个点集，以便其他点集中的...
用半径为r的圆覆盖n个点，最少需要多少个圆？
什么是覆盖所有n个点所需的最小半径为r的圆圈数？ 输入将给出r和n，接着是n对表示n个点的x-y坐标的整数。 r是大于0的实数，n小于20。 如果一个点在圆内，则该圆覆盖了该点。 如果点与圆心之间的距离小于或等于r，则该点位于圆内。
从边的列表中生成多边形
在一张由边缘Map<Point, List<Edge>>组成的地图中，给定N个点，能否在O(N log N)时间内得到这些边所形成的多边形？我知道你必须遍历所有的顶点，并获取包含该顶点为起始点的边缘。这些是Voronoi图的边缘，每个顶点最多有3个与之相邻的顶点。因此，...
计算圆和三角形之间的交集面积？
如何计算三角形（由三个（X，Y）对指定）和圆形（X，Y，R）之间的交集面积？我已经搜索了一些但没有结果。这是为工作而非学校。:) 在C#中，它看起来会像这样： struct { PointF vert[3]; } Triangle; struct { PointF center; floa...