computational-geometry

3热度

2回答

我想找到一个快速算法来找到（近似的，如果需要的话）在二维空间中给定点的最近邻居，其中点经常从数据集和新的点被添加。（与此相关的，也有这个问题的两个变种是引起我的兴趣：一个在哪些点可以被看作是补充和随机取出，另一种所有的点都在不断地运动）一些想法： KD树提供了良好的性能，但只适用于静态的点集 R * - 树似乎提供良好的性能，适用于各种尺寸，但其设计的通用性（任意尺寸，一般内容几何）表明可能性

0热度

3回答

调整地形高度图中的道路

假设我们有一张表示地形高程的高度图，其形式为每个像素指示高度的图像。假设同一图像上的另一图层正被用于指示穿过地形的道路，因此亮像素表示道路上的点，暗像素指示道路偏离，中间像素表示沿着边缘的位置的道路。这似乎是在这种情况下代表道路的一种自然方式，但我们也可以使用行进方块将其转换为道路的多边形轮廓。问题是：算法如何调整高度图以保持道路左右水平。通过平均道路上每个点的高程来使道路完全水平很容易，但这不

1热度

3回答

高效的方式来找到一个数组中的最小差异对

我想解决一个问题，需要我找到一个数组中的最小差异对。例如，如果阵列是 6,7,1,3,9 输出是 (6,7) 具有1差是最小的。我能想出的最快解决方案是对数组进行排序并遍历排序后的数组，以找到最小差异[O（nlogn）]。有没有一种方法来优化或更好地解决O（n）或O（logn）？编辑：数组的所有元素都是不同的。

-1热度

1回答

连接两个三角形网格

我想问问你如何连接两个三维网格。我附上一个截图与两个半球三角形和打开。如何将它们连接成无孔的单个网格（单个球体）。两个网格的三角剖分应保持不变（无重新网格算法）。在此先感谢。 screenshot

0热度

1回答

查找一组间隔的最大深度

给定一组间隔I，形式为[a_i，b_i]的每个元素在O（n * logn）时间内找到最大深度的结束点b_i。将x的深度定义为点“刺入”（或相交）的间隔数。如果两个端点具有相同的深度，则返回较小的一个。尝试：我不知道如何找到它的O（N * LOGN）的时间。我理解寻找一组间隔的插入集合的贪婪算法，但严格地用O（n * log n）时间找到一个终点似乎是非常不同的。我可以尝试先排序间隔，然后蛮力

0热度

2回答

如何离散线段

如何找出一条线段经过的网格单元？例如，线段可以作为(8.3555 9.1654) -> (1.4123 5.6312)（以任意精度）给出。我要像顶部的第二图像中看到，改造成一个基于网格的表示这样的：我目前正在研究CGAL。它有包装Snap Rounding哪种做我正在寻找的，但仅用于细分市场的起点和终点。

0热度

1回答

凹面实现

我正在尝试实现下面描述的算法http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf 我正在使用以下类库。 Loyc库来自http://core.loyc.net/ using System; using System.Collections.Generic; using System.Li

0热度

2回答

拥有最终的泰森多边形，是否有可能找到最初的一组点？

我试图找到一种方法来扭转Voronoi算法。基本上，有一些连接的形状，这主要是由三角形和正方形的，我试图找到一套，使用的Voronoi算法将重新创建初始形状点。

3热度

3回答

将两个凸的非相交多边形合并为一个

我需要将两个凸的非交叉多边形合并为一个连接的凸多边形，以最小化所产生的面积，如下图所示：我正在寻找一个这样做的算法。如果有人向我提供相应的python实现，我也将不胜感激。

3热度

1回答

使用CGAL的Voronoi图：仅提取边缘点（凸包）

我想使用Voronoi图提取边缘点（点位于凸包的边界边缘上）。我知道一个无界单元格包含一个边界站点点，但是如何使用迭代器访问该信息？解决方案 VD vd; //initialise your voronoi diagram VD::Face_iterator it = vd.faces_begin(), beyond = vd.faces_end(); for (int f = 0; it