我正在尝试找到一种高效的解决方案，用于查找 n 个矩形的重叠区域，其中矩形存储在两个不同的列表中。我们要查找listA中与listB中矩形重叠的所有矩形（反之亦然）。将第一个列表中的一个元素与第二个列表中的一个元素进行比较可能需要极长的时间。我正在寻找一种高效的解决方案。 我有两个矩形列表 ...

我一直在使用Qhull（R中的geometry包）和MatLab中的某些函数，将局部笛卡尔X、Y、Z点投影到以0,0,0为中心的球坐标系（theta，phi，R）。由于所有Z值在原始坐标系中都是正值（X和Y则是以0为中心），因此这给了我所需的半球形投影（点颜色按Z值缩放），使用R plotri...

我想在在线编程比赛中解决几何问题。但是每当我阅读它们时，我发现它们太难了。请推荐一些可以学习计算几何的书籍和资源。

我正在处理地理信息，最近需要画一个椭圆形。为了符合OGC的标准，我不能直接使用椭圆，而是使用多边形来近似表示椭圆，通过选择一个被椭圆包含的多边形并使用任意多的点。 生成给定点数N的椭圆的过程如下（使用C#和一个虚构的Polygon类）：Polygon CreateEllipsePolygon...

我希望计算两条折线段之间的距离d: 显然，我可以检查所有线段对的距离并选择最小距离，但这种方法的算法时间复杂度为O(n2)。有更好的方法吗？

我有一些点（例如，基站位置的lat、lon对），需要获取它们所形成的 Voronoi cell 的多边形。from scipy.spatial import Voronoi tower = [[ 24.686 , 46.7081], [ 24.686 , 46.7081],...

我有一个由N个点组成的凸多边形P1。这个多边形可以是任何形状或比例（只要它仍然是凸的）。 我需要使用原始多边形的几何形状计算另一个多边形P2，但需要将其“扩展”给定数量的单位。如何扩展凸多边形的算法是什么？

对于由一系列(x,y)点定义的多边形，如何检测它是否为复杂多边形？复杂多边形与自身相交，如下所示： 有没有比O(N^2)更好的解决方案来检查每对多边形点?

给定平面上的n个点，没有三个共线。 给定数字k。 找到k个点的子集，使得这k个点组成的凸包周长最小，且这个凸包的周长比其他k个点的子集所组成的凸包的周长都要小。 我能想到一种朴素的方法，其时间复杂度为O(n^k k log k)。（对于每个大小为k的子集寻找凸包并输出最小值）。 我认为...

我有一些二维封闭矢量路径，用SVG路径语法指定 - 即这些路径包括直线和各种贝塞尔曲线。是否有类似的小型、简单且离散的库（最好是C、Java或Ruby，但如果该库干净易用，任何语言都可以）可用于执行与这些路径的布尔运算，如并集、交集和差集？ 目前我找到的内容包括： 巨大而昂贵的商业矢量图...