鸟语天空

计算几何

作者：追风剑情 发布于：2018-1-7 14:16 分类：Algorithms

示例代码

using System;
using System.Collections.Generic;

namespace Geometry
{
    /// <summary>
    /// 计算几何类
    /// 封装了计算几何的基本算法:
    /// 点与矩形的关系、点与圆的关系、点与直线的关系、直线与直线的关系、点与多边形的关系
    /// </summary>
    public class ComputationGeometry
    {
        public static double Epsilon = 0.00000001;//1E-8精度

        // 判断一个点是否在矩形内
        public static bool IsPointInRect(Point p, Rect rc)
        {
            double xr = (p.x - rc.p1.x) * (p.x - rc.p2.x);
            double yr = (p.y - rc.p1.y) * (p.y - rc.p2.y);
            return (xr <= 0.0) && (yr <= 0.0);
        }

        // 判断两个矩形是否相交
        public static bool IsRectIntersect(Rect rc1, Rect rc2)
        {
            return (Math.Max(rc1.p1.x, rc1.p2.x) >= Math.Min(rc2.p1.x, rc2.p2.x))
                && (Math.Max(rc2.p1.x, rc2.p2.x) >= Math.Min(rc1.p1.x, rc1.p2.x))
                && (Math.Max(rc1.p1.y, rc1.p2.y) >= Math.Min(rc2.p1.y, rc2.p2.y))
                && (Math.Max(rc2.p1.y, rc2.p2.y) >= Math.Min(rc1.p1.y, rc1.p2.y));
        }

        // 判断一个点是否在圆内
        public static bool IsPointInCircle(Point p, Point o, double r)
        {
            double d = PointDistance(p, o);
            return d <= r;
        }

        // 判断一个点是否在线段上
        public static bool IsPointOnLineSegment(Point p, LineSegment ls)
        {
            Rect rc = GetLineSegmentRect(ls);
            //如果线段所表示的矢量和点的矢量的叉积是0,就说明点在线段所在的直线上
            double cp = CrossProduct(ls.pe.x - ls.ps.x, ls.pe.y - ls.ps.y,
                                     p.x - ls.ps.x, p.y - ls.ps.y);
            return IsPointInRect(p, rc) //排除实验
                && IsZeroFloatValue(cp);//1E-8精度
        }

        // 判断两条线段的包围盒是否排斥 true:不相交
        private static bool IsLineSegmentExclusive(LineSegment ls1, LineSegment ls2)
        {
            Rect rc1 = GetLineSegmentRect(ls1);
            Rect rc2 = GetLineSegmentRect(ls2);
            return !IsRectIntersect(rc1, rc2);
        }

        // 判断两条线段是否相交
        public static bool IsLineSegmentIntersect(LineSegment ls1, LineSegment ls2)
        {
            //排斥实验
            if (IsLineSegmentExclusive(ls1, ls2)) {
                return false;
            }

            //(P1 - Q1)×(Q2 - Q1)
            double p1xq = CrossProduct(ls1.ps.x - ls2.ps.x, ls1.ps.y - ls2.ps.y,
                                       ls2.pe.x - ls2.ps.x, ls2.pe.y - ls2.ps.y);
            //(P2 - Q1)×(Q2 - Q1)
            double p2xq = CrossProduct(ls1.pe.x - ls2.ps.x, ls1.pe.y - ls2.ps.y,
                                       ls2.pe.x - ls2.ps.x, ls2.pe.y - ls2.ps.y);
            //(Q1 - P1)×(P2 - P1)
            double q1xp = CrossProduct(ls2.ps.x - ls1.ps.x, ls2.ps.y - ls1.ps.y,
                                       ls1.pe.x - ls1.ps.x, ls1.pe.y - ls1.ps.y);
            //(Q2 - P1)×(P2 - P1)
            double q2xp = CrossProduct(ls2.pe.x - ls1.ps.x, ls2.pe.y - ls1.ps.y,
                                       ls1.pe.x - ls1.ps.x, ls1.pe.y - ls1.ps.y);
            //跨立实验
            return (p1xq * p2xq <= 0.0) && (q1xp * q2xp <= 0.0);
        }

        // 获取线段的矩形包围盒
        public static Rect GetLineSegmentRect(LineSegment ls)
        {
            Rect rc = new Rect();
            rc.p1 = ls.ps;
            rc.p2 = ls.pe;
            return rc;
        }

