我正在寻找与几何算法相关的优质资源； 像两条线相交这样的简单问题很容易（也很容易找到），但我想找到一些更复杂的算法，比如找到通过将给定的多边形扩展一定量所形成的形状；高效处理具有曲边形状的图形等。 有什么好的建议吗？谢谢！

给定一组点 S (x, y, z)，如何找到这些点的 凸包(convex hull) ? 我试图理解来自这里的算法，但没有得到太多信息。 它说： 首先将所有点投影到xy平面上，并通过选择具有最高y坐标的点并执行一次礼品包装(gift wrapping)来确定边缘上的另一个端点，从而找出肯...

什么是覆盖所有n个点所需的最小半径为r的圆圈数？ 输入将给出r和n，接着是n对表示n个点的x-y坐标的整数。 r是大于0的实数，n小于20。 如果一个点在圆内，则该圆覆盖了该点。 如果点与圆心之间的距离小于或等于r，则该点位于圆内。

给定一个凸多边形和一个数字N，如何找到最小的多边形，以满足以下条件： 包含原始多边形中的每个点 恰好有N个角点 例如，假设我有一组点并为它们计算凸包（绿色）。现在我想找到包含所有点的最小四边形（红色）。 很容易看出，任何其他有四个角的多边形要么更大，要么无法包含所有点。但在一般...

如何计算三角形（由三个（X，Y）对指定）和圆形（X，Y，R）之间的交集面积？我已经搜索了一些但没有结果。这是为工作而非学校。:) 在C#中，它看起来会像这样： struct { PointF vert[3]; } Triangle; struct { PointF center; floa...

最近在面试中被问到了这个问题。尽管我能想出O(n²)的解决方案，但面试官却迷恋于一个O(n)的解决方案。我也查看了一些O(n logn)的其他解决方案，虽然我理解了，但假设按开始时间排序的O(n)解决方案仍不是我的强项。 有人能解释一下吗？ 问题陈述：您有n个约会。每个约会都包含一个开始时...

一道经典的二维算法问题通常描述为： 给定 n 个非负整数，表示一个高程地图，每个条形的宽度为 1，计算在下雨之后能够捕获多少水。 例如，给定输入：[0,1,0,2,1,0,1,3,2,1,2,1] 返回值将是6 我用于解决上述二维问题的算法是int trapWaterVolume2D(...

一种检测直线与凸多边形是否相交的O(n)算法是检查多边形的任一边是否与直线相交，并查看相交点数是奇数还是偶数。 是否存在渐进更快的算法，例如O(log n)的算法？

给定一个平面上的点集 U，其中有 n 个点，您可以在常数时间内计算任意两点之间的距离。选出 U 的一个子集 C，使得 C 恰好包含 k 个点，并且 C 中最远的两点之间的距离对于给定的 k 最小。1 < k ≤ n 除了明显的 n-choose-k 解决方案，有什么更快的方法吗？

我有大约16,000个75维数据点，对于每个点，我想找到它的k个最近邻居（使用欧几里得距离，目前k=2以使问题简化）。 我的第一个想法是使用kd树实现，但是随着维数增长，它们变得相当低效。在我的示例实现中，它只比穷举搜索略快一些。 我的下一个想法是使用PCA（主成分分析）来减少维数，但我想...