1回答
凸壳的Graham扫描算法分析
algorithm、computational-geometry、testcase
我已经写了一个代码来实现凸包的Graham扫描算法。我已经通过生成一些测试用例对程序进行了测试。在所有情况下，它都会给出准确的结果。但我的问题是，当程序可能无法给出完美的凸包作为输出时，是否有可能生成一些棘手的测试用例？生成此类案例的过程是什么？
浏览 14提问于2016-09-18得票数 0
2回答
凸壳误解？
algorithm、convex-hull、grahams-scan
我写了一个Graham的扫描凸包算法的实现，对于测试数据，我使用了根据我的程序，凸包是
[(0.0,4.0),(1.0,4.0),(4.0,4.0),(3.0,2.5),(4.0,2.0在抱怨和抱怨之后，我在维基百科上读到“一个对
浏览 10提问于2012-06-27得票数 3
回答已采纳
1回答
gpu中的并行凸包算法
algorithm、computational-geometry、gpu
我正在实施分而治之的方法，以凸包在数据自动化系统。这是我的方法:自下而上：
NbegincurSize 创建一个列表列表来存储凸包； curSize =输入的大小(所有点)；for i: 1 to log curSize/ 2；在threads//Initially中，将列表中的每两个相邻凸壳合并成更大的船体(使用标准的上、下共同切线法)，它将列表中的每两个相邻点合并到
浏览 3提问于2011-07-30得票数 4
1回答
点列表的三维轮廓(凹面外壳线)
3d、points、concave
我在c#中有一个Vector3点的列表，我需要计算这些点的凹轮廓。周围确实有很多参考资料，特别是-凸分辨率(多亏了graham算法，我已经成功地实现了)，我也关心性能，所以能够先验地对算法速度进行基
浏览 2提问于2011-11-06得票数 3
回答已采纳
2回答
获取一组二维点的周长
algorithm、computational-geometry、convex-hull
我在2D中有一组点(x和y的坐标)，现在我需要丢弃所有对我没有意义的点，我的意思是我只对这些点所跟踪的区域感兴趣。简而言之，这就是它应该产生这样的结果问:什么算法可以对这些点进行这种过滤？
浏览 1提问于2013-03-31得票数 4
回答已采纳
1回答
检查格雷厄姆扫描中的非左转
algorithm、convex-hull、grahams-scan
根据Cormen的“算法简介”中对Graham扫描算法的描述，我发现了以下注意事项：
凸多边形的
浏览 4提问于2017-02-17得票数 0
回答已采纳
3回答
线性规划算法
algorithm、linear-programming
给出平面上两组点的P1, P2。而P1 = {1,2} and P1 = {3,4,5}
是否有一种基于线性设计的不使用凸壳的算法来解决这个问题？我很乐意
浏览 1提问于2020-12-22得票数 0
回答已采纳
1回答
重复-直到或Python中的等效循环
python、loops
我是Python编程的初学者。我正在尝试这个算法，它使用Graham的扫描方法找到凸包。但是，在伪代码中，有一个repeat ... until循环，我想不出用Python语言编写它的方法。
浏览 2提问于2013-05-26得票数 24
回答已采纳
1回答
在O(n)时间内，如何计算按x坐标排序的一组点的凸包？
algorithm、time-complexity、computational-geometry、convex-hull
我读过关于计算凸壳的算法。它们中的大多数花费O(n*log(n))时间，其中n是输入点的数目。., p_n}是一组按x坐标排序的点，即p_1.x <= p_2.x <= ... <= p_n.x.
我必须描述一个算法，它计算S的凸包，CH(S)，在O(n)时间。另外，我还要分析算法的运行时间。
浏览 4提问于2017-05-23得票数 5
回答已采纳
1回答
计算几何领域中最常见的算法是什么？
computer-science
到目前为止，我已经讨论了计算几何的各个方面，包括构造平面几何(轨迹交叉)、平面图拓扑算法、3D DDA，以及最近使用Graham的扫描和k均值聚类表示为Voronoi图的2D凸包实现。这是个迷人的领域。我很想知道更多。我想知道在这个领域里最常见的算法是什么，它们是做什么的。
浏览 0提问于2011-08-29得票数 3
回答已采纳
1回答
在3D空间中跟踪2D多边形-适当的算法？
algorithm、geometry、computational-geometry
我目前正在解决一个问题，我需要在3D空间中对构成平面多边形的节点进行适当的排序(使用类似于右手规则)。到目前为止，我的想法是构建一个转换矩阵，将节点转换到x-y平面，然后使用Graham扫描。我需要确保用户只输入凸多边形，所以如果我找到任何“内部”节点，我就知道多边形是凹的，并且会抛出错误。除了检查凸性之外，Graham扫描的排序过程还将为我排序节点。
我对优化的几何算法不是很熟悉
浏览 1提问于2011-05-11得票数 3
回答已采纳
2回答
合并具有最小周长的两个凸包
algorithm、merge、computational-geometry、convex-hull、convex
假设我们在平面上有两个(或更多)凸壳，并且我们希望合并它们。但是凸包的结果具有最小周长。有没有什么算法可以解决这个问题呢？
浏览 49提问于2021-10-06得票数 0
1回答
给定平面上的一组点，找出包含它们的极小面积的(不一定是凸的)多边形。
algorithm、geometry、computational-geometry
给定平面上的一组点，我想找到包含所有点的最小多边形。更准确地说，这个多边形的顶点必须是原始点集的子集。最简单的方法是用Graham的扫描算法在O(N log(N))时间内求出凸包，但理想情况下，我不要求多边形是凸的。这方面有什么标准办法吗？我认为这个问题相当困难，因为在我看来，不一定会有一个独特的解决办法。
浏览 0提问于2014-03-25得票数 2
回答已采纳
2回答
计算列表中两点的最大距离的最有效方法是什么？
algorithm、geometry、big-o
此方法的运行时复杂性为
凸壳最大的距离将是在凸壳的元素之间。，当你从凸包的一个点开始，从它的相邻点开始，对角线不断增加，达到最大值，然后继续减小。直觉上，我会继续改进算法:一旦第
浏览 4提问于2014-06-29得票数 17
1回答
检查点是否从二维凸包的面上可见
computational-geometry、delaunay、convex-hull
我正在尝试实现Bowyer-Watson算法来生成平面中一组点的Delaunay三角剖分。该算法假设存在一个有边界的超三角形，但也提到了一些替代方案，如保持点集的凸包。因此，当我们决定在增量算法中通过假设凸壳来产生点的delaunay三角剖分时，如果一个点位于凸壳之外，我们应该绘制从该点到凸壳上的所有顶点的顶点
浏览 2提问于2012-01-18得票数 1
3回答
求解有序点集的凸包算法
computational-geometry、sorted、convex-hull
我需要一个算法来计算三维和更高维度中排序的点集的凸包。此外，我需要在凸壳的较低部分，这是没有必要建立一个完整的凸壳。有没有什么高效快速的算法可以满足我的需求？
浏览 3提问于2013-05-15得票数 1
2回答
凸船壳分选步骤
algorithm、computational-geometry、convex-hull
我正在阅读格雷厄姆扫描算法，从CLRS中找出凸包。在CLRS中给出的凸壳的算法是：我无法理解这一行(算法的步骤2)：
如果两个或多个点相对于p0有相同的极角，那么除最远点外，所有这些点都是p0和最远点的凸组合，因此我们完全不考虑它们。如果一个以上的点对阿宝有相同的极角，我该怎么办？我的意思是，我应
浏览 3提问于2012-07-13得票数 2
回答已采纳
3回答
由一组点组成的最大三角形
computational-geometry
可能重复：
不过，那是我被困住的地方。从这些点中找出最大三角形的唯一方法是在n^3时刻使用蛮力，这在平均情况下仍然是可以接受的，因为凸包算法</e
浏览 2提问于2010-06-17得票数 11
云服务器
对象存储
ICP备案
云点播
腾讯会议
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号