        /// <summary>
        /// 判断点是否在多边形内
        /// </summary>
        /// <param name="polygon">边数组</param>
        /// <returns></returns>
        public static bool IsPointInPolygon(Point p, Polygon polygon)
        {
            if (!polygon.IsValid())
                throw new ArgumentException("无效多边形");

            int count = 0;//记录射线与多边形的交点个数
            //创建一条从P点出发向左的最大线段P1P2
            LineSegment ll = new LineSegment();
            ll.ps = p;
            ll.pe = new Point(-1000, p.y);//这里的x值应该根据多边形的包围盒计算得到
            LineSegment edge;
            for (int i = 0; i < polygon.edges.Count; i++ )
            {
                edge = polygon.edges[i];
                if (IsPointOnLineSegment(p, edge)) {
                    return true;
                }

                //如果edge与P1P2平行，则忽略这条边,
                //如果平行,要么交点为0个，要么有无数个。
                if (edge.IsHorizontal())
                    continue;

                //当P1P2与多边形的顶点相交时,此时交点会被计算两次
                //这种情况的处理原则是:
                //如果P的y坐标与P1、P2中较小的y坐标相同,则忽略这个交点。
                if (IsSameFloatValue(edge.ps.y, p.y) && edge.ps.y > edge.pe.y)
                {
                    count++;
                }
                else if (IsSameFloatValue(edge.pe.y, p.y) && edge.pe.y > edge.ps.y)
                {
                    count++;
                }
                else
                {
                    if (IsLineSegmentIntersect(edge, ll))
                    {
                        count++;
                    }
                }
            }
            return (count % 2) == 1;//交点个数为奇数时表示点在多边形内
        }

        // 计算两点间距离
        private static double PointDistance(Point p1, Point p2)
        {
            return Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
        }

        // 计算三角形面积
        public static double CalculateTriangleArea(Triangle triangle)
        {
            return CalculateTriangleArea(triangle.p0, triangle.p1, triangle.p2);
        }

        public static double CalculateTriangleArea(Point p0, Point p1, Point p2)
        {
            Vector2 v01 = Vector2.Create(p0, p1);
            Vector2 v02 = Vector2.Create(p0, p2);
            double s = CrossProduct(v01.x, v01.y, v02.x, v02.y) / 2;
            return s;
        }

        // 判断一个点是否在三角形内
        public static bool IsPointInTriangle(Point p, Triangle triangle)
        {
            double s012 = CalculateTriangleArea(triangle);
            double s01p = CalculateTriangleArea(triangle.p0, triangle.p1, p);
            double s02p = CalculateTriangleArea(triangle.p0, triangle.p2, p);
            double s12p = CalculateTriangleArea(triangle.p1, triangle.p2, p);
            return s01p + s02p + s12p <= s012;
        }

        // 是否近似0
        private static bool IsZeroFloatValue(double d)
        {
            return d > -Epsilon && d < Epsilon;
        }

        // 是否相等
        private static bool IsSameFloatValue(double d1, double d2)
        {
            return Math.Abs(d1 - d2) < Epsilon;
        }

        /**
         * 点积(内积)
         * (P, Q)表示向量P和Q的夹角。
         * 
         * 如果P和Q不共线,则:
         * P·Q > 0，则P和Q的夹角是钝角(大于90度)
         * P·Q < 0，则P和Q的夹角是锐角(小于90度)
         * P·Q = 0，则P和Q的夹角是90度
         */
        private static double DotProduct(double x1, double y1, double x2, double y2)
        {
            return x1 * x2 + y1 * y2;
        }

        /**
         * 叉积(外积)
         * P×Q = -(Q×P)
         * 
         * 几何意义:
         * P×Q为所构成的平行四边行的面积。
         * 
         * 方向:
         * P×Q的方向是垂直于P和Q所在的平面(右手坐标系)
         * 
         * 性质:
         * 判断两矢量相互之间的位置关系
         * P×Q > 0，则Q在P的逆时针方向
         * P×Q < 0，则Q在P的顺时针方向
         * P×Q = 0，则Q与P共线
         */
        private static double CrossProduct(double x1, double y1, double x2, double y2)
        {
            return x1 * y2 - x2 * y1;
        }
    }

    public class Point
    {
        public double x;
        public double y;

        public Point(double x, double y)
        {
            this.x = x;
            this.y = y;
        }
    }

    public class Vector2
    {
        public double x;
        public double y;

        public static Vector2 Create(Point p0, Point p1)
        {
            Vector2 v = new Vector2();
            v.x = p1.x - p0.x;
            v.y = p1.y - p0.y;
            return v;
        }
    }

    public class Rect
    {
        public Point p1;
        public Point p2;
    }

    public class Triangle
    {
        public Point p0;
        public Point p1;
        public Point p2;
    }

    public class LineSegment
    {
        public Point ps;
        public Point pe;

        //是否为水平线段
        public bool IsHorizontal()
        {
            return Math.Abs(pe.y - ps.y) < 0.00000001;
        }
    }

    public class Polygon
    {
        public List<LineSegment> edges;

        // 判断是否为合法的多边形
        public bool IsValid()
        {
            return true;
        }
    }
}

标签: Algorithms