凹凸多边形 [英] Concave and Convex Polygon

问题描述

如何识别和删除在下面的链接中绘制的四个红色点.
http://pritesharyan.weebly.com/question.html [

How can I identify and remove those four red points drawn in image at below link.
http://pritesharyan.weebly.com/question.html[^]

Those four points make that polygon a concave polygon that’s why I want to remove it.

My goal is to convert concave polygon to convex by removing this kind of point by identifying and removing those points.

IS THERE ANY MATHEMATICAL WAY TO IDENTIFY AND REMOVE THIS KIND OF POINTS?

Thanks.

推荐答案

确定这些要点很简单:

To identify such points is quite simple:

1. 考虑点 P n 和与该点垂直的两个线段；它们是 S 1 = P n - P n-1 和 S 2 = P n + 1 - P n
2. 现在考虑两个段的标量和矢量积:
   
   
   
   • S 1 * S 2 = | S 1 | * | S 2 | * cos( alpha )
   • S 1 ^ S 2 = | S 1 | * | S 2 | * sin( alpha )

1. consider the point Pn and the two segments adiacent to the point; they are S1 = Pn - Pn-1 and S2 = Pn+1 - Pn
2. now consider the scalar and vectorial product of the two segments:
   
   
   
   • S1 * S2 = |S1| * |S2| * cos(alpha)
   • S1 ^ S2 = |S1| * |S2| * sin(alpha)

• S 1 * S 2 =( X 1 - X n-1 )*( X n + 1 - X n )+( Y n - Y n-1 ) *( Y n + 1 - Y n )
• S 1 ^ S 2 =( X n - X n-1 )*( Y n + 1 - Y n )-( Y n - Y n-1 )*( X n + 1 - X n )

• S1 * S2 = (X1 - Xn-1) * (Xn+1 - Xn) + (Yn - Yn-1) * (Yn+1 - Yn)
• S1 ^ S2 = (Xn - Xn-1) * (Yn+1 - Yn) - (Yn - Yn-1) * (Xn+1 - Xn)

alpha = atan2( S 1 ^ S 2 ， S 1 * S 2 )= atan2(sin( alpha )，cos( alpha ))

alpha = atan2(S1 ^ S2, S1 * S2) = atan2(sin(alpha), cos(alpha))

这篇关于凹凸多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！