以下是从careercup.com的Google面试部分提出的一个问题： 在二维空间中给定2n + 3个点，没有三个点共线也没有四个点位于一个圆上，设计一个算法，找到包含n个点内部，n个点外部和3个点在其上的圆。 我可以想到一个O(n^4)的解决方案： a）选择任意三个点[以C（2n+3,...

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

我已经成功实现了Marching Cubes算法。 我使用标准材料作为参考，但完全从头开始重新编写了它。它能够工作，但我发现其中存在的模糊性会导致网格中出现洞。 我正在考虑使用Marching Tetrahedrons算法，据说这种方法不会存在模糊性。但是我看不懂这怎么可能。 Marchi...

假设我有一组非重叠的整数坐标矩形，它们一旦固定就不再改变。我有另一个带有整数坐标的矩形 A，其坐标正在移动（但您可以假设其大小是恒定的）。最有效的方法是什么，以找到哪些矩形与 A 相交（或在其中）？由于我的集合太大，我不能简单地遍历它们。谢谢。 编辑：所有矩形都平行于坐标轴。

我面临以下问题： 给定： - 在欧几里得平面上一组点集，每个点P(x,y,w)都有坐标和一个相关的正权重。 - 一组 U 个正方形，它们都有相同的边长L。 目标： - 分配（找到位置），使得所有正方形内包含的点的总权重最大化。 注意： - 正方形应该是轴对齐的。 - 正方形可以重叠，但被...

我需要编写一个程序来找到给定的2D点列表中的所有凸四边形。 我已经尝试使用向量叉积，但似乎不是正确的解决方案。 也许有一些有效的算法可以解决这个问题，但我找不到它。 以下是输入和输出的示例： 输入 点的数量： 6 点的坐标(x,y)： 0 0 0 1 1 0 1 1 2 0 2 ...

我希望能够得到类似于C++中CGAL的东西——我想要对多边形进行凸分割或至少三角剖分。同时，它也必须是免费的。之前的一个问题建议使用JTS，但它似乎没有这些功能。

我被这个小问题卡住了，我的解决算法对于所有情况都不适用。有人有什么想法如何解决吗？ 这里是一个多边形的示例： 示例 http://img148.imageshack.us/img148/8804/poly.png 形式化描述： 我们有一个由顺时针方向定义的点列表来定义此多边形。我们还可...

截至2014年初，SVG规范没有任何内置的布尔运算支持。 布尔运算是改变大多重叠路径固有几何形状的方法。它们通过对简单形状执行操作，允许构建复杂形状，与构造性实体几何(CSG)有些相似。 然而，此问题涉及2D矢量路径。 流行的路径操作包括：联合、减法、交集、异或(Exclusive Or)...

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