标签: computational-geometry

Jarvis：对于具有 h 个极值点的 n 个输入点，该算法在最坏情况下需要 O(nh) 时间。

Graham：最坏的情况下是 O(nlogn)。

来源 the ref of CGAL, from where I use the two algorithms.

这意味着当 h 小于 logn 时，Jarvis 对于数据集（假设是二维）速度更快。不过，我希望看到它的实际效果，但我未能找到用于此目的的数据集。有人知道吗？

谷歌搜索得到这个链接，它实际上支持我上面所说的。

我有一个点云 C，其中每个点都有一个关联的值。假设这些点在二维空间中，所以每个点都可以用三元组 (x, y, v) 表示。

我想找到局部最大值点的子集。也就是说，对于某个半径 R，我想找到 C 中点 S 的子集，使得对于 S 中的任何点 Pi（具有值 vi），在距离 Pi 的 R 距离内，C 中没有点 Pj 的值 vj 为大于 vi。

我知道如何在 O(N^2) 时间内做到这一点，但这似乎很浪费。有没有一种有效的方法来做到这一点？

旁注：

• 这个问题的根源是我试图在一个稀疏矩阵中找到局部最大值，所以在我的例子中 x, y 是有序整数 indeces - 如果这简化了问题，请告诉我！
• 如果解决方案仅适用于曼哈顿距离或其他任何问题，我非常高兴。
• 我在 python 中，所以如果有某种很好的矢量化 numpy 方法来做到这一点，那就太好了。

我需要找到一个凸多边形的最大内切圆，我搜索了很多网站，我知道这可以通过使用 Delaunay 三角剖分来完成。我在 CGAL 讨论中找到了一个使用 CGAL 的算法的线程：

您可以使用 CGAL 轻松计算：

首先，计算点的 Delaunay 三角剖分。

然后，迭代三角剖分的所有有限面。对于每个有限面 f

• 计算它的外心 c
• 在三角剖分中定位 c（为了加快速度，您可以将 f 的一个顶点作为点位置的起始提示）
• 如果 locate(c,hint) 返回的面是有限的，则外心 c 位于点的凸包中，因此，f 是候选者
• 如果 f 是这样的候选人脸，计算它的平方外接圆半径，只保留最小平方外接圆半径的脸

CGAL 手册（第 2 章 2D 三角剖分，以及内核中的一些内容）显示了执行此操作的每个基本功能。

我对这个算法的最后一部分有点困惑。当我阅读它时，我从中了解到三角剖分面的最小外接半径是最大内切圆的半径。但是从使用 Delaunay 三角剖分的多边形示例来看，似乎即使是最小的外接圆有时也无法放入多边形内，那么它如何与最大的内切圆具有相同的半径？

假设我有数百个甚至数千个 GPS 坐标、纬度和经度，它们构成了一个国家/地区的边界。

我也有我目前的位置纬度和经度。

我如何确定（使用 C#，为 Windows10 UWP 编程）我的位置是否在某个国家/地区的边界内？

EG 假设我拥有构成下图中红线的所有点。如果我在 X 位置，我的函数将返回 true。如果我在 Y 位置，我的函数将返回 false。

我正在尝试自定义绘制二维中随机点的Voronoi区域

import matplotlib.pyplot as plt
%matplotlib inline

from scipy.spatial import Voronoi
pt = np.random.random((10,2))
x = sp.spatial.Voronoi(pt)

# trial an error to figure out the type structure of [x]

plt.plot(x.vertices[:,0], x.vertices[:,1], '.', markersize=5)

# how to iterate through the x.regions object?
for poly in x.regions:
    z = np.array([ x.vertices[k] for k in poly])
    print z
    if z.shape[0] > 0:
        plt.plot( z[:,0], z[:,1])

plt.xlim([0,2])
plt.ylim([0,2])

为什么区域重叠？绘制无限区域的任何建议？

数据点只是随机数：

x.vertices

array([[ 0.59851675,  0.15271572],
       [ 0.24473753,  0.70398382],
       [ 0.10135325,  0.34601724],
       [ 0.42672008, …

任务

从一组不重叠（但接触）的多边形计算对偶图。

例子

多边形A、B和C，它们部分共享的坐标 1-22（黄色）和对偶图（蓝色）。

数据

我有一组S多边形。每个多边形P _i都表示为坐标的有序列表。多边形P _i的边a — b表示为P _i,(a,b)