在给定平面上具有坐标的一组点的情况下，找出最大周长的简单多边形
。
答案： 要找出最大周长的简单多边形，可以使用凸包算法来解决。凸包是包含所有点的最小凸多边形。
凸包算法有多种实现方式，其中一种常用的算法是Graham扫描算法。以下是解决该问题的步骤：
- 首先，根据给定的点集，找到最低的点（y坐标最小），如果有多个点具有相同的最低点，则选择最左边的点作为起始点。
- 将起始点与其他点按照极角进行排序，极角是指从起始点到其他点的连线与x轴正方向的夹角。
- 从排序后的点集中选取前两个点作为凸包的起始边。
- 依次遍历剩余的点，对于每个点，判断它与凸包的最后两个点构成的边是否为左转，如果是左转则将该点加入凸包，否则将最后一个点从凸包中移除，直到找到一个左转的点或者凸包中只剩下两个点。
- 遍历完所有点后，得到的凸包就是最大周长的简单多边形。
凸包算法的时间复杂度为O(nlogn)，其中n为点的数量。
腾讯云相关产品推荐： 腾讯云提供了丰富的云计算服务和解决方案，以下是一些相关产品的介绍：
- 云服务器（CVM）：提供弹性计算能力，可根据业务需求快速创建、部署和管理虚拟服务器实例。 产品介绍链接：https://cloud.tencent.com/product/cvm
- 云数据库MySQL版（CDB）：提供高性能、可扩展的关系型数据库服务，适用于各类应用场景。 产品介绍链接：https://cloud.tencent.com/product/cdb_mysql
- 云存储（COS）：提供安全可靠的对象存储服务，适用于存储和处理各类非结构化数据。 产品介绍链接：https://cloud.tencent.com/product/cos
- 人工智能平台（AI Lab）：提供丰富的人工智能服务和工具，包括图像识别、语音识别、自然语言处理等。 产品介绍链接：https://cloud.tencent.com/product/ailab
请注意，以上推荐的腾讯云产品仅供参考，具体选择应根据实际需求进行评估和决策。
相关·内容
多边形必须由所有n个点组成。可以保证任何三个点都不是共线的。现在，我只能想出暴力算法。我想知道是否有其他方法来解决这个问题。点集的体积可以达到10^5。欢迎任何想法:)
浏览 19提问于2021-05-30得票数 0
1回答
给出一个简单的(不相交的)多边形，如平面图(房间之间的门不开，以便给出一个简单的不间断的边界)。如何从(x，y)点(在多边形的边界内或边界上)找到多边形内的所有区域？理想情况下，我希望从这里返回一个多边形，然后可以覆盖显示所有可到达的区域。我考虑了A*搜索类型的方法，其中我将
浏览 2提问于2021-03-21得票数 2
回答已采纳
4回答
非自交多边形生成算法的有效性
、、、、
作为对的扩展和部分回答，我编写了一个简单的算法，给出一组点(具有xy坐标)可以形成一个非自交多边形。
假设存在一个包含所有顶点的集合V2)设想一条与x轴平行的直
浏览 1提问于2011-03-11得票数 4
回答已采纳
给定平面上的一组点，我想找到包含所有点的最小多边形。更准确地说，这个多边形的顶点必须是原始点集的子集。最简单的方法是用Graham的扫描算法在O(N log(N))时间内求出凸包，但理想情况下，我不要求多边形是凸的。这方面有什么标准办法吗？我认为这个问题相当困难，因为在我看来，不一定会有一个独
浏览 0提问于2014-03-25得票数 2
回答已采纳
3回答
最大超体积单纯形算法
、、、
给出了D-dimensional空间中的一组点。最大可能的D-simplex的最优算法是什么?它的所有顶点都在集合中？代数上这意味着我们必须找到D + 1点的一个子集，这样，由第一D点和最后D + 1-st点的每个坐标的行构成的D * D矩阵的行列式在集合上具有最大的
浏览 4提问于2014-06-17得票数 0
给定一个可能是凹的、可能有洞的多边形，我如何才能得到由其顶点的子集组成的最大的简单凸多边形？，最大的简单凸多边形可能会旋转到多边形的另一半，因此，它不会掉下先前的点，而是下降(30，2.01)，并将(31.91，0.62)替换为在该点和(3
浏览 4提问于2021-12-28得票数 0
2回答
二维和三维空间中多边形中心的计算
、、、、
考虑二维笛卡尔空间中的简单凸多边形。如果给出一个在逆时针方向上排序的顶点坐标列表，就像这个[[x0, y0], ..., [xn, yn]]。如何计算多边形的中心(多边形内的点，即与所有顶点等距的)？我现在意识到我<e
浏览 5提问于2013-08-19得票数 3
回答已采纳
4回答
我试图对光线投射算法()进行编码，以便在以下情况下有效：
多边形很简单，但不一定是凸的。我将使用从点( xp，yp)向右的水平射线: xr =xp+ a，a>=0，yr = yp。我不需要循环遍历多边形的所有
浏览 4提问于2014-08-14得票数 0
5回答
我在3D中有两个凸多边形。它们在不同的平面上都是平的，所以它们是一对面。编辑:端点在第一个多边形中，另一个端点在第二个多边形中的最短直线的长度。我要找的距离是这条最短的线的长度。
浏览 4提问于2011-02-25得票数 8
回答已采纳
7回答
球和环面是不翻转的边，克莱因瓶-有一个翻转边，射影平面与两者。这是投影平面的基本多边形(或闭包规则)的单独图片(用于1..N符号)：
[1, 1]格的N x
浏览 0提问于2023-05-22得票数 14
2回答
寻找内外多边形之间的桥梁
、、、、
我在三维空间中有几个多边形(作为顶点和边的环)，但它们位于同一平面上。我需要在“洞”和“多边形”之间找到一座桥梁：红桥
如果多边形是以树的形式包含的，那么是否有人知道为多边形寻找这样的桥梁的算法:多边形作为父元素，并且包含作为子元素的所有洞？我找到了这样的材料(4.寻找相互可见的顶点)：
但我不知道如何将这个
浏览 3提问于2022-04-08得票数 1
我和几个相互重叠的凸多边形一起工作，我需要把它们组合在一起，形成一个可能是凸的或凹的多边形。1)我需要合并的多边形总是凸的。( 4)最后的多边形只能是简单的凸多边形或凹多边形，
浏览 1提问于2019-09-06得票数 2
回答已采纳
2回答
在内存范围查询中执行地理哈希
、、、、
我试图在内存中做一个非常简单的地理哈希范围查询，我正在使用下面的软件来计算Geo散列- 和我有一个Cython包装器在Python3.6中调用这些API。我使用一个来存储geohash，我的目标是在内存中执行一个简单的Geo散列范围查询。我希望窗口在0.1度以内，或者我指定的任何窗口。我不知道怎么算窗户。整个Geo散列包非常快，我只对查询的近似匹配感兴趣。我相信我的测试点应该在输入数据集的“范围”之
浏览 0提问于2018-09-14得票数 0
4回答
我正试图计算出最上面最相交的任意几个平面，没有joy！我正在使用actionscript，但只需要找到一个我可以实现的算法。
然而，当我们允
浏览 0提问于2011-07-30得票数 9
7回答
我正在寻找一种算法，以生成一个多边形内均匀分布的点。我有一个由每个点的角点(x，y)上的点的坐标指定的多边形。我得到了多边形内部要生成的点的数量。例如，假设我有一个包含5个点的多边形：(1，1)；(1，2)；(2，3)；(3，2)；和(3，1)
我需要在<em
浏览 6提问于2012-06-24得票数 9
回答已采纳
我是Paraview的新手，我想问一下如何才能制作水库的3D视图。我也读过以前的一些文章，最好的方法可能是应用一个过滤器"Alphabetical -> Delaunay2D“(例如)。我也尝试过；不幸的是，由于我的域不是矩形的，所以在主域之外形成了一些无用的三角形。在上面的链接中，它可以很容易地使用，因为域是一个矩形。
浏览 0提问于2016-12-08得票数 0
5回答
找到小叶多边形的中心？
、、、
我在我创建的地图上有一堆传单多边形。每个多边形代表不同的东西。根据用户所在的页面，在弹出窗口中显示一组特定的信息。我需要找到一种方法，使“弹出式”泡泡在它所代表的多边形中心打开。每个多边形都使用以下代码绘制： [74.0995, -99.92615], [74.07691, -99.3383
浏览 2提问于2014-04-01得票数 33
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
