-
2021-03-15 14:03:26
算法思想:动态规划
实际问题:多边形游戏
编写语言:Java
前言
多边形游戏问题是矩阵连乘的最优计算次序问题与凸多边形最优三角剖分问题的推广。我在解决凸多边形最优三角剖分问题时偶然间看到了这个结论,便跳过了该问题,直接解决其推广的问题,即多边形游戏问题。对于凸多边形最优三角剖分问题有兴趣的读者,可以自行百度。
问题描述
有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符。每条边被赋予一个运算符+或*。所有边依次用整数1到n编号。
游戏规则:
删去一条边
后续步骤按以下方式操作:
选择一条边E及边E的两个顶点v1和v2
用一个新的顶点v取代边E及由E连接着的2个顶点,将2个顶点上的数值由E上的运算符获得结果,病赋值给新的顶点v。最后,所有的边都被删除,游戏结束,得到游戏分数(最后顶点上的整数值)
问题:对于给定的多边形,计算最高得分
关键特征
设给定的多边形的顶点和边的顺时针序列为 op[1], v[1], op[2], v[2], ..., op[n], v[n]。其中 op[i] 表示第 i 边所对应的运算符,v[i] 表示第 i 个顶点上的数值,1 <= i <= n。
在所给定的多边形中,从顶点 i 开始,长度为 j(链中有 j 个顶点) 的顺时针链 p(i, j) 可表示为 v[i], op[i + 1], ..., v[i + j - 1]。如果这条链的最后一次合并运算发生在 op[i + s] 处,则可在 op[i + s] 处将链分为两个子链 p(i, s) 和 p(i + s, j - s)。
设 m1 是子链 p(i, s) 内部合并得到的值,设 a 和 b 是子链 p(i, s) 内部合并可能得到的最小值和最大值;设 m2 是子链 p(i + s, j - s) 内部合并得到的值,设 c 和 d 是子链 p(i + s, j - s) 内部合并可能得到的最小值和最大值。则有:a <= m1 <= b, c <= m2 <= d。而两个子链合并得到的结果 m = (m1)opi + s。分析运算符的情况可得:
当op[i + s] = '+'时,显然有 a + c <= m <= b + d。即链 p(i, j) 合并的最优性可由子链 p(i, s) 和 p(i + s, j - s) 的最优性推出。且最大值对应子链的最大值,最小值对应子链的最小值。
当op[i + s] = '*'时,考虑到 v[i] 可以取负整数,显然有 min{ac, ad, bc, bd} <= m <= max{ac, ad, bc, bd},亦可由子链的最有性推出原链的最优性。
综上,可得多边形游戏问题满足最优子结构性质
递归结构
设 m[i, j, 0] 是链 p(i, j) 合并的最小值,m[i, j, 1] 是链 p(i, j) 合并的最大值,并设最优合并在 op[i+s] 处,为方便起见,记:a=m[i, i+s, 0], b=m[i, i+s, 1], c=m[i+s, j-s, 0], d=[i+s, j-s, 1],则关系式满足:
当 op[i+s]='+', min(i, j, s) = a+c, max(i, j, s) = b+d
当 op[i+s]='*', min(i, j, s) = min(ac, ad, bc, bd), max(i, j, s) = max(ac, ad, bc, bd)
由此可知 m[i, j, 0]=min(min(i, j, s)), m[i, j, 1]=max(max(i, j, s)),其中 1 <= s <= j - 1,这是个循环求值的过程。
Java代码
//本代码所用示例为:+ -7 + 4 * 2 * 5
public class PolygonGame
{
static int n; //边和点个数
static int minf, maxf;
static int[] v; //点集
static char[] op; //边集
static int[][][] m; //存储最终计算结果
public static void main(String[] args)
{
n = 4;
//以下所有数组下标为0的都不使用
//构造出的多边形的最终结果:+ -7 + 4 * 2 * 5
v = new int[]{Integer.MIN_VALUE, -7, 4, 2, 5};
op = new char[] {' ', '+', '+', '*', '*'};
m = new int[n + 1][n + 1][2];
for(int i = 1; i <= n; i++)
{
//m[i][j][0]:表示链的起点为i,长度为j时的结果最小值
m[i][1][0] = v[i];
//m[i][j][1]:表示链的起点为i,长度为j时的结果最大值
m[i][1][1] = v[i];
}
int result = polyMax();
System.out.println(result);
}
/**
* 参数含义:
* i:链的起点
* s:断开位置
* j:链长度
*
*/
public static void minMax(int i,int s,int j)
{
int[] e = new int[n + 1];
int a = m[i][s][0],
b = m[i][s][1],
r = (i + s - 1) % n + 1, //多边形是封闭的,不能出现下标溢出
c = m[r][j - s][0],
d = m[r][j - s][1];
if(op[r] == '+')
{
minf = a + c;
maxf = b + d;
}
else
{
e[1] = a * c;
e[2] = a * d;
e[3] = b * c;
e[4] = b * d;
minf = e[1];
maxf = e[1];
for(int k = 2; k < 5; k++)
{
if(minf > e[k])
minf = e[k];
if(maxf < e[k])
maxf = e[k];
}
}
}
public static int polyMax()
{
for(int j = 2; j <= n; j++) //链的长度
//链的起点,多边形是封闭的,不会存在什么问题
for(int i = 1; i <= n; i++)
for(int s = 1; s < j; s++) //断开的位置
{
minMax(i, s, j);
if(m[i][j][0] > minf)
m[i][j][0] = minf;
if(m[i][j][1] < maxf)
m[i][j][1] = maxf;
}
int temp = m[1][n][1];
for(int i = 1; i <= n; i++)
if(temp < m[i][n][1])
{
temp = m[i][n][1];
}
return temp;
}
}
运行结果
更多相关内容 -
【OpenGL】十八、OpenGL 绘制多边形 ( 绘制 GL_POLYGON 模式多边形 )
2021-01-20 09:43:11一、绘制 GL_POLYGON 模式多边形、 二、多边形绘制顺序分析、 三、相关资源
一、绘制 GL_POLYGON 模式多边形
使用 glBegin(GL_POLYGON) 设置绘制多边形 , 不管有几个点 , 都按照指定的顺序连接起来 ;
注意 : 这些点组成的多边形必须是凸多边形 , 不能是凹多边形 ;
代码示例 :
// 只显示正面 , 不显示背面 //glEnable(GL_CULL_FACE); // 设置顺时针方向 CW : Clock Wind 顺时针方向 // 默认是 GL_CCW : Counter Clock Wind 逆时针方向 //glFrontFace(GL_CW); // 主消息循环: while (GetMessage(&msg, nullptr, 0, 0)) { if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg)) { TranslateMessage(&msg); DispatchMessage(&msg); } // 渲染场景 // 清除缓冲区 , // 使用之前设置的 glClearColor(1.0, 0.0, 0.0, 1.0) 擦除颜色缓冲区 // 红色背景 glClear(GL_COLOR_BUFFER_BIT); // 设置当前的绘制颜色 , 4 个 unsigned byte // 每个颜色的分量占一个字节 // 参数数据是 R 红色 G 绿色 B 蓝色 A 透明度 // 下面设置的含义是白色, 绘制点的时候, 每次都使用白色绘制 glColor4ub(255, 255, 255, 255); // 设置线的宽度 glLineWidth(2.0f); //glBegin(GL_POINTS); // 绘制点 //glBegin(GL_LINES); // 绘制线 //glBegin(GL_LINE_STRIP);// 绘制前后连接的点组成的线 //glBegin(GL_LINE_LOOP); // 绘制前后连接的点组成的线 , 并且收尾相连 //glBegin(GL_TRIANGLES); // 绘制多个三角形 //glBegin(GL_TRIANGLE_STRIP); // 绘制 GL_TRIANGLE_STRIP 三角形 //glBegin(GL_TRIANGLE_FAN); // 绘制三角形扇 // 绘制多边形 glBegin(GL_POLYGON); // 1. 设置白色 , glVertex3f (GLfloat x, GLfloat y, GLfloat z) glColor4ub(255, 255, 255, 255); glVertex3f(0.0f, 0.0f, -10.0f); // 2. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(-5.0f, 0.0f, -10.0f); // 3. 设置蓝色 glColor4ub(0, 0, 255, 255); glVertex3f(-5.0f, -2.0f, -10.0f); // 4. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(0.0f, -2.0f, -10.0f); // 5. 设置白色 , glVertex3f (GLfloat x, GLfloat y, GLfloat z) glColor4ub(255, 255, 255, 255); glVertex3f(0.0f, 4.0f, -10.0f); // 6. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(-5.0f, 4.0f, -10.0f); // 绘制四边形结束 glEnd(); // 将后缓冲区绘制到前台 SwapBuffers(dc); }
绘制效果 :
二、多边形绘制顺序分析
在 glBegin 和 glEnd 之间设置了 6 6 6 个点 , 分别在图中标号 , 绘制顺序按照 1 → 2 → 3 → 4 → 5 → 6 → 1 1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 1 1→2→3→4→5→6→1 顺序连接起来 , 最终画出了如下多边形 ;
// 绘制多边形 glBegin(GL_POLYGON); // 1. 设置白色 , glVertex3f (GLfloat x, GLfloat y, GLfloat z) glColor4ub(255, 255, 255, 255); glVertex3f(0.0f, 0.0f, -10.0f); // 2. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(-5.0f, 0.0f, -10.0f); // 3. 设置蓝色 glColor4ub(0, 0, 255, 255); glVertex3f(-5.0f, -2.0f, -10.0f); // 4. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(0.0f, -2.0f, -10.0f); // 5. 设置白色 , glVertex3f (GLfloat x, GLfloat y, GLfloat z) glColor4ub(255, 255, 255, 255); glVertex3f(0.0f, 4.0f, -10.0f); // 6. 设置绿色 glColor4ub(0, 255, 0, 255); glVertex3f(-5.0f, 4.0f, -10.0f); // 绘制四边形结束 glEnd();
三、相关资源
GitHub 地址 : https://github.com/han1202012/OpenGL
( GitHub 源码始终都会随着后续博客的进度更新覆盖 , 可能没有本博客的相关源码 , 推荐下载博客源码快照 ) ;博客源码快照 : https://download.csdn.net/download/han1202012/14880720
( 该源码是 Windows 桌面程序 , 使用 Visual Studio 2019 打开 ) -
多边形扩展和收缩(凸多边形和凹多边形)
2020-07-22 17:44:51如下图所示,黑色是原多边形,红色是扩展的多边形,蓝色是收缩的多边形。这是最终的效果。 PS:楼主使用的是ES6的语法,地图是高德地图API 知识积累: 使用的是高中所学的向量的知识和三角公式知识。 向量: 设:a...背景介绍:
如下图所示,黑色是原多边形,红色是扩展的多边形,蓝色是收缩的多边形。这是最终的效果。
PS:楼主使用的是ES6的语法,地图是高德地图API知识积累:
使用的是高中所学的向量的知识和三角公式知识。
对于向量:- 设二维向量:a = (a1, a2); b = (b1, b2);
- 设三维向量:OA = (x1, y1, z1); OB = (x2, y2, z2);
- 向量点乘积:a · b = a1 * b1 + a2 * b2 = |a| |b| cos<a, b>
- 向量单位化:a 单位化后的 na = (a1 / Math.sqrt(a1 * a1 + a2 * a2), a1 / Math.sqrt(a1 * a1 + a2 * a2))
- 向量叉乘积:
二维: a X b = (a1 * b2) - (a2 * b1)
三维:OA X OB = (y1 * z2 - y2 * z1, x2 * z1 - x1 * z2, x1 * y2 - x2 * y1) - 半角公式:
思路点拨:
- 用一个数组paths表示要操作的多边形。其中paths的格式为:[[117.14589,36.659714],[117.145278,36.658952],[117.14626,36.658505],[117.147017,36.659628]]
- 需要将paths的经纬度换成像素坐标。原因:如果使用经纬度和要扩展(收缩)大小做对比会有单位不统一的问题。解决方案:使用map.lnglatToPixel将经纬度换成像素坐标;使用map.pixelToLngLat将像素坐标转换成经纬度坐标。
- 如上图所示,PP1 = (x1 - x, y1 - y); PP2 = (x2 - x, y2 - y); 令vx1 = x1 - x;vy1 = y1 - y;vx2 = x2 - x;vy2 = y2 - y;则 PP1 = (vx1, vy1); PP2 = (vx2, vy2);
- 把PP1 和 PP2 单位化后,就得到了v1 = (vx1 / n1, vy1 / n1) 和 v2 = (vx2 / n2, vy2 / n2)。其中n1 = norm(vx1, vy1);n2 = norm(vx2, vy2)
- PQ = v1 + v2 = (vx1 / n1 + vx2 / n2, vy1 / n1 + vy2 / n2)。设 vx = vx1 / n1 + vx2 / n2;vy = vy1 / n1 + vy2 / n2,则PQ = (vx, vy)。还需要对PQ做单位化,则PQ = (vx / n, vy / n),其中n = norm(vx, vy)。
- 根据向量点乘积的含义,可以得到cos<v1, v2> = (vx1 * vx2 + vy1 * vy2) / (n1 * n2);
- |PQ| = L / sin(<v1, v2> / 2) 经化简可得 L / Math.sqrt(1 - (v1x * v2x + v1y * v2y) / 2)
- 根据上述所说,就可以得到完整的PQ,现在加上P点坐标,就可以得到Q点坐标。
- 处理完成后,记得将像素坐标转成经纬度坐标。
- 在处理凹多边形时,需要使用叉乘积。用来判断是两向量的夹角是凹角还是凸角。
若叉乘积 < 0,向量夹角为 凹角;若叉乘为OP1 X OP2,则 P1 - O - P2 为顺时针。
若叉乘积 > 0,向量夹角为 凸角;若叉乘为OP1 X OP2,则 P1 - O - P2 为逆时针。
若叉乘积 = 0,向量夹角为 平角;若叉乘为OP1 X OP2,则 P1 - O - P2 在一条直线上。
因此在计算PQ 方向的时候,若为凸角, PQ = PP1 + PP2;若为凸角,PQ = P1P + P2P。无论是凸角还是凹角,|PQ| 是 恒定不变的,都为:|PQ| = L / Math.sqrt(1 - (v1x * v2x + v1y * v2y) / 2)
代码区域:
废话不多说,下面是完整代码(ES6),地图使用的是高德地图
/** * 计算多边形的外延 * 算法详情可移步:https://blog.csdn.net/sun_and_breeze/article/details/107517088 去看 * @param {*} map 高德地图map对象 * @param {*} zoom 地图缩放比例 * @param {*} scale 地图比例尺. 高德地图可以通过map.getScale()来获取。含义:表示当前屏幕距离一米代表实际距离多少米 * @param {*} paths 多边形顶点数组。PS:下面代码中是按照多边形顶点逆时针排列的顺序进行处理的,如果你的顶点数组是顺时针,那么是用reverse方法倒过来即可。 * @param {*} extra 外延大小。为正: 向外扩; 为负: 向内缩 * @return 扩展或缩小后的多边形顶点数组 */ export const calcPolygonExtra = (map, zoom, scale, paths, extra) => { if (!zoom) return const norm = (x, y) => Math.sqrt((x * x) + (y * y)) const len = paths.length // 获取实际1m对应像素是多少 const extraPixel = (extra / scale) * getDPI() * 1000 let polygon = [] for (let i = 0; i < len; i++) { const point = map.lnglatToPixel(paths[i], zoom) // P 点 const point1 = map.lnglatToPixel(paths[i === 0 ? len - 1 : i - 1], zoom) // P1 点 const point2 = map.lnglatToPixel(paths[i === len - 1 ? 0 : i + 1], zoom) // P2 点 // 向量PP1 const vectorX1 = point1.x - point.x // 向量PP1 横坐标 const vectorY1 = point1.y - point.y // 向量PP1 纵坐标 const n1 = norm(vectorX1, vectorY1) // 向量的平方根 为了对向量PP1做单位化 let vectorUnitX1 = vectorX1 / n1 // 向量单位化 横坐标 let vectorUnitY1 = vectorY1 / n1 // 向量单位化 纵坐标 // 向量PP2 const vectorX2 = point2.x - point.x // 向量PP2 横坐标 const vectorY2 = point2.y - point.y // 向量PP2 纵坐标 const n2 = norm(vectorX2, vectorY2) // 向量的平方根 为了对向量PP1做单位化 let vectorUnitX2 = vectorX2 / n2 // 向量单位化 横坐标 let vectorUnitY2 = vectorY2 / n2 // 向量单位化 纵坐标 // PQ距离 const vectorLen = -extraPixel / Math.sqrt((1 - ((vectorUnitX1 * vectorUnitX2) + (vectorUnitY1 * vectorUnitY2))) / 2) // 根据向量的叉乘积来判断角是凹角还是凸角 if (((vectorX1 * vectorY2) + (-1 * vectorY1 * vectorX2)) < 0) { vectorUnitX2 *= -1 vectorUnitY2 *= -1 vectorUnitX1 *= -1 vectorUnitY1 *= -1 } // PQ的方向 const vectorX = vectorUnitX1 + vectorUnitX2 const vectorY = vectorUnitY1 + vectorUnitY2 const n = vectorLen / norm(vectorX, vectorY) const vectorUnitX = vectorX * n const vectorUnitY = vectorY * n const polygonX = vectorUnitX + point.x const polygonY = vectorUnitY + point.y const polygonLngLat = map.pixelToLngLat(new window.AMap.Pixel(polygonX, polygonY), zoom) polygon[i] = [polygonLngLat.getLng(), polygonLngLat.getLat()] } return polygon } /** * 获取屏幕DPI的算法。屏幕每一毫米对应多少像素。 */ const getDPI = () => { let dpi if (window.screen.deviceXDPI !== undefined) { dpi = window.screen.deviceXDPI // arrDPI[1] = window.screen.deviceYDPI } else { let tmpNode = document.createElement('DIV') tmpNode.style.cssText = 'width:1mm;position:absolute;left:0px;top:0px;z-index:99;visibility:hidden' document.body.appendChild(tmpNode) dpi = parseInt(tmpNode.offsetWidth, 0) // arrDPI[1] = parseInt(tmpNode.offsetHeight, 0) tmpNode.parentNode.removeChild(tmpNode) } return dpi }
-
地图通过经纬度判断点否在多边形内(多边形在多边形内)
2021-08-13 13:23:47实现方案 先直接上代码,这个方法就是关键的操作(用于js中),用来判断点是否在多边形内,先解释一下里面的变量及其含义 变量名 内容 length 多边形点的数量 lianx 多边形内经度坐标数组 lianx 多边形内纬度坐标...项目需求
在在线地图中判断一个图形是否在另一个图形内,好像很复杂的样子,其实的确有点复杂,我们可以这样想。这个问题其实可以拆分成两步,第一步实现判断点是否在多边形内,第二步判断第一个多边形所有的点是否在第二个多边形内。
实现方案
先直接上代码,这个方法就是关键的操作(用于js中),用来判断点是否在多边形内,先解释一下里面的变量及其含义
变量名 内容 length 多边形点的数量 lianx 多边形内经度坐标数组 lianx 多边形内纬度坐标数组 lianx 点经度坐标 lianx 点纬度坐标 judge(length, lianx, liany, testx, testy) { var i, j, c = false; length = parseInt(length); testx = parseFloat(testx); testy = parseFloat(testy); for (i = 0, j = length - 1; i < length; j = i++) { liany[i] = parseFloat(liany[i]); liany[j] = parseFloat(liany[j]); lianx[i] = parseFloat(lianx[i]); lianx[j] = parseFloat(lianx[j]); if ( (liany[i] > testy) != (liany[j] > testy) && (testx < (lianx[j] - lianx[i]) * (testy - liany[i]) /(liany[j] - liany[i]) + lianx[i]) ) c = !c; } return c; },
如果想知道原理的小伙伴可以接着往下看
这个方法其实每次都是在计算多边形中相邻的两个点和测试点之间是否满足以下两个关系
1.测试点纬度是否在两点纬度之间 (liany[i] > testy) != (liany[j] > testy)
2.如果在两点之间了,接下就得判断待测点test是否在i,j两点之间的连线之下** (testx < (lianx[j] - lianx[i]) * (testy - liany[i]) /(liany[j] - liany[i]) + lianx[i])**
然后每次这两个条件同时满足的时候我们把返回的布尔量取反。可这到底是啥意思啊?
这个表达式的意思是说,随便画个多边形,随便定一个点,然后通过这个点水平划一条射线,先数数看这条
射线和多边形的边相交几次,(或者说先排除那些不相交的边,第一个判断条件),然后再数这条射线穿越多边形的次数是否为奇数,如果是奇数,那么该点在多边形内,如果是偶数,则在多边形外。该部分转载百度百科。将这步完成后,就实现了判断点是否在多边形,而想要实现多边形在多边形内,就按上述所说即可。
如果存在问题请大家批评指正!!!
-
GIS应用技巧之泰森多边形分析
2020-08-13 08:51:23一、什么是泰森多边形? 泰森多边形是由荷兰气候学家A.H.Thiessen提出的一种根据离散分布 的气象站的降雨量来计算平均降雨量的方法,即将所有相邻气象站连成三角 形,作这些三角形各边的垂直平分线,于是每个气象站... -
matlab练习程序(多边形顶点凹凸性)
2021-04-22 01:15:31生成简单多边形后,有时还需要对多边形各顶点的凹凸性做判断。先计算待处理点与相邻点的两个向量,再计算两向量的叉乘,根据求得结果的正负可以判断凹凸性。结果为负则为凹顶点,为正则为凸顶点。凹顶点用o表示,凸... -
[计算机图形学]多边形扫描转换算法
2021-07-27 08:23:50多边形的表示顶点表示。只要得到顶点再连线即可。如果是凸多边形由点集极角排序即可,其他情况不太了解点阵表示。需要判断哪些属于内部点本文主要讨论点阵表示其实主要是PPT的copy,但是复制一遍确实印象深刻一点??1... -
MFC之学习多边形绘制、阴影模式、多边形填充模式与绘制实心五角星
2021-07-25 17:48:361.1绘制多边形函数 BOOL CDC::Polygon(LPPOINT lpPoints,int nCount); lpPoints是多边形顶点数组名,数组中每个点是CPoint对象(或称POINT结构体),nCount是数组中顶点个数。调用成功返回非零,否则返回零。 ... -
[Boost::Polygon]多边形相减得到新的多边形序列
2019-09-25 03:46:51再调用get成员函数就可以获得这一系列多边形进行合并消除覆盖面积的新多边形序列。 如果是polygon_90_set_data还有get_rectangles函数,可以实现获得合并后的矩形划分,在芯片设计 中可以用来求取矩形的OBS... -
直线裁剪 多边形裁剪
2012-12-02 15:32:58图形学实验,用VC++实现直线裁剪和多边形裁剪 -
数学八年级下北师大版4.4相似多边形同步练习2.doc
2021-10-12 13:43:44初高中数学习题 -
计算两个多边形的重叠面积
2020-08-03 16:44:45参数含义: ipc_point_t *a:检测区域的点的集合 ipc_point_t *b:目标物点的集合 int na:检测区域的点的数量 int nb:目标物点的数量 这个接口方法的设计思想: 将检测区域和目标的边框分别拆解成多个三角形,... -
简单多边形与圆相交求面积
2019-12-24 16:32:40简单多边形与圆相交求面积简单多边形的有向面积简单多边形与圆相交的有向面积圆心三角形与圆相交求面积 简单多边形的有向面积 所谓简单多边形,就是指不相邻的边不相交,且每个顶点只跟2条边相邻。一般而言,除非... -
【C++ 程序】 tvj::Polygon类 (多边形类)
2021-01-04 00:08:33代码 Polygon.h /* * Project: ... 本头文件由我的博客 【C++ 程序】 多边形面积周长问题 改写而来。 ALL RIGHTS RESERVED © 2021 Teddy van Jerry 欢迎转载,转载请注明出处。 See also Teddy van Jerry 的导航页 -
Maya多边形建模教程(三)
2021-02-07 02:59:47棱柱体)打开选项窗口,如下图(左)所示,长度和长度大小的参数含义如下图所示。◎length(长度)设置棱柱体y轴向.上的长度,默认值为2。◎Side length (边长)设置几何体x轴向上的长度,相当于改变了几... -
泰森多边形(Voronoi diagram)
2016-02-12 23:06:44泰森多边形(Voronoi diagram) 荷兰气候学家A•H•Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法,即将所有相邻气象站连成三角形,作这些三角形各边的垂直平分线,于是每个气象站周围... -
动态规划:凸多边形最优三角剖分
2020-02-09 21:15:38这是一个凸多边形。对于这个凸多边形,我们可以将弦连接,将其分为多个三角形。 那么问题来了,怎么做才能使这些三角形的权值之和最小呢? 在这里,权值可以是任何和弦长,边长有关的权函数,一般来说,我们使用... -
叠置分析的含义.pptx
2020-06-15 02:25:13从原理上来说叠置分析是对新要素的属性按一定的数学模型进行计算分析其中往往涉及到逻辑交逻辑并逻辑差等的运算根据操作要素的不同叠置分析可以分成点与多边形叠加线与多边形叠加多边形与多边形叠加根据操作形式的... -
opencv学习-物体轮廓(3)-绘制轮廓外接多边形(凸包检测)
2021-07-16 11:39:56参数含义如下: (1)InputArray类型的points,输入二维点集,存储在std::vector或Mat中。 (2)OutputArray类型的hull,输出凸包。它可以是索引的整数向量,也可以是点的向量。 (3)bool类型的clockwise,方向... -
3dsmax 里”编辑网格“与”编辑多边形“的区别
2016-12-30 15:55:19编辑网格(edit mesh):mesh本来是max最基本的多边形加工方法,但在max4之后被更好的一种算法代替了,这个算法就是“编辑多边形edit poly”取代,之后edit mesh的方法逐渐就被遗忘了。(不过mesh最稳定,很多公司... -
流程图基本图形的含义
2022-05-22 07:42:57大家在绘制流程图时,有各种各样的形状,有圆形、菱形、矩形等等,他们都代表什么概念呢? 如果我们画的流程图用错图形,发给别人看,那是一件很尴尬的事。 重要的事说三遍,不要用错图形符号!... -
判断一个坐标点是否在 任意给定边界顶点集的不规则多边形 内部
2019-07-15 16:47:31首先根据已知给定多边形边界顶点集求得其最小x值Xmin、最小y值Ymin、最大x值Xmax和最大y值Ymax,根据这4个值可以确定包含该不规则多边形的水平放置的最小矩形,在此前提下,输入一个任意位置的测试点(x_test,y_test... -
一种通过鼠标操作实现多边形的绘制的实现方法
2014-04-02 00:01:27前面的《MFC基本图形的绘制(三)在SDI中实现绘图操作》对多边形的绘制做了一个简单的介绍。尽管也实现了多边形的绘制,但那种方法有很大的局限性,最主要的就是表现在多边形的顶点(个数和位置)必须固定。通常在实际... -
多边形三角剖分的最低得分--LeetCode1039
2020-05-09 10:14:31多边形三角剖分的最低得分–LeetCode1039 题目 给定 N,想象一个凸 N边多边形,其顶点按顺时针顺序依次标记为 A[0],A[1],...,A[i],...,A[N-1]。假设您将多边形剖分为 N-2个三角形。对于每个三角形,该三角形的值是... -
Svg五角星、太阳花、多边形的绘制
2021-03-01 20:48:50我们在学习平面几何中,学到了多边形的概念,有多少条边就有多少个顶点。本篇我们介绍一下如何用svg来绘制规则的多边形,比如三角形、五角星和任意多边形。在此,我们用到polygon标签,<polygon> 标签用来创建... -
zip的作用_geogebra进阶系列4:映射指令的神奇作用(巧妙提取多边形列表中的顶点)...
2020-11-12 08:45:51现在以大神孙生富老师的做法为例: 第一步,创建整数滑条,范围1-30 第二步,创建多边形列表:l1=序列(多边形((k, k), (-k, k), 4), k, 1, n, 1) 效果如下: 反思1:这个是利用序列+多边形的指令嵌套。多边形的第一... -
多边形的面积导学案
2012-12-13 11:33:57多边形的面积导学案平行四边形、三角形、梯形 -
PNPoly算法代码例子,判断一个点是否在多边形里面
2021-02-25 18:53:50写C语言的实验用到的一个算法,判断一个点是否在多边形的内部。C的代码如下:int pnpoly(int nvert, float *vertx, float *verty, float testx, floattesty){int i, j, c = 0;for (i = 0, j = nvert-1; i < nvert...