任意多边形拆分长多个三角形

如题,有什么算法能将一个不规则的任意多边形拆分成多个三角形呢?例如下面这
样的多边形
图片说明

或者下面这样的
图片说明

欢迎各位大神提供思路

4个回答

huangli321456
星辰落 谢谢,虽然后面也找到这个算法了,分还是给你吧
大约一年之前 回复

对于凸多边形,可以选取一个点k,然后从这个点开始顺序取(k+1,k+2)(k+2,k+3)……和点k组成三角形。如果不是凸多边形的话,就看看能不能把它切割成凸多边形。
凸多边形的性质就是外角和为360度或所有内角都小于180度,可以由此判断是否时凸多边形。

数学归纳法证明:一个k边形可以分解为若干个三角形
K=3 显然成立
假设k(k>3)边形都可以分解为k-2个三角形 ,那么对于k+1边形A1A2……AkAk+1,连A1Ak,就把它分成△A1AkA和k边形A1A2……Ak,由归纳假设,k(k>3)边形都可以分解为k-2个三角形,∴k+1边形可以分解为k-2+1=k-1个三角形.
综上,n(n>3)边形都可以分解为n-2个三角形.

分割算法: 耳切法处理多边形三角划分

对于n条边的多边形,随意取一个角点A,则设连接该点的边为S1和S2,两条边端点分别为B、C。连接BC得到S3,判断S3是否在该多边形的内部。如果是,则得到一个三角形和一个新的n-1条边的多边形,对新的多边形进行迭代操作,直到这个多边形为三角形;如果不是,选下一个角点进行迭代操作,直到S3在该多边形的内部。这样就得到了n-2个三角形。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
求代码:拆分长字符串
在网上下了个单词表,形式是一个连续不断的文字序列(长字符串),部分内容如下。rn想拆成每个单词一行,存入一个dbf中,dbf表的三个字段为:单词,音标,汉意 三个rnrn how often[]多久一次 exercise['eks2saiz]v.&n.锻炼;运动 skateboard[]v.踩滑板;参加滑板运动 hardly['ha:dli]adv. 几乎不;几乎没有 ever['ev2]adv. 曾;曾经 shop[60p]v.购物 once[w3ns]adv. 一次rnrn其中的空白都是空格(asc=32). 以上内容拆分后应为: rnrn 单词 音标 汉意rn how often [] 多久一次rn exercise ['eks2saiz]v.&n. 锻炼;运动rn skateboard [] v.踩滑板;参加滑板运动rn hardly ['ha:dli] adv. 几乎不;几乎没有rn ever ['ev2] adv. 曾;曾经 shop[60p]v.购物rn once [w3ns] adv. 一次rnrn请高手出招!
如何将一个任意多边形用三角形来表示?
如果是凸多边形,很容易,如果是凹多边形呢?
求助:任意多边形切分成三角形的算法和代码!
我搜索了下以前的贴子,也有人问过,请各位大侠,有这方面的算法和代码,能否mail给我!rn谢先!rnwongflying@163.com
拆分成多个文件
NULL 博文链接:https://brucefight.iteye.com/blog/783259
在长方形内画多个任意多边形的排序问题。
大家好,有一个指定大小的长方形木板,在这个长方形里面排放各种多边形(三角形、小长方形、扇形等),如何能达到最高的效率,也就是在大长方形内排布满后,浪费掉的面积最小。rnrn这好像是一个古老的算法,小的时候在童话故事中见过,后来在微积分中听过,不知道在计算机中实现是否有经典的算法。rnrn谢谢各位!!!
多个三角形与点的关系 点在多个三角形外部的算法
设平面上有多个三角形,三角形都不相交,可以一个三角形在另一个三角形内部,求在这些三角形外部的点的集合。写出算法
拆分字符串:如果拆多个??
想把这条纪录都拆开:abc*123#def*456#ghi*789rnrn以'#'隔开的是一组 (如:abc*123 )然后'*'是组内的。rnrn就是说先根据'#'把纪录拆开,然后再根据'*'把刚才拆开的再拆一回,这个怎么做?rnrn前辈们帮帮忙!谢谢!
集合拆分为多个集合
package com.stdsoft.wisdomh.util;/** * Created by DELL on 2017/8/23. */ import java.util.*; /** * @author pengXiaoLin * @create 2017-08-23 15:21 **/ public class ListUtil { /** * 拆分集合...
绘制任意多边形
用C#在 vs2005上实现了 绘制任意多边形的一个简单DEMO,将点连线绘制多边形与绘制填充色多边形结合,里面有 单例模式 及 将数组序列化转换为字符串方便数据库存储等 技术点,供初学者参考还是不错的。
填充任意多边形
用鼠标在屏幕上绘制多边形,实现了回显,约束,橡皮筋和引力域技术
任意多边形的面积
利用行列式求任意凸多边形的面积(即叉积): 其中x,y表示该凸多边形顶点的坐标
自动生成任意多边形
我想按下按钮后,计算机就自动在view中生成一个任意多边形,该怎么做呢,怎么样产生顶点,怎么 样存储这些点呢
VB绘制三角形并填充三角形(可用此方法绘制出任意多边形)
我们可以填充Shape控件,可以填充用Line和Circle绘制的矩形和圆形(椭圆,扇形等),但是怎么填充三角形和多边形呢?这是我找到的源码,理解后将注释改成了中文的,用API函数,很短,也很好理解,超实用。
小Y喜欢拆拆拆(送)
Problem Description小Y最喜欢把东西拆开了,虽然一般都无法组装回去(= =b) 在数学中,有一种一定能组装回去的方式是分解质因数,所以小Y最喜欢分解质因数了!但是小Y不是普通人,当然不想按常人的思路“组装”一个数,于是小Y是用以下方法来“组装”: 1. 对于一个数,如果这个数是合数,那么小Y用正常人的方法进行分解质因数,执行操作2,如果这个数不是合数,那么小Y把这个数写下来,结
Java:把list拆分成多个list
一、需求 把一个集合,拆分成多个size一样的集合,做批量插入更新或者删除操作。 二、工具类方法 /** * 把集合拆分成多个集合 */ public class BatchListUtil<E> { /** * 把list分成多个批次 * @param list 集合 * @param batchSize 批次大小 * @ret...
怎样拆分成多个短的字符串????
各位高手:rn 小弟现在有一个难题不能解决,请各位帮帮忙。rn 有一个字符串很长的,想要把它分成多个短的字符串,现在遇上了包含既有汉字又有英文的,若是简单的left,right,mid等的函数去取不行,会造成后面的字符串出现乱码。必须判断所取的字符串是否正确。你有什么办法切断去它呢? rn 例如:str=“造成后面1的字符串出现乱码”,我要分成每句5个汉字的短句,rn得到str1="造成后面1",str2="的字符串出",str3="现乱码"rn 若是简单的用left(str,10)是不行的,它必然会造"的'后的字符串出现乱码?必须要判断去9位还是10位才能正确分开。请问怎样去判断呢?rn 请高手们帮忙写个算法给我好吗?rn 请发个email给我:cholee@21cn.com.rn cholee
手机号码拆分成多个excel文件
可将一个excel里一列的手机号数据拆分成多个Excel文件,主要用于短信推广时,分批次导入手机号
Java中将list拆分成多个,分批操作
近来在开发过程中,碰到查询到一个list数据较大,批量操作时程序报错,后将list拆分,分批处理,记录一下过程。 package com.oigbuy.dsf.dsfUtils; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.util.ArrayList; import java.util....
C# 如何将List拆分成多个子集合?
[b][size=18px]List list = new List();rn for (int i = 1; i < 95; i++)rn rn list.Add(i.ToString());rn rn如何将list拆分成10个子集合?[/size][/b]
EXCEL拆分为多个文档的宏
此宏可以将一个EXCEL文件拆分成多个文件,运行宏后会提示拆分的列号,与标题行数,并将拆分后的文件命名为“列名+当前文件名”。文件中有宏的解说,供大家讨论
工程拆分成多个EXE的布局问题.
我想把一个工程EXE拆成多个模块运行,rn有没有办法让它们打开的时候仍然可以公用同一个MDI父窗体?rn
struts2里面struts.xml如何拆多个文件
struts.xml 放在src里面,我想把它统一放在WEB-INF/config/模块名里面rn如果有哪位高手知道可以麻烦教下吗? [img=https://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/003/onion/25.gif][/img]
java 如何将list拆分成多个list
List ls = new ArrayList ();rnMap m =new HashMap();rnm.put("NAME","ZS");rnm.put("AGE","45");rnm.put("SEX","Y");rnMap m1 =new HashMap();rnm1.put("NAME","LIX");rnm1.put("AGE","12");rnm1.put("SEX","Y");rnMap m2 =new HashMap();rnm2.put("NAME","XF");rnm2.put("AGE","29");rnm2.put("SEX","N");rn....rnls.add(m);rnls.add(m1);rnls.add(m2);rn......rnls.add(mn);rnlist有n个元素。如何根据m的AGE属性,获得多个list,每个list中只存放相同age的map。
excel文件的多个sheet拆分成多个excel文件
Sub SplitWorkBook() '拆分工作簿Dim ws As Worksheet Application.ScreenUpdating = False For Each ws In ThisWorkbook.Worksheets ws.Copy Workbooks(Workbooks.Count).SaveAs ThisWorkbook.Path &amp;amp; &quot;\&quot; &amp;amp; &quot;用你...
unity实现任意多边形三角剖分
项目有一个对任意形状截面生成3维物体的需求,需要用到三角化的算法。如果截面是凸多边形,那么非常简单,以任意一点为起点按顺序切分即可: /// <summary> /// 局限性三角剖分 /// </summary> /// <returns></returns> public static int[] LimitedTriangleI
C++实现——任意多边形的面积
//求任意多边形的面积 /*语法:result = polygonarea(vector<Point>&polygon, int N); 参数: polygon:多变形顶点数组 N:多边形顶点数目 返回值:多边形面积 注意: 支持任意多边形,凹、凸皆可 多边形顶点输入时按顺时针顺序排列*/ typedef struct Point{ double x, y; Point(){} }
任意多边形渐变色填充
vb画任意多边形、封闭多边形,并在其中填充渐变色,比如:画实心箭头,就可以用上了。
任意多边形的最大内切圆算法
网上找内切圆算法没找到理想的,在国外看到一篇文章,作者本人也有源码,编译没通过,自己重新写了下,实现了功能。 一 算法思想在这里插入代码片 上图中在三角形形成的二维平面区域中,高度为H,宽度为W。将空间进行等分,高度为n份,宽度为m份,每份为H/n,W/m份 在空间形成网格,将三角区域外的点剔除掉。再剩下的点中,对每个点而言,找出到边最近的距离。这样在很多点中找出最大的距离...
请教:任意多边形的面积
用任意条直线段联接成一闭合多边形(凹凸),怎么计算其面积?最好算法不要太复杂,因为考虑到执行效率的问题。
凸包法求任意多边形的面积
自己编的,用凸包算多边形的面积,输入由文件输入
实现任意多边形的最小外接圆
本功能实现任意多边形的最小外接圆,先实现任意多边形的绘制,在通过一个菜单实现绘制这个多边形的最小外接圆。
MFC画任意多边形?
从一个对话框得到边数
求任意多边形的面积
原理就是将每两个点组成一个梯形,利用梯形公式(上底+下底)*高/2,两两相加直到起点, 其中,ΔABC顶点A、B、C逆时针给出时有向面积为正,顺时针给出时有向面积为负。 如有(X1,Y1)(X2,Y2)(X3,Y3)(X1,Y1) 公式:(Y1+Y2)*(X2-X1)/2+(Y2+Y3)*(X3-X2)/2+(Y3+Y1)*(X1-X3)/2 以此类推就可以算出任意不规则图形的面积了 对于有...
cocos2d-x任意多边形渲染
cocos2d-x任意多边形渲染 当然我已经很久没有做cocos2d-x的东西了 不是很熟悉了哈 不会用不要找我
mfc 任意多边形填充色
基于mfc的自己绘制任意多边形后填充颜色,主要指用种子填充算法,及预扫描处理。
任意多边形求交算法?
[size=16px][/size]怎么求任意 多边形的交的区域的顶点集合 啊?rn用gdi的Crgn类的intersection只能求一个Crgn,怎么抽取出顶点顺序集合。。rn或者用其它的方法快速的算出来,不用太底层,能实现即可
opengl画任意多边形的棱柱
我的问题是:在opengl中如何产生一个任意多边形的棱柱。rn 我现在的想法是:先产生一个任意多边形(二维),通过给它一定厚度,使它变成一个棱柱,并能实现旋转。目前只能产生二维图形,不知怎样加厚度使它变成棱柱。rn 是否有更好的办法来产生任意多边形的棱柱。rn 多谢!rn
任意多边形的求解c语言
杭电2037题 #include int main(void) { int n,i;//n个坐标 double sum;//面积 int site[150][2];//每个坐标 while(scanf("%d",&n)!=EOF)//获得输入 { if(n==0) break;//0时跳出 for(
任意多边形的面积计算
任意给出一个三角形ΔABC,设其顶点坐标分别为A(x1, y1),B(x2, y2),C(x3, y3),那么根据线性代数的知识,ΔABC的有向面积可表示为: 其中,ΔABC顶点A、B、C逆时针给出时有向面积为正,顺时针给出时有向面积为负。如图1所示,.S∆ABC>0、S∆ABD 图1 我们知道任意的多边形都可以分割成多个三角形,根据以上三角形面积公式就可以求出任意多边形的面
任意多边形填充FillPoly
任意多边形填充,可以看看。自己用的话,还是动手的改的
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池

相似问题

1
jcanvas如何控制不规则多边形在canvas大小范围内移动
2
如何计算一个多边形与哪些网格相交
1
用C语言实现多边形顶点计算的一个问题,具体看下面
1
小白求助,Python怎么提取二值图中的矩形和多边形顶点坐标呢?
1
arcgis engine 绘制多边形outline设置width属性时是否可以让宽度不要超过多边形边缘(向内增宽)?
0
计算多边形有多少个面的问题,怎么利用C程序的代码的编写来实现呢
4
C 语言 检测点是否在凸边行内侧,学校算法作业一部分 检测是否是凸边行
1
求助完整代码,,,求助图形学大佬
1
求编程设计思路及代码
0
运用数据结构建立多边形的联通的算法,怎么采用C程序的代码的编写的步骤才能实现?
2
怎么用labelme标记虹膜
1
请问怎么用VS来绘制三次B样条曲线?
1
如何在高德地图上根据画好的线,在他周边200米范围内画出多边行,这条线是随意长度,可以拐外的
0
多边形的切割的问题,怎么使用C语言的程序编写代码的形式方法去解决呢,具体代码编写
0
多边形的顶点的构建问题,是如何采用C语言的程序设计的思想方法加以有效实现的呢
0
面积大者在前面输出。(输出部分要四舍五入到整数),这个问题具体用C语言的实现做法
0
百度地图构建多边形交叉问题。
3
“=”作为左操作数,这个报错怎么解决?
0
输出二维平面凸多边形的问题,使用C程序的代码设计的方式和步骤来计算的实现的思路