最大凸包算法 - 腾讯云开发者社区

文章/答案/技术大牛

发布

1回答

来自DBSCAN的簇有时是非凸的？

machine-learning、clustering、dbscan

我已经在我的ML技术包中使用集群很长一段时间了，而且我从来没有找到这个问题令人满意的答案。我的困惑是，“半径”的概念，它描述一个凸对象，如何可以作为一个算法的输入，从而导致一个非凸对象？

浏览 0提问于2015-07-04得票数 5

回答已采纳

2回答

利用凸包算法对整数进行排序

sorting、convex-hull

二维凸包的算法使用排序。假设有人给了你一个用凸包实现为黑盒的库。演示如何使用凸包算法对给定整数序列进行排序。短语“黑盒”意味着您不查看代码内部；您只知道输入和输出是什么以及结果是什么样子。你不能从凸包的库实现中“拉出排序算法”。您可以假设您可以调用凸壳算法作为原始步骤。

浏览 2提问于2012-11-28得票数 3

4回答

是否有线性时间算法来寻找复杂多边形的凸包？

algorithm、polygon、time-complexity、convex-hull

我知道有一个最坏情况的O(n log n)算法来寻找复杂多边形的凸包，还有一个最坏情况的O(n)算法来寻找简单多边形的凸包。是否有一个最坏情况的O(n)算法来寻找复杂多边形的凸包？寻找复杂多边形的凸包等同于寻找无序点列表的凸包。

浏览 2提问于2010-07-31得票数 4

回答已采纳

3回答

最大超体积单纯形算法

algorithm、math、geometry、computational-geometry

最大可能的D-simplex的最优算法是什么?它的所有顶点都在集合中？代数上这意味着我们必须找到D + 1点的一个子集，这样，由第一D点和最后D + 1-st点的每个坐标的行构成的D * D矩阵的行列式在集合上具有最大的可能值(绝对值)。我确信，所有D + 1所需的点都是给定点集的凸包的顶点，但我需要算法，它没有使用任何凸壳算法，因为它们所需的单纯形是启动多边形等算法所需的。如果不可能在小于指数型的时间内得到单纯形，那么给出可调比的运

浏览 4提问于2014-06-17得票数 0

3回答

如何在三维空间中求凸壳

algorithm、computational-geometry、convex-hull

我试着从中了解算法，但没有得到多少。首先将所有点投影到xy平面上，然后通过选择具有最高y坐标的点来找到一个绝对在船体上的边缘，然后执行一次礼品包装迭代来确定边缘的另一个端点。我们这样做是通过选择点，使所有其他点都位于这个三角形的右边，当适当地观察时(就像礼品包装算法中一样，我们选择了一个边缘，使得所有其他点都位于该边的右边)。

浏览 4提问于2013-08-24得票数 22

1回答

识别一组地理空间点是否包含在另一组中

python、geospatial

{ group_id：(lat，long，data_val)，(lat，long，data_val) } 任何帮助寻找一个算法，以有效地识别是否包含在彼此之间的集群将是非常感谢的。

浏览 4提问于2014-06-02得票数 0

回答已采纳

1回答

A中不含点的最大凸包

computational-geometry、convex-hull

我在寻找A的子集，它的凸包最多包含来自B的n个点。有有效的算法吗？我的问题是2D。

浏览 2提问于2016-10-08得票数 0

1回答

凸包中点间的最大距离

python、algorithm、python-2.7、convex-hull

我正在解决一个问题，在这个问题中，我需要找到平面(2D) .So上两个点之间的最大距离，有一个O(n^2)方法，其中我计算了图中每个点之间的距离。我现在还实现了一个凸包算法，我的方法是在O(nlogn)中计算凸包，然后使用O(n^2)算法计算凸包中点间的最大距离。有比这更好的方法来计算凸包中的最大距离吗？以下是我的算法：

浏览 1提问于2016-10-15得票数 4

回答已采纳

1回答

动态和/或静态直线/正交/X-Y凸包

python、performance、algorithm、convex

我正在寻找一种有效的算法来处理2D动态。任何帮助都将不胜感激，Python中的算法，非常感谢。

浏览 7提问于2013-01-19得票数 2

1回答

N维点凸包中的最大单纯形

algorithm、geometry

给定n维点集的凸包C，是否有一个已知的算法(除了检查所有可能性)，它能找到完全在C中体积最大的单形的n+1角点？ (有关多边形/三角形的相同问题，请参见。)

浏览 0提问于2018-04-26得票数 2

回答已采纳

1回答

如何检查多边形是否凸？

algorithm、graphics、geometry

可能重复：一种明显的方法是运行凸包算法。如果凸包中的点数与多边形中的点数相同，这是否意味着多边形是凸的？

浏览 4提问于2011-12-29得票数 1

回答已采纳

4回答

如何在C#中计算凸包

c#、convex-hull

如何从点集开始计算凸包？我正在寻找凸包算法在C#中的实现

浏览 4提问于2013-02-03得票数 9

回答已采纳

10回答

如何找到两个最远的点？

algorithm、language-agnostic、geometry

最明显的方法是计算所有点之间的所有距离，并找到最大值。问题是它是O(n^2)，这使得它对于大型数据集来说非常昂贵。

浏览 2提问于2010-04-29得票数 60

回答已采纳

1回答

检查点是否从二维凸包的面上可见

computational-geometry、delaunay、convex-hull

我正在尝试实现Bowyer-Watson算法来生成平面中一组点的Delaunay三角剖分。该算法假设存在一个有边界的超三角形，但也提到了一些替代方案，如保持点集的凸包。因此，当我们决定在增量算法中通过假设凸壳来产生点的delaunay三角剖分时，如果一个点位于凸壳之外，我们应该绘制从该点到凸壳上的所有顶点的顶点，这些顶点包括从凸壳上可以看到该点的面。我应该最初生成所有点的凸包，或者像增量方法一样，一

浏览 2提问于2012-01-18得票数 1

2回答

计算机图形学中的最大凸补

c++、algorithm、c++11、graphics、3d

给定计算机图形学中的三维物体，其表面表示为三维三角形网格(由三维三角形物体组成的网格)，我需要在给定的三维物体的表面上找到最大连续凸补片。我必须将不同的颜色应用到对象上的不同凸块上，以表示选择。假设我有一个球体，那么整个球就是一个最大凸块。球面的任何部分都是凸的，最大我指的是可以找到的最大连续凸块。在渲染中，视视角而定，观看者所能看

浏览 6提问于2016-03-18得票数 1

回答已采纳

3回答