手机网站制作免费,网页前端开发技术,上海网站建设在哪里,wordpress上传网站简单多边形三角化(暴力) 说在前面 网上流传着各种神奇的多边形三角剖分算法#xff0c;但是讲道理#xff0c;实现难度太高了。。。也没有搜到其他人的实现。这里写个最暴力的做法。。随机数据验证没问题#xff0c;欢迎 hack 实现 一个简单多边形的耳朵定义为#xff1a;如… 简单多边形三角化(暴力) 说在前面 网上流传着各种神奇的多边形三角剖分算法但是讲道理实现难度太高了。。。也没有搜到其他人的实现。这里写个最暴力的做法。。随机数据验证没问题欢迎 hack 实现 一个简单多边形的耳朵定义为如果一个凸点与他相邻的点构成的三角形内没有其他多边形的点那么他是一个耳朵。 我们的思想很简单每次切掉一个耳朵直到多边形变为一个三角形。 核心代码 typedef vectorvectorP VPP;
VPP divPtoT(vectorP ps){ // O(n^3) 简单多边形三角剖分 多边形逆时针VPP T; T.clear();if(ps.size()3) return T;listint L;rep(i, 0, ps.size()-1) L.pb(i);auto ck [](P A, P B, P C) {if( crossOp(B,C,A) 0 ) return false;for(int p: L) {if( ps[p] A || ps[p] B || ps[p] C ) continue;if( crossOp(A,B,ps[p])0crossOp(B,C,ps[p])0crossOp(C,A,ps[p])0 ) return false;}return true;};P A,B,C;while(L.size() 3) {auto it L.begin();A ps[*it]; it; B ps[*it]; --it; C ps[*--L.end()];if(ck(A,B,C)) { L.erase(it); T.pb({A,B,C}); continue; }auto ed --L.end();B ps[*ed]; -- ed; A ps[*ed]; ed; C ps[*L.begin()];if(ck(A,B,C)) { L.erase(ed); T.pb({A,B,C}); continue; }it L.begin();for( ; it ! ed; it) {B ps[*it]; --it; A ps[*it]; it; it; C ps[*it]; --it;if(ck(A,B,C)) { L.erase(it); T.pb({A,B,C}); break; }}}if(L.size() 3) {vectorP tmp; for(auto it L.begin(); it ! L.end(); it) tmp.pb(ps[*it]);T.pb(tmp);}return T;
} 实验 使用 cyaron 生成简单多边形用三角剖分求面积与实际多边形面积比较判断。 样例 生成 转载于:https://www.cnblogs.com/RRRR-wys/p/11430147.html
