C#多边形求角——实例说
前段时间有写过一个计算多边形角度的代码，这里给它整理整理，留给自己也送给萌新。
看左下图，这是一个多环的多边形，一个外环（内部为多边形内部区域），一个内环（外部为多边形内部区域），同时多边形中任意一个角不等于零角（等于 0° 的角）或周角（等于 360° 的角）。注意：本文下文所讨论的多边形求角度不包含零角和周角。
现在我们要求 ∠abc 和 ∠def 的大小。那咋算唻?
1. 内积计算夹角
给它加上坐标系（坐标是自己配的，计算出的角度值不一定准确，但不影响角度大小的关系）， 如右上图。角度采用向量的内积来求。
以上面的 ∠abc 为例，数学计算公式如下。
于是乎，有：
角度计算代码如下：
public struct cxpoint
{
public cxpoint(double x, double y)
{
x = x;
y = y;
}
public double x;
public double y;
}
/// <summary>
/// 计算三点角度，p1-p2-p3为沿环方向的三个连续顶点，其中p2为角点。计算结果范围 0° - 180°，-1为无效值
/// </summary>
private static double calculationangle(cxpoint p1, cxpoint p2, cxpoint p3)
{
//cos(angle) = a•b/(|a|*|b|)
double x1 = p1.x - p2.x, y1 = p1.y - p2.y; //向量 a
double x2 = p3.x - p2.x, y2 = p3.y - p2.y; //向量 b
//零向量，存在共点
if (x1 == 0 && y1 == 0) return -1;
if (x2 == 0 && y2 == 0) return -1;
double v = x1 * x2 + y1 * y2; //向量内积 a•b
double val = math.sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2)); //a,b模长乘积 |a|*|b|
double cosangle = v / val; //求出来的值可能略小于 -1 或者略大于 1，此时 angle 等于 nan
double angle = math.acos(cosangle) * 180.0 / 3.14159265358979; //两向量夹角，0-180
if (system.double.isnan(angle))
{
if (v > 0) return 0;
else return 180;
}
else
{
if (angle > 180) return 180;
else if (angle < 0) return 0;
else return angle;
}
}
用上述代码我们能够计算得出 ∠abc = 124.63°，∠def = 101.57°。细心的朋友会发现，∠def 很明显是个优角（大于 180° 小于 360° 的角），为什么求出来是个劣角的值（大于 0° 小于 180° 的角）呢？原来反余弦函数的值域为 [ 0，π ]，故采用向量内积计算出来的夹角总是在 [ 0°，180° ] 之间。
2. 外积判断互组
针对像 ∠def 这种优角，我们如何计算其结果呢？原来，内积计算的夹角与正确结果必定互为组角（相加等于 360° 的两个角互为组角），如此 ∠def 的正确结果为 360° - 101.57° = 258.43°。故在内积计算夹角后，问题转换为判别待求角是优角还是劣角，优角则求其组角，劣角则直接是结果。
以 ∠abc 为例 ，a → b → c 为环方向，取ac中点m，再取 bm 上靠近 b 点的 b' 点（称为面内面外判断点），其中 bb' 的距离很小很小（若直接以 m 点作为面内面外判断点，由于存在多环的情况，会出现问题）。若 b' 在多边形内，则待求角为劣角，内积计算夹角即为结果，若 b' 在多边形外，即出现 ∠def 这种情况（此时 b' 是 e'）,则需要求内积计算夹角的组角作为计算结果。
面内面外判断点求取代码如下：
/// <summary>
/// 求取面内面外判断点，p1-p2-p3为沿环方向的三个连续顶点，其中p2为角点。
/// </summary>
private static cxpoint calculationjudgepoint(cxpoint p1, cxpoint p2, cxpoint p3, double smalldis = 0.01)
{
double tempx = (p1.x + p3.x) / 2;
double tempy = (p1.y + p3.y) / 2;
double disx = tempx - p2.x;
double disy = tempy - p2.y;
double val = math.sqrt(disx * disx + disy * disy);
double scale = smalldis / val;
return new cxpoint(p2.x + scale * disx, p2.y + scale * disy);
}
假设，沿着环的方向，多边形的内部总在环的右侧区域，所以在上图中，∠abc 所在的环为顺时针方向，∠def 所在的环为逆时针方向。有了这个假设，我们就能够用向量外积来判断 b' （或者是 e'）点是否在面内了。具体做法为计算 ( 待求角角点，沿环方向角点下一顶点 ) 与 ( 待求角角点，面内面外判断点 ) 的外积（在本文图中为和
）：结果若大于 0，则面内面外判断点在环的左侧和多边形外部，待求角为优角，求内积计算夹角的组角作为结果；结果若小于等于 0，则面内面外判断点在环的右侧和多边形内部或边界上，待求角为劣角或平角，内积计算夹角直接作为结果。
以判断 b' 在 bc 的哪一侧为例，数学计算公式如下。
左右侧判断代码如下：
public struct cxline
{
public cxline(cxpoint frompoint, cxpoint topoint)
{
frompoint = frompoint;
topoint = topoint;
}
public cxpoint frompoint;
public cxpoint topoint;
}
/// <summary>
/// 判断点在线的左方还是右方，在左为 true，在线上或在右为 false
/// </summary>
public static bool judgabout(cxline pline, cxpoint ppoint)
{
double ax = pline.topoint.x - pline.frompoint.x;
double ay = pline.topoint.y - pline.frompoint.y;
double bx = ppoint.x - pline.frompoint.x;
double by = ppoint.y - pline.frompoint.y;
double judge = ax * by - ay * bx;
if (judge > 0.0)
return true;
else
return false;
}
3. 求角源码整理
通过上述分析，将所有代码整理成一个 cs 类。
/// <summary>
/// 调用示例：anglecalculation.cxpoint p1 = new anglecalculation.cxpoint(-112, -12);
/// anglecalculation.cxpoint p2 = new anglecalculation.cxpoint(-68, -51);
/// anglecalculation.cxpoint p3 = new anglecalculation.cxpoint(0, 0);
/// double angle = anglecalculation.analysis(p1, p2, p3, true);
/// </summary>
public sealed class anglecalculation
{
public struct cxpoint
{
public cxpoint(double x, double y)
{
x = x;
y = y;
}
public double x;
public double y;
}
public struct cxline
{
public cxline(cxpoint frompoint, cxpoint topoint)
{
frompoint = frompoint;
topoint = topoint;
}
public cxpoint frompoint;
public cxpoint topoint;
}
/// <summary>
/// 角度计算主方法，p1-p2-p3为沿环方向的三个连续顶点，其中p2为角点。
/// </summary>
/// <param name="isclockwise">p1-p2-p3所在环方向，顺时针为 true，逆时针为 false</param>
public static double analysis(cxpoint p1, cxpoint p2, cxpoint p3, bool isclockwise)
{
double angle = calculationangle(p1, p2, p3);
if (angle == -1) return angle;
cxpoint judgepoint = calculationjudgepoint(p1, p2, p3);
cxline referenceline = new cxline(p2, p3);
bool isleft = judgabout(referenceline, judgepoint);
if (isclockwise == isleft) angle = 360 - angle;
return angle;
}
/// <summary>
/// 计算三点角度，p1-p2-p3为沿环方向的三个连续顶点，其中p2为角点。计算结果范围 0° - 180°，-1为无效值
/// </summary>
private static double calculationangle(cxpoint p1, cxpoint p2, cxpoint p3)
{
//cos(angle) = a•b/(|a|*|b|)
double x1 = p1.x - p2.x, y1 = p1.y - p2.y; //向量 a
double x2 = p3.x - p2.x, y2 = p3.y - p2.y; //向量 b
//零向量，存在共点
if (x1 == 0 && y1 == 0) return -1;
if (x2 == 0 && y2 == 0) return -1;
double v = x1 * x2 + y1 * y2; //向量内积 a•b
double val = math.sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2)); //a,b模长乘积 |a|*|b|
double cosangle = v / val; //求出来的值可能略小于 -1 或者略大于 1，此时 angle 等于 nan
double angle = math.acos(cosangle) * 180.0 / 3.14159265358979; //两向量夹角，0-180
if (system.double.isnan(angle))
{
if (v > 0) return 0;
else return 180;
}
else
{
if (angle > 180) return 180;
else if (angle < 0) return 0;
else return angle;
}
}
/// <summary>
/// 求取面内面外判断点，p1-p2-p3为沿环方向的三个连续顶点，其中p2为角点。
/// </summary>
private static cxpoint calculationjudgepoint(cxpoint p1, cxpoint p2, cxpoint p3, double smalldis = 0.01)
{
double tempx = (p1.x + p3.x) / 2;
double tempy = (p1.y + p3.y) / 2;
double disx = tempx - p2.x;
double disy = tempy - p2.y;
double val = math.sqrt(disx * disx + disy * disy);
double scale = smalldis / val;
return new cxpoint(p2.x + scale * disx, p2.y + scale * disy);
}
/// <summary>
/// 判断点在线的左方还是右方，在左为 true，在线上或在右为 false
/// </summary>
private static bool judgabout(cxline pline, cxpoint ppoint)
{
double ax = pline.topoint.x - pline.frompoint.x;
double ay = pline.topoint.y - pline.frompoint.y;
double bx = ppoint.x - pline.frompoint.x;
double by = ppoint.y - pline.frompoint.y;
double judge = ax * by - ay * bx;
if (judge > 0.0)
return true;
else
return false;
}
}
}
|
作者： 出处： 本文为作者原创，版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接，否则保留追究法律责任的权利。如本文有误，欢迎批评指正。 |