我有一个实体的三维固体，它由一组多面体凸壳的联合表示（如果这样做更容易，则为单个凸壳）。我想以一种方式将该实体近似为一组球的联合，以使球集中的球数和逼近误差都最小化。 （后一个目标故意模糊：任何合理的误差度量都可以。同样，如何结合这些目标尚未确定；可以约束球的数量或误差度量，或者可以最小化两者...

这是2010年太平洋ACM-ICPC比赛中出现的问题。其重点是尝试找到一种方法，将三角形内一组点分成三个子三角形，使得每个分区恰好包含三分之一的点。 输入： 一个边框三角形的坐标：(v1x,v1y),(v2x,v2y),(v3x,v3y) 一个数字3n < 30000，代表位于三角...

在工业中，通常存在这样一个问题：您需要计算材料的最有效利用方式，无论是织物、木材、金属等。因此，起点是由多边形和/或曲线制成的给定尺寸的X个形状，并且目标是另一个给定尺寸的多边形。 我假设许多当前的CAM套件都实现了这一功能，但是我没有使用它们或了解它们的内部结构，那么用于找到空间最有效利用...

我正在解决教授布置的问题，但我遇到了一个问题，就是寻找一种方法来检测三个点之间的角度是否超过180度，例如： 我想检测 alpha 是否大于 180 度。任何情况下，我的教授有一段解决该问题的代码，但他有一个名为 zcross 的函数，但我不知道它是如何工作的。有人能告诉我吗？他的代码在...

我最近被一家GIS公司聘请来重写他们的旧地理信息库。因此，我现在正在寻找一个好的计算几何库。我看过了CGAL，它非常棒，但是我的老板想要一个免费的。 所以我现在正在查阅Boost.Geometry。这个库似乎很不错，但它也似乎在快速变化。许多东西尚未实现，而且邮件列表上有很多问题正在讨论。...

我想要找到图中最近的边。考虑以下示例： 图1： 黄色：顶点，黑色：边，蓝色：查询点 基本信息： 该图包含约 1000万个顶点 和约 1500万条边。每个顶点都有坐标，而边是由相邻的两个顶点定义的。 简单解决方案： 我可以简单地计算查询点与图中每条其他边的距离，但这会非常慢。 思路和困...

我有一组二维点，它们是标准笛卡尔坐标系（在本例中为UTM区域）上的X、Y坐标。我需要找到这些点集中的孔，最好能够设置发现这些孔的算法的灵敏度。通常，这些点集非常密集，但有些可能不那么密集。 如果有帮助的话，它们是田地中取样的土壤的点，人们显然认为这些属性很有用。有时，在这些点样本中会有巨大的...

我正在寻找一个在二维空间中计算 alpha shape 的实现方法。我使用的操作系统是 Ubuntu。我希望能够用命令行工具来完成这个任务，但也可以接受使用 Python 库。 在 Google 上，我找到了许多计算 alpha shape 的实现方法。但是它们都没有输出我想要的结果。我有一...

免责声明：是的，这是一项作业，我已经思考了几天但是找不到解决方案。 有n条直线（y = ax + b），我想要找到它们的上凸壳（图片中加粗部分）。时间复杂度必须为O(nlogn)。 我理解的是，我需要找到一种方法来忽略一些直线，因为如果搜索所有的直线，时间复杂度就不会是O(nlogn)。 ...

我希望找到两个拥有数百万个顶点的多边形之间的最小距离（而不是它们各自顶点之间的最小距离），需要计算第一个形状的每个顶点与另一个形状的所有顶点之间的最短距离，并找出这些距离中的最小值。类似于Hausdorff距离，但我需要最小值而不是最大值。