欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

各种多边形算法

程序员文章站 2022-03-13 14:50:53
...
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" />
    <script src="/scripts/mathematicsAndPhysics/linearAlgebra/matrix/gl-matrix/2.7.1/dist/gl-matrix.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/geometry/shape-points/2.0.1/shapPoints.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/bezierCurve/jsbezier/0.9.3/jsbezier.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/bezierCurve/bezierjs/2.2.15/bezierjs.js"></script>
    <title></title>
    <style>
        #canvas {
            border: 1px solid #000;
        }
    </style>
</head>
<body>
    <canvas id="canvas">

    </canvas>
        
    <script>
        var canvas = document.getElementById('canvas')
        canvas.width = 1000;
        canvas.height = 1000;
        var ctx = canvas.getContext('2d');
       
       

        // 创建一个
        var rotate = 20 / 180 * Math.PI;
        var rectSize=vec2.fromValues(100,100)
        var rectPosition = vec2.fromValues(100, 100);
        var rectRotatePosition = vec2.rotate(vec2.create(), rectPosition, [0, 0], rotate)

        // 创建一个矩阵
        var m = mat2d.create();
        m = mat2d.translate(mat2d.create(), m, [100, 100]);// 位移
        m = mat2d.scale(mat2d.create(), m, [1, 1]);// 缩放
        m = mat2d.rotate(mat2d.create(), m, rotate);// 旋转20

        var m2=mat2d.multiply(mat2d.create(),mat2d.create(),[2,0,0,2,100,100])
        // 创建一个矩形
        ctx.fillStyle = 'red';
        ctx.setTransform.apply(ctx, m)
        ctx.fillRect(rectPosition[0], rectPosition[1], rectSize[0], rectSize[1]);

   //    ctx.setTransform.apply(ctx, mat2d.create())
        // 创建一个圆
        ctx.beginPath();

        ctx.arc(400, 100, 50, 0, Math.PI * 2);
        ctx.fill();

        function drawPoints(points,fill) {
            ctx.moveTo(points[0], points[1])
            for (var i = 2; i < points.length; i += 2) {
                ctx.lineTo(points[i], points[i + 1])
            }
            if (fill) {
                ctx.fill();
                return;
            }
            ctx.stroke()
        }

        //创建一个三次贝塞尔图形
        var heartPoints = [];
        function heart() {
            var ops = {
                x: 100,
                y: 50,
                width: 30,
                height: 30
            }, x = ops.x, y = ops.y, w = ops.width, h = ops.height;
            ctx.beginPath();
            ctx.moveTo(x, y);

            heartPoints.push([{
                x: x,
                y:y
            }, {
                x: x + w / 2,
                y: y - h * 2 / 3
            }, {
                x: x + w * 2,
                y: y + h / 3

            }, {
                x: x,
                y:y+h
            }])
            heartPoints.push([{
                x: x,
                y: y+h
            }, {
                x: x - w * 2,
                y: y + h / 3
            }, {
                x: x - w / 2,
                y: y - h * 2 / 3

            }, {
                x: x,
                y: y
            }])
            ctx.bezierCurveTo(
              x + w / 2, y - h * 2 / 3,
              x + w * 2, y + h / 3,
              x, y + h
          );
            ctx.bezierCurveTo(
                x - w * 2, y + h / 3,
                x - w / 2, y - h * 2 / 3,
                x, y
            );

            window.isCurve = function (x2, y2) {
                ctx.beginPath();
                ctx.moveTo(x, y);
                        ctx.bezierCurveTo(
                   x + w / 2, y - h * 2 / 3,
                   x + w * 2, y + h / 3,
                   x, y + h
               );
                ctx.bezierCurveTo(
                    x - w * 2, y + h / 3,
                    x - w / 2, y - h * 2 / 3,
                    x, y
                );
           
                if (ctx.isPointInPath(x2, y2)) {
                    return true;
                }
                return false;
            }

            ctx.fill();



            // 曲线转成直线
            var p1=heartPoints[0].reduce(function(a,b){
                return a.concat(b.x,b.y);
            }, [])
            var p2 = heartPoints[1].reduce(function (a, b) {
                return a.concat(b.x, b.y);
            }, [])
            var p1Points = shapPoints.bezierCurveTo.apply(null, p1)
            var p2Points = shapPoints.bezierCurveTo.apply(null, p2)
            console.log(p1Points)
            //drawPoints(p1Points, true)
            // drawPoints(p2Points, true)
            var heartBezierPoints = [];
            var heartLinePoints = [];
            var p4 = p1Points.concat(p2Points);
            for (var i = 0,length=p4.length; i < length; i+=2) {
                heartLinePoints.push([p4[i], p4[i + 1]])

               
            }
            window.heartLinePoints = heartLinePoints;


            var b = new bezierjs(heartPoints[0])
            var b2 = new bezierjs(heartPoints[1])
            var b3 = new bezierjs.PolyBezier([b, b2]);
        
        }
        heart();




        
        function Polygon(points) {

            ctx.moveTo(points[0][0], points[0][1]);
            for (var i = 1, l = points.length; i < l; i++) {
                ctx.lineTo(points[i][0], points[i][1]);
            }
            
        }
        var p2=vec2.fromValues(600,100)
        ctx.beginPath();
        ctx.strokeStyle = 'red';
        ctx.lineWidth = 2;
        var points=[[600,100],[700,100],[750,150],[700,200],[600,200],[550,150]];
        Polygon(points);
        ctx.closePath();
        ctx.stroke();

    
        function contian(a, b) {
            var x = 0;
            return a[0] - b[0] <= x && a[1] - b[1] <= x;
        }
        function windingLine(x0, y0, x1, y1, x, y) {
            if ((y > y0 && y > y1) || (y < y0 && y < y1)) {
                return 0;
            }
            // Ignore horizontal line
            if (y1 === y0) {
                return 0;
            }
            var dir = y1 < y0 ? 1 : -1;
            var t = (y - y0) / (y1 - y0);
            //当交点为两条多边形线的连接点时避免缠绕误差
            // Avoid winding error when intersection point is the connect point of two line of polygon
            if (t === 1 || t === 0) {
                dir = y1 < y0 ? 0.5 : -0.5;
            }

            var x_ = t * (x1 - x0) + x0;

            // If (x, y) on the line, considered as "contain".
            return x_ === x ? Infinity : x_ > x ? dir : 0;
        }

        
        function isAroundEqual(a, b) {
            return Math.abs(a - b) < EPSILON;
        }
        var EPSILON = 1e-8;

        function isAroundEqual(a, b) {
            return Math.abs(a - b) < EPSILON;
        }

         function contain(points, x, y) {
            var w = 0;x
            var p = points[0];

            if (!p) {
                return false;
            }

            for (var i = 1; i < points.length; i++) {
                var p2 = points[i];
                w += windingLine(p[0], p[1], p2[0], p2[1], x, y);
                p = p2;
            }
            var p0 = points[0];
             // 第一个点与最后一个点,值相差differ 大于0.00000001,再
            if (!isAroundEqual(p[0], p0[0]) || !isAroundEqual(p[1], p0[1])) {
                w += windingLine(p[0], p[1], p0[0], p0[1], x, y);
            }

            return w !== 0;
         }



        // 
         function linearRingContainsXY(flatCoordinates, offset, end, stride, x, y) {
             // http://geomalgorithms.com/a03-_inclusion.html
             /**
             版权所有(C / / 2000年softsurfer丹,2012年《星期日泰晤士报
                的这段代码可能会用到的*……和改性的任何用途
                提供版权通知,这是与包含它。
                softsurfer让好的保单在这个方法的代码,和不能被举行
                liable任何房或imagined损伤的功能从它的使用。
                用户的这段代码必须验证的正确性的方法及其应用。
             */
             let wn = 0;
             let x1 = flatCoordinates[end - stride];
             let y1 = flatCoordinates[end - stride + 1];
             for (; offset < end; offset += stride) {
                 const x2 = flatCoordinates[offset];
                 const y2 = flatCoordinates[offset + 1];
                 if (y1 <= y) {
                     if (y2 > y && ((x2 - x1) * (y - y1)) - ((x - x1) * (y2 - y1)) > 0) {
                         wn++;
                     }
                 } else if (y2 <= y && ((x2 - x1) * (y - y1)) - ((x - x1) * (y2 - y1)) < 0) {
                     wn--;
                 }
                 x1 = x2;
                 y1 = y2;
             }
             return wn !== 0;
         }
         function linearRingsContainsXY(flatCoordinates, offset, ends, stride, x, y) {
             if (ends.length === 0) {
                 return false;
             }
             if (!linearRingContainsXY(flatCoordinates, offset, ends[0], stride, x, y)) {
                 return false;
             }
             for (let i = 1, ii = ends.length; i < ii; ++i) {
                 if (linearRingContainsXY(flatCoordinates, ends[i - 1], ends[i], stride, x, y)) {
                     return false;
                 }
             }
             return true;
         }

        // 绕线算法
         function isContainPoint(points,x,y) {
             var r=0;
             for (var i = 0, length=points.length; i < length; i++) {
                 var j = (i + 1) % length;
                 var x2 = points[i][0], y2 = points[i][1];
                 var x3 = points[j][0], y3 = points[j][1];

                 
                 //  

                 // 判断点是否在两点之间
                 if (y >= y2 && y <= y3 && x < ((x3 - x2) * (y - y2) / (y3 - y2) + x2)) {
                     r++;
                 } else if (y <= y2 && y >= y3 && x < ((x3 - x2) * (y - y2) / (y3 - y2) + x2)) {
                     r--;
                 } 

             }
            return r!=0;
         }
       

         function pointInPolygon(vertices, x, y) {
             var a, b, i, j;
             var xpi, ypi, xpj, ypj;
             var c = false;
             for (i = 0; i < vertices.length; i++) {
                 j = (i + 1) % vertices.length;
                 a = vertices[i];
                 b = vertices[j];
                 xpi = a[0];
                 ypi = a[1];
                 xpj = b[0];
                 ypj = b[1];
                 if ((((ypi <= y) && (y < ypj)) || ((ypj <= y) && (y < ypi))) &&
                     (x < (xpj - xpi) * (y - ypi) / (ypj - ypi) + xpi)) {
                     c = !c;
                 }
             }
             return c;
         }
        // x 100  y 100   150 150  x 200 y 200

         //+ Jonas Raoni Soares Silva
         //@ http://jsfromhell.com/math/is-point-in-poly [rev. #0]

         function isPointInPoly(poly, x,y) {
             var c = false;
             for (var i = -1, l = poly.length, j = l - 1; ++i < l; j = i) {
                 var px = poly[i][0];
                 var py = poly[i][1];
                 var px2 = poly[j][0];
                 var py2 = poly[j][1];

                 if (((py <= y && y < py2) || (py2 <= y &&y < py))&& (x< (px2- px) * (y - py) / (py2 - py) + px)){
                     c = !c;
                 }
             }
             return c;

         }
         function isPointInPath(x, y, poly){
             var num = poly.length;
             var i = 0;
             var j = num - 1;
             var c = false;
             for(;i<num;i++){
                 if (((poly[i][1] > y) != (poly[j][1] > y)) &&
                 (x < poly[i][0] + (poly[j][0] - poly[i][0]) * (y - poly[i][1]) /
                                   (poly[j][1] - poly[i][1]))) {
                     c = true;
                 }
                 j = i
             }
             return c

         }

        document.addEventListener('click', function (e) {

            var x = e.pageX - canvas.offsetLeft, y = e.pageY - canvas.offsetTop;

            var invertM = mat2d.invert(mat2d.create(), m);// 逆阵
         
            var xy2 = vec2.transformMat2d(vec2.create(), vec2.fromValues(x, y), m)
            // 计算当前图形位置
            var xy4 = vec2.transformMat2d(vec2.create(), rectPosition, m)
            // 当前鼠标位置
            var xy3 = vec2.transformMat2d(vec2.create(), vec2.fromValues(x, y), invertM)
            
            // 正方形
            if (contian(rectPosition, xy3) && contian(xy3, vec2.add(vec2.create(), rectPosition, rectPosition)))
            {
                console.log('rect命中');
            }
            // 贝塞尔曲线
            //    console.log('bezier', jsBezier._distanceFromCurve({ x: xy3[0], y: xy3[1] }, heartPoints[0]))
            if (isCurve(x, y)) {
                console.log('heartLine命2中');
            }
            if (pointInPolygon(heartLinePoints, xy3[0], xy3[1])) {
                console.log('heartLine命中');
            }
            // 圆形
            if (vec2.distance([400, 100], xy3) <= 50) {
                console.log('circle命中');
            }
            // 多边形
            if (contain(points, xy3[0], xy3[1])) {
                console.log('polygon命中');
            }
            if (pointInPolygon(points, xy3[0], xy3[1])) {
                console.log('polygon3命中');
            }
            if (isPointInPoly(points, xy3[0], xy3[1])) {
                console.log('polygon4命中');
            }
            if (isContainPoint(points, xy3[0], xy3[1])) {
                console.log('polygon5命中');
            }
            var p2 = points.reduce(function (a, b) { return a.concat(b); }, []);
            if (linearRingsContainsXY(p2,0, [p2.length], 2, xy3[0], xy3[1])) {
                console.log('polygon2命中');
            }
           // console.log(x, y, invertM);

        })

    </script>

</body>
</html>