精华内容
下载资源
问答
  • 凸,凹多边形定义

    千次阅读 2017-04-27 10:29:35
    多边形(Polygon): 由三条以上的直线所组成的形状为多边形。 凸多边形(Convex Polygon):每个内角(Interior Angle)都是锐角(Acute Angle)或钝角(Obtuse Angle),也就是没有大于180°的优角(Reflexive Angle)搜索的...

    多边形(Polygon): 由三条以上的直线所组成的形状为多边形。
    凸多边形(Convex Polygon):每个内角(Interior Angle)都是锐角(Acute Angle)或钝角(Obtuse
    Angle),也就是没有大于180°的优角(Reflexive Angle)搜索的多边形。
    凹多边形(Concave Polygon):至少有一个优角(Reflexive Angle)的多边形。
    正多边形:(Regular Polygon)每条边相等,每个角也相等的多边形。
    凸多边形,就是把一个多边形任意一边向两方无限延长成为一条直线,如果多边形的其他各边均在此直线的同旁,那么这个多边形就叫做凸多边形,也可以理解为通过凸多边形的任意一条边作平面,并与此多边形所在的平面相异,那么凸多边形的其他所有部分都在所作平面的同一侧。
    凹多边形就是把一个各边不自交的多边形任意一边向两方无限延长成为一直线,如果多边形的所有边中只要有一条边向两方无限延长成为一直线时,其他各边不在此直线的同旁,那么这个多边形就叫做凹多边形。
    像正方形,是凸变形。 像五角星是凹变形

    展开全文
  • 简单多边形 P 的核(kernel),K(p)定义如下:K(p)由多边形内部的点构成,这些点与多边形的任何顶点相连所构成的线段完全包含在 P 中。 一个重要的性质是现,K(p)作为半平面的交集,它或者为空或者为完全包含在P...

    基础概念

    简单多边形 P 的核(kernel),K(p)定义如下:K(p)由多边形内部的点构成,这些点与多边形的任何顶点相连所构成的线段完全包含在 P 中。
    一个重要的性质是现,K(p)作为半平面的交集,它或者为空或者为完全包含在P 内的有界凸集。
    在这里插入图片描述
    红色部分。

    半平面,在数学定义下就是
    ax + by + c >= 0
    所控制的一个的半空间。半空间在不同维度下意义不同,如果是2维的话,其实此时ax + by + c >= 0 就是二维中一条直线的一侧。

    此时如果你再看核,其实可以理解为线性规划时得到的一个可行域。

    我们上面说到 如果是2维的话,其实此时ax + by + c >= 0 就是二维中一条直线的一侧。所以直线(也就是决定半平面的直线)切割多边形 ,让直线不断的去切割当前多边形,然后得到新的多边形。

    不难想象,其实结果可能是一个多边形(一定是凸的)、一个线段、空、一个点等等。我们记录顶点的数据来进行描述。

    综上,如果计算半平面的交集,可以使用一个

    • 将直线们极角排序,角度相同的保留下需要的一个
    • 用一个双端队列存储当前半平面交,每次通过判断队首与队尾第一个交点是否满足当前直线来更新
    • 先用队尾判定队首交点是否合法,再用队首判断队尾交点是否合法
    • 最后求出来的半平面交是一个凸多边形

    同理如果计算多边形交,可以将每一个边对应到一个半平面,从而运行半平面交集进行计算。

    Ref

    https://blog.csdn.net/weixin_30345577/article/details/97505934
    https://blog.csdn.net/accry/article/details/6070621

    展开全文
  • 有很多文章讨论在scratch中画圆的方法,所看到的文章中有如下方法:多边形逼近法、图章法、克隆法、三角函数法、...弧度定义:弧长/半径。所以360度角度所对应的弧度为2πr/r=2π,1度角度用弧度表示为2π/360,即近似

    有很多文章讨论在scratch中画圆的方法,所看到的文章中有如下方法:多边形逼近法、图章法、克隆法、三角函数法、方程遍历法、圆的标准方程法等。对于多边形逼近法,所看到文章都认为其缺点是很难精准的控制圆的半径和圆心的位置,感觉这种看法有些片面。首先看下面的脚本,使用360个边的多边形逼近圆,每边对应1度圆心角,边长为2,该圆圆心在(0,0),半径为114.6。见下图。
    源程序
    所画圆的半径是可以计算出来的。弧度定义:弧长/半径。所以360度角度所对应的弧度为2πr/r=2π,1度角度用弧度表示为2π/360,即近似为1/57.29578。所画圆1度圆心角对应的弧长近似为360个边的多边形的边长(为2),根据定义,1度角度所对应弧度1/57.29578=边长2/半径,则半径为57.29578*2= 114.59156。有了半径,就可以画指定圆心位置和半径的圆,例如圆心坐标为(x,y),半径为r,将画园起点移动到(x+r,y),即可画指定圆心和半径的园。以上脚本第1条语句“移到x:114.6 Y:0”,将圆心坐标设定为(0,0),圆的半径为114.6。第2条语句是设定第1条边的方向。运行效果图如下。请注意,铅笔的定位点在笔尖上,见下边右图。
    在这里插入图片描述
    应注意到,用360个边的多边形逼近圆,画圆的速度太慢了。在scratch中画圆,逼近圆的多边形的边长在15以下,就能画出比较满意的圆。可修改上边脚本:循环次数=48,每次右转7.5度,移动15步,看一看是否满意,速度快多了。见下图。
    在这里插入图片描述
    但有一个问题,圆心不在坐标原点上。这是由于设定第1条边的方向不正确。下边讨论如何得到第1条边的方向。为了直观,画出了用5、6和8条边的多边形逼近圆的图形。见下图。
    在这里插入图片描述
    这些图形都以x坐标轴为对称轴,以6边形为例,见上图,角1=角4,角2=角3,角2+角3=120度,则角4=30度,因此所画6边形的第1条边的方向为-150度,画6边形程序的第2条语句要改为“面向-150方向”。总结计算公式为:第一条边起始方向=-180+(右转角度/2)。在实际使用中,首先知道圆心位置和圆的半径,计算出周长,除以15,得出循环大概次数,调整循环次数使其能被360整除,得到循环次数,360度/循环次数得到每次右转的角度,然后用周长除以循环次数,得到每次移动步数。设定圆点坐标为:(0,0),半径=80,下边表中列出几种多边形逼近圆所需参数。
    几边形   半径   起始方向   起点坐标  循环次数  右转角度  移动步数
    5边形     8 0      -144       ( 8 0 , 0 )        5         7 2        100.53
    6边形      80      - 150      ( 8 0 , 0 )        6        6 0         83.78
    8边形      80      - 157.5    ( 8 0 , 0 )        8        4 5         62.83
    36边形     80      - 175     ( 8 0 , 0 )       36        1 0         13.96
    45边形     80      - 176     ( 8 0 , 0 )       45        8          11.17
    按表中参数,用36边形和45边形画圆所得图形见下图。可见两者所画的圆区别不大。
    在这里插入图片描述

    展开全文
  • 多边形极点,定义为,多边形内距离边界最远的点。我这里用来这个点位来标注凹多边形的名称,如下图,计算多边形质心位置时,不一定会落在多边形为内部,此时可以用极点来表示改多边形内部的点。 第三方库, mapbox...

    使用多边形极点对多边形进行标注,polygon pole of inaccessibility

    • 对应文中名称为自己翻译,仅供参考

    概念

    多边形极点,定义为,多边形内距离边界最远的点。我这里用来这个点位来标注凹多边形的名称,如下图,计算多边形质心位置时,不一定会落在多边形为内部,此时可以用极点来表示改多边形内部的点。
    极点位置
    凹多边形

    第三方库, mapbox提供了js库来计算多边形的极点坐标

    计算原理

    • 核心是通过划分规则格网,通过一定策略来确定极点位置

    对多边形划分格网

    计算步骤

    • 使用外包矩形宽高的最小值作为网格的初始大小,生成覆盖多边形的网格
    • 依次判断每个网格距离多边形的最短距离,加上网格的对角线的一半记为max
    • 依次比较每个cell的max,取max最大的网格作为最优网格
    • 依据网格的最小尺寸对最优网格进行四分,迭代判断每个网格是否为最优网格
    • 迭代时,使用queue,仅判断最大max的网格

    实例

    • leaflet实例如下:

      /*
      testdata为geojson数据
      将geometry的多个coordinates传入作为方法参数,设置网格的最小尺寸即可
      polylabel默认使用多边形的外边界进行计算
      */
      let lxs_data = L.geoJSON(
          testdata.features,
          {
              onEachFeature: (feature, layer) => {
                  let polygon = feature.geometry.coordinates;
                  let polypoint = polylabel(polygon, 0.001);
                  var popup = L.popup()
                      .setLatLng([polypoint[1],polypoint[0]])
                      .setContent('<p>lxs!<br />This is a lxs popup.</p>')
                      .openOn(mymap);
              }
          })
          .addTo(mymap);
      
    展开全文
  • 多边形填充

    2014-05-04 10:55:17
    按照图像学书上的讲解,多边形的填充可以采用
  • 多边形、凹多边形、凸包算法

    千次阅读 2020-06-29 22:23:39
    (Convex Polygon)可以有以下三种定义: 1、没有任何一个内角是优角(Reflexive Angle)的多边形。 2、如果把一个多边形的所有边中,有一条边向两方无限延长成为一直线时,其他 3、凸多边形是一个内部为凸集的简单...
  • 多边形表示城市的范围 所以问题的本质意思是求一个点是否在一个多边形内(这个多边形既可以是凸包 或者可能是凹包) 但是同时也要注意corner case:比如说乘客站在两个城市的边界上怎么办(我们可以找其周围的两三...
  • 在OpenCV里用fillPoly填充多边形

    千次阅读 2019-12-30 17:11:09
    前面学习过fillConvexPoly函数,这个函数是用来填充凸多边形的,但在OpenCV里还添加了fillPoly函数,这个函数与fillConvexPoly函数有什么差别呢?一般来说,fillPoly函数可以...下面来看一下函数定义: 其中参...
  • 耳切法处理多边形三角划分

    万次阅读 2016-10-18 09:23:04
    2016.10.18 孙广东 ...  日文《【Unity】Ear Clipping Triangulation》, 它使用这个技术 弄了软体的功能 ...这也是我Get到的新概念. 一种 网格多边形三角化算法之一。 我之前 也写过文章关于在Unity下 使用Mesh...
  • 多边形包围区域

    2017-03-27 22:58:27
    多边形包围区域
  • 常见凸多边形判断方法

    万次阅读 2013-08-21 21:15:33
    多边形的判定方法 在计算几何和地理信息系统中,...一些基础概念 顶点、向量、向量叉乘、 一般来说,多边形是由首尾相连的顶点组成的。这里的顶点就是几何中的点。向量,在2D以及3D几何中,点和向量可以用一个类或者
  • 简单多边形与圆相交求面积简单多边形的有向面积简单多边形与圆相交的有向面积圆心三角形与圆相交求面积 简单多边形的有向面积 所谓简单多边形,就是指...另外一个需要注意的概念就是多边形的凹凸性。一般而言,凸多...
  • 一、SVG概念 1.什么是SVG? SVG英文全称为Scalable Vector Graphics,意思为可缩放的矢量图 2.位图和矢量图 在计算机中有两种图形, 一种是位图, 一种是矢量图 2.1 位图: 传统的 jpg / png / gif图都是位图 位图...
  • 多边形建模方式取消了三角面的概念,它不仅可以定义三角形面,还可以定义四边形面和多边形面。本节我们首先来了解多边形建模工作模式和使用方法。 9.3.1 多边形建模的工作模式 多边形对象与网格对象最根本的区别...
  • (30)点多边形测试

    2018-07-18 17:18:47
    * 概念介绍 测试一个点是否在给定的多边形内部,边缘或者外部 *API介绍 cv::pointPolygonTest pointPolygonTest( InputArray contour,// 输入的轮廓,一个轮廓一个轮廓的做 Point2f pt, // 测试点 测试的像素点...
  • 求任意多边形面积

    2018-06-03 11:33:31
    首先声明一个概念:三角形外积: 把向量外积定义为: |a ×b| = |a|·|b|·sin<a,b>. 方向根据右手法则确定,就是手掌立在a、b所在平面的向量a上,掌心向b,那么大拇指方向就是垂直于该平面的方向,被...
  • 多边形上的最优三角剖分问题也是动态规划经典题目,此类问题基本上都是在一个给定的凸多边形上规划三角形分割,使得剖分后得到的一系列三角形的某种结果最优,比如三角形的面积之和最大(或最小),或者是三角形的...
  • 扫线法快速判断凹多边形相交

    千次阅读 2020-01-08 00:55:14
    这个开源库基于Unity开发,主要实现了凹多边形之间的相交判断,当然也可以应用于顶点与凹凸包、线段与凹凸包、凸包与凸包之间的相交判断,也就是说,这个方案基本可以解决前面两则文章中的所有多边形判断,效率也...
  • 概念介绍 测试一个点是否在给定的多边形内部,边缘或者外部 API介绍 API double cv::pointPolygonTest(InputArray contour, Point2f pt, bool measureDist) 参数介绍 第一个参数InputArray contour,输入...
  • 平面区域填充算法是计算机...区域填充中最常用的是多边形填色,本文中我们就讨论几种多边形区域填充算法。一、种子填充算法(Seed Filling) 如果要填充的区域是以图像元数据方式给出的,通常使用种子填充算法(Seed F
  • 多边形的填充,算法原理,特殊情况的处理办法。
  • OpenGL(五)多边形

    2020-02-05 20:13:12
    显存只存在显卡里面,是显卡独有的概念,缓冲区是ram区,高速读取区,你写代码操作的所有内存都可以称为缓冲区,显存属于缓冲区的一种 (1)多边形的两面以及绘制方式。 虽然我们目前还没有真正的使用三维坐标来...
  • 图形学中呈现多边形的总体目的就是可视精度和速度。精确性是依具体情况而言的,对于机械而言,精确指的是模型的渲染在一定的误差范围;对于一个太空模拟游戏,最重要的是整体的感觉,模型的使用就成了关键。对于一...
  • 二、扫描线算法(Scan-Line Filling) 扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何位置,不需要指定种子点,适合计算机自动进行图形处理的场合使用,比如电脑游戏和三维CAD软件的渲染等等。...
  • 例如,椭圆是封闭曲线,故有椭圆的内部与椭圆的外部的概念。ThingJS不仅实现矩形、多边形的创建,也能够开发控制圆形。 矩形区域和圆形区域都很好画,大部分建模工具可直接拖拽生成,但多边形区域则需要确定多边形要...
  • 程序化随机多边形地图生成

    千次阅读 2017-08-01 14:02:30
    最近跟团队想要开发一个开放世界的游戏,这是很有趣的游戏概念,然而参考了《塞尔达传说 荒野之息》的设定后发现,这个游戏的成功很大程度是美工和设计大量的工作,才形成了这个很有趣的大陆,然而我们的团队没有...
  • 题目描述给出一个简单多边形(没有缺口),它的边要么是垂直的,要么是水平的。要求计算多边形的面积。多边形被放置在一个X-Y的卡笛尔平面上,它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值...
  • 基于2D多边形的碰撞检测和响应

    千次阅读 2012-02-05 12:01:08
    这里的碰撞是基于多边形而不是基于精灵的。这两者之间在设计上会有不同。 基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点,时间和碰撞方向。虽然多边形仅仅是精灵的一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,746
精华内容 4,298
关键字:

多边形定义的概念