企业网站的推广形式有,dw做网站 后台用什么后台,wordpress大站,河北建设厅网站修改密码在哪里OpenGL研究3.0 多边形区域填充 DionysosLai(906391500qq.com)2014-06-22 所谓多边形区域填充。就是将多边形内部区域#xff0c;所有已相同色块填充。注意#xff1a;这里讨论的多边形是简单多边形#xff08;即不考虑诸如五角星这样的相交多边形#xff09;。简单多边形qq.com)2014-06-22 所谓多边形区域填充。就是将多边形内部区域所有已相同色块填充。注意这里讨论的多边形是简单多边形即不考虑诸如五角星这样的相交多边形。简单多边形分为凹多边形和凸多边形。 多边形区域填充有下面几种方法 1. 逐点扫描方法 原理扫描多边形区域逐点推断点是否在多边形内。 难点在于怎样推断点是否在区域内; 经常使用怎样推断点是否在区域内方法射线法、面积法。 面积法原理:取一个点。连接多边形各个点依据三个点形成一个三角形原理我们能够求得三角形面积。推断面积的大小就能够推断该店是否在多边形内了。 射线法这种方法。是我们这里要重点解说的一个方法。原理取一个点。向左或者向右做一条射线过去推断射线与多边形的交点。依据多边形交点熟练和本身多边形边情况推断点是否在多边形内。 首先射线从左向右最左边点肯定在多边形区域为我们这里假定射线方向水平向左。那么与多边形相交第一个点必定表明射线右部分在多变形内与多边形相交第二个点。表明射线右部分在多边形外面。因此。通过推断射线与多变的交点奇偶性。推断点是否在多边形内。 这里。有几种特殊情况例如以下图所看到的 图a射线与多变形顶点相交顶点算一个图b。射线与多边形顶点的交点。不被计算在内注意图a和图b的差别-顶点纵坐标大小差别图c和图d射线与多边形一条边重合这条边被忽略不计。 因此。我们能够设计例如以下取点向左做一条射线1. 对于水平边不做考虑2. 对于多边形顶点与射线交点情况。假设其纵坐标是所属边较大顶点则计数參考图a否则不计数图b。3.对于点在多边形上情况可直接推断点在多边形内。 伪代码例如以下 count ← 0;
以P为端点。作从右向左的射线L;
for 多边形的每条边sdo if P在边s上 then return true;if s不是水平的then if s的一个端点在L上if 该端点是s两端点中纵坐标较大的端点then count ← count1else if s和L相交then count ← count1;
if count mod 2 1 then return true;
else return false;对应代码例如以下注我是在coco2dx2.3版本号内測试的。因此可能移植要改些类名。 ///brief 推断点是否在多边形
///param[in] p0--要推断点 poly--多边形点集合 numberOfPoints--多边形点数量
///return 2---点在多边形内 1---点在多边边上0---点不在多边形内
///author DionysosLai,906391500qq.com
///retval
///post
///version 1.0
///data 2014-04-11
int HelloWorld::pointIsInPolygon(const CCPoint p0, const CCPoint* poly, const unsigned int numberOfPoints)
{unsigned int count 0; /// 用来标记射线L与多边形的交点数CCSize winsize CCDirector::sharedDirector()-getWinSize();/// 已点p0向左向右做一条射线LCCPoint leftPoint ccp(-100.0f, p0.y);CCPoint rightPoint ccp(winsize.width100.0f, p0.y);/// 推断每条边for (unsigned int i 0; i numberOfPoints-1; i){/// 先推断点p0是否在边s上if (pointIsAtLine(p0, poly[i], poly[(i1)%(numberOfPoints)])){CCLOG(Point is at the %dth line, i);return 1;}/// 推断边s是否是平行线if (poly[i].y ! poly[(i1)%(numberOfPoints)].y){ do {/// 推断边s的是否有端点在L上 同一时候 再推断该点是否是边s纵坐标较大的一个点if (pointIsAtLine(poly[i], leftPoint, rightPoint)){if (poly[i].y poly[(i1)%(numberOfPoints)].y){count 1;}break;} if (pointIsAtLine(poly[(i1)%(numberOfPoints)], leftPoint, rightPoint)){if (poly[i].y poly[(i1)%(numberOfPoints)].y){count 1;}break;} /// 假设边s没有端点在L上则推断s与L是否相交if (segmentLineIsIntersect(leftPoint, rightPoint, poly[i], poly[(i1)%(numberOfPoints)])){count 1;} } while (0);}}if (1 count%2){CCLOG(Point is not in polygon!);return 0;}else{CCLOG(Point is in polygon!);return 2;}
} 这里有个pointIsAtLine。是用来推断点是否在边上函数segmentLineIsIntersect。是用来推断两条线段是否相交函数。可參考我的还有一边博文http://blog.csdn.net/dionysos_lai/article/details/24418697计算几何文档一系列文章眼下仅仅写了一篇实际上是几乎相同写了经常使用几何算法还没写成博文。怪楼主太懒了。 Ok逐点扫描推断方法就是差不都这样了。 2. 扫描线算法 逐点扫描算法没有充分考虑到像素之间的连贯性。效率低。扫描线算法。就是要利用像素之间的连贯性提高算法效率。 所谓连贯性有三个概念1.边的连贯性AB边与扫描线1相交也可能与扫描线2相交2.扫描线连贯性当前扫描线与多边形边交点顺序可能与下一条扫描线交点情况一致或者类似3.区间连贯性同一区间像素取同一颜色属性。 扫描线原理将整个多边形区域扫描问题分解到一条条扫描线问题。仅仅要完毕每条扫描线的绘制就实现了多边形区域填充问题。一条扫描线与多边形有偶数个交点0就不算了按顺序每2个点形成一个区间仅仅要绘制这个区间就可以。 难点这与扫描线与多边形边交点推断这个是高中问题了通过线段一般方程axbyc0,两立方程求解。只是这样的方法。要计算各种參数比較费时更好的方法是分成各种情况分开讨论尽管比較麻烦。能够关注我的《计算几何算法》系类文章。 转载于:https://www.cnblogs.com/lytwajue/p/6823287.html
