查找一组点是否描述凸包络的算法
凸包是一个计算几何的概念，它是一个包含一组点的最小凸多边形。在计算机科学中，凸包算法是一种用于找到一组点的凸包的算法。
常用的凸包算法有：
- Graham Scan算法：该算法基于凸包的一个重要性质，即凸包上的任意两个点之间的线段不会包含在凸包内部。该算法的时间复杂度为O(nlogn)。
- Jarvis March算法：该算法基于凸包的另一个重要性质，即凸包上的任意两个点之间的线段不会包含在凸包内部。该算法的时间复杂度为O(n^2)。
- Chan算法：该算法基于凸包的一个重要性质，即凸包上的任意两个点之间的线段不会包含在凸包内部。该算法的时间复杂度为O(nlogn)。
在实际应用中，可以根据具体情况选择合适的算法来计算凸包。
推荐的腾讯云相关产品：
- 腾讯云数据库：提供了MySQL、PostgreSQL、MongoDB等多种数据库产品，可以满足不同应用场景的需求。
- 腾讯云服务器：提供了弹性云服务器、负载均衡、CDN等多种服务器产品，可以满足不同应用场景的需求。
- 腾讯云云原生：提供了Kubernetes、容器服务等多种云原生产品，可以满足不同应用场景的需求。
产品介绍链接地址：
相关·内容
2回答
一组点描述凸包络的算法
algorithm、convex-polygon
我想检查一组N点是否描述凸多边形以下是我想到的一些方法：
如果集合等于他的凸包，那么它就是凸的。该算法的复杂度为O(n*LN(N))。3.看角度:
然后，我想检查两个连续向量的角度是否不超过180°。但是，由于我的<
浏览 3提问于2011-07-04得票数 7
回答已采纳
1回答
识别一组地理空间点是否包含在另一组中
python、geospatial
在这个项目的这个阶段，我有两种类型的卫星数据(MODIS和AMSR)已经过滤和地理聚集。下一步是识别来自AMSR数据的任何集群是否在任何MODIS集群的范围内。我使用SciKit的DBSCAN库(在python中学习)对两个数据集中的高值点进行了单独的聚类，但我不确定如何确定一种类型的集群是否位于另一种类型的集群中。来自每个数据集的输入存储在python字典中，将集群ID映射到点及
浏览 4提问于2014-06-02得票数 0
回答已采纳
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
回答已采纳
8回答
如何找到O(nlogn)中相交直线的上包络？
algorithm、geometry、computational-geometry、analysis
所以有n条直线(y= ax + b)，我想找出它们的上端信封(图片中的粗体部分)。它必须在O(nlogn)中。我所理解的是，我需要找到一种方法来忽略某些行，因为如果我搜索所有行，它不会是O(nlogn)。
浏览 0提问于2011-09-15得票数 19
回答已采纳
1回答
多边形等高线到多边形的无序云点
python、geometry、2d、polygon、computational-geometry
亲爱的斯塔克溢流社区
由于多边形的非凸形状，我不能使用凸包包络。我不能用最小距离准则，因为轮廓的其他部分的一些点离得更近(例如:点A必须与B连接，但更接近C)。由于轮廓的不规则形状，我不能使用顺时针顺序。有谁知道(在Python中优先实现)一种从起点重新排
浏览 2提问于2015-03-30得票数 0
2回答
缠绕数算法与凸的边界/边上的点
c++、algorithm、point-in-polygon、convex
我需要的算法可以告诉我，如果点位于凸包(C/C++)的内部/外部或边界(边)。如果点恰好位于凸面的边界(边)上，是否有可能以及如何使缠绕数算法进行检测？有没有其他<em
浏览 21提问于2016-06-08得票数 3
1回答
检查点是否从二维凸包的面上可见
computational-geometry、delaunay、convex-hull
我正在尝试实现Bowyer-Watson算法来生成平面中一组点的Delaunay三角剖分。该算法假设存在一个有边界的超三角形，但也提到了一些替代方案，如保持点集的凸包。因此，当我们决定在增量算法中通过假设凸壳来产生点的delaunay三角剖分时，如果一个点位于凸壳之外，我们应该绘制从该点到凸壳上的所有顶点<em
浏览 2提问于2012-01-18得票数 1
1回答
如何获取L.polygon边界，不包括内点
javascript、arrays、leaflet、openstreetmap
我有一个由纬度和经度描述的地理点数组，以及一个基于这些点的多边形。如何删除多边形的内点而只绘制它的外部边界？这是500分的全部显示。 ? 我所期待的结果。这里所有的内部点都被移除，显示了覆盖的区域。 ?
浏览 51提问于2019-05-05得票数 1
回答已采纳
2回答
如何获得voronoi单元格周围的点？
c++、algorithm、polygon、voronoi
我正在尝试获取形成多边形的点，以便用一些颜色填充它。我有一组点，然后我计算它的Voronoi图。结果是这样的：绿点是我定义的点，蓝点是Voronoi图的计算顶点。我想填充由特定绿点生成的多边形，因此我需要知道它周围有哪些点来形成多边形并填充它。
我读过关于和的文章，但它似乎不是我所需要的。有没有什么算法可以满足这种需
浏览 2提问于2013-05-29得票数 6
1回答
如何检索2d图上最外层的点？
algorithm
我有一个二维图，上面画了一些点。我似乎无法理解的是，我需要使用的算法才能做到这一点？我认为这可能会帮助你理解我想要实现的目标：o x o我想得到的所有的o和我想忽略的x。而且，点可以在任何位置和任何形状，但我仍然只想抓住外层的大部分点。
有
浏览 0提问于2013-01-16得票数 3
回答已采纳
1回答
求点是否在由一组点生成的凸壳中
c++、algorithm、computational-geometry
我需要从一组点计算凸包。集合的大小很小，通常为2~ 10。
我需要的任务是判断一个点是否在由点集构造的凸包内。有哪些算法可以执行这些操作，或者我是否可以使用现有的库？
浏览 2提问于2016-08-15得票数 0
3回答
属多面体内的长方体
performance、algorithm、computational-geometry
我正在寻找一种有效的算法来找出一个长方体是完全在里面还是完全在外面，或者(不内外)一个普通的(凹的或凸的)多面体。多面体由三维点和面的列表定义。每个面都是由等高线点的子集来定义的，例如向外的右侧法线点。谢谢
浏览 6提问于2014-06-12得票数 3
回答已采纳
7回答
找出一个点是否在一组点的凸包内，而不计算凸包本身
algorithm、graphics、geometry、computational-geometry
验证点P是否在由一组点X形成的凸包内的最简单方法是什么？
我想要一个在高维空间(例如，高达40维)中工作的算法，它不会显式地计算凸壳本身。有什么想法吗？
浏览 0提问于2011-02-05得票数 47
2回答
利用两凸壳的切线进行合并的算法在实际中是如何工作的？
c++、convex-hull、divide-and-conquer
我试图在C++中实现分而治之的算法，从一组二维点求出凸包。为了简单起见，让我们假设所有的点都是用整数描述的。合并很简单，如果你找到了描述切线的四个点，那么由这
浏览 5提问于2014-09-13得票数 2
回答已采纳
2回答
R中点集上凸壳的求取
r、ggplot2、convex-hull
我试图获得与生产率数据相关的一组点的上凸壳( R )。我希望它是一个规模收益递减的函数，输入是工时，输出是完成工作的度量。我想要上凸壳，因为这将使我得到效率的前沿。我在R中搜索并找到了方法chull，但这给出了整个包络中的一组点，而不仅仅是上面的船体点。有没有一种方法可以自动选择R中的上船体点？
例如，我们可以
浏览 9提问于2022-04-11得票数 3
回答已采纳
2回答
在2D中查找远程点
c#、2d、point
我在无限大平面上有一组点(嗯，双精度)二维平面。橙色点就是我想得到的例子。它们到底在哪里并不重要，只要它们离所有的黑点相对较远。更新:使用delaunay算法查找大的</
浏览 2提问于2009-09-25得票数 2
回答已采纳
1回答
如何在矩形周围获得最小长度的电路？
graph
在最后一次比赛中，我得到了一组建筑，我需要在这些建筑周围创建最短长度的栅栏。栅栏可以接触建筑物的角落，墙壁，但不能通过建筑物，所有建筑物必须在一个区域内。
我知道我需要在栅栏的多边形的边缘构建角点。
浏览 0提问于2012-11-07得票数 0
回答已采纳
1回答
求一组交叉口中的所有四元数
math、language-agnostic、geometry、theory
我想取一组线的所有交点，找出它们所创建的所有凸四元数。我不确定是否有一个完美的算法，或者我是否需要循环并创建自己的算法。
我有一系列的线，以及它们的所有交叉点。我怎样才能做到这一点？如果没有一个算法可以实现，我如何检查每个交点与其他交叉口，以确定他们是否形成一个凸四边形？
浏览 5提问于2017-07-21得票数 3
6回答
(经度，纬度)-points在球面上的凸壳
geometry、geospatial、latitude-longitude、computational-geometry、convex-hull
标准凸包算法不适用于(经度、纬度)-points，因为标准算法假设您想要一组笛卡尔点的外壳。经纬度点不是笛卡尔的，因为经度“绕”在反子午线(+/- 180度)。也就是说，东经179度是-179度。所以，如果你的一组点正好跨越了反子午线，你就会计算出虚假的船体，它们在世界各地伸展得不对。
对于技巧，我有什么建议可以用标准的凸壳算法
浏览 8提问于2012-03-13得票数 26
回答已采纳
1回答
从点集中求四边形的角点
algorithm、math、trigonometry、corner-detection
我试着从一组点中得到四边形的角点。
第二张图片有点极端，但我的一组</e
浏览 2提问于2013-03-12得票数 8
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
