2025年顶角判别法识别多边形的凸凹性，并将凹多边形近似处理为凸多边形

科技前沿 • 2025-02-23 18:48 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

点一定显凸性;然后，以该凸顶点为支点顺时针方向旋转后一个顶点到支点与前一个顶点的射线上，若旋转角度小于7T，则记为“+”号，大于7T则记为“一”号;遍历

其他顶点，以该顶点为支点顺时针方向旋转后一个顶点到支点与前一个顶点的射线上，旋转的角度小于7T则记为“+”号，大于7T则记为“一”号(凸凹点的判断);最后，

如果该点和顶点的符号相同则为凸点，否则为凹点。

效果图：

讯享网

处理后：

代码实现：

/ 
  
    
   
   顶点判决法，并将凹多边形近似处理为凸多边形 */ void MyPainterWidget::apexAngle(){ //1.找顶角 int maxIndex = 0 ; int maxY = points[0].y(); int maxX; for(int i = 1;i &lt; points.size();i++){ if(points[i].y() &lt; maxY){ maxY = points[i].y(); maxX = points[i].x(); maxIndex = i; }else if(points[i].y() == maxY){ //y值相同 if(points[i].x() &gt; maxX){ maxX = points[i].x(); maxIndex = i; } } } 
  
 // qDebug()&lt;&lt;“maxIndex:”&lt;&lt;maxIndex; //2.1 找到顶角后，判断是否是凹点如果是，则移除 // 逐次的往后求sin sin &lt; 0 ：凸点：凹点； preIndex = maxIndex; for(int i = maxIndex + 1;i + 1 &lt; points.size() && i - 1 &gt;= 0;i++){ 讯享网 filter(preIndex,i,i &#43; 1); 
 } if(points.size() &gt; 2){  //2.2 求最后一个角 filter(preIndex,points.size() - 1,0); //2.3求第0个角 filter(preIndex,0,1); 
 } //2.4 找出顶角前面的凹点 for(int i = 1;i &lt; maxIndex + 1;i++){ 讯享网 filter(preIndex,i,i&#43;1); 
 } } / 
  
    
   
   @brief MyPainterWidget::filter 
   @param pre 前一个凸点 
   @param cur 当前点 
   @param next 下一个点 
   记录最新凸点，剔除凹点 */ void MyPainterWidget::filter(int pre,int cur,int next){ if(!isBump(&points[pre],&points[cur],&points[next])){ //更新前面最新的一个凸点 preIndex = cur; }else{ //从容器中移除当前凹点 points.erase(points.begin() + cur); qDebug()&lt;&lt;“delete:”&lt;&lt; cur; } } 
  
 //三个点组成的夹角，判断该点是否是凸点 bool MyPainterWidget::isBump(QPoint *p1,QPoint *p2,QPoint *p3){ int sin &#61; ((p1-&gt;x() - p2-&gt;x())*(p3-&gt;y() - p2-&gt;y()) - (p3-&gt;x() - p2-&gt;x())*(p1-&gt;y() - p2-&gt;y())); return sin &lt; 0; 
 }

讯享网

完整工程下载地址：http://download.csdn.net/detail/buqulinghun/

参考论文：平面多边形凹凸性的顶角判别法，万书亭，韩庆瑶

2025年顶角判别法识别多边形的凸凹性，并将凹多边形近似处理为凸多边形

相关推荐