首页 > 其他分享 >可视化学习：利用向量判断多边形边界

可视化学习：利用向量判断多边形边界

时间：2023-11-30 12:35:25浏览次数：41  
标签：canvas 多边形 ctx vertices 可视化 const 三角形 向量

引言

继续巩固我的可视化学习，向量运算是计算机图形学的基础，本例依旧是向量的一种应用，利用向量判断多边形边界，但是多边形的边界判断稍微有点复杂，所以除了应用向量之外，还需要借助三角剖分的相关工具。这个例子中可视化的展示采用Canvas2D来实现。

问题

假设Canvas画布上存在一个如下多边形：

polygon1

我们移动鼠标的时候，想要实现一个效果，就是当鼠标移动到多边形内部的时候，将多边形内部的填充颜色更新成其他颜色；所以此时我们需要判断鼠标是否在多边形内部，这就涉及到多边形边界的判断。

思路

首先我们先将这个多边形绘制到Canvas画布上。

<canvas width="512" height="512"></canvas>

canvas {
  width: 512px;
  height: 512px;
  border: 1px solid #eee;
}

const canvas = document.querySelector('canvas');
const ctx = canvas.getContext('2d');

ctx.translate(canvas.width / 2, canvas.height / 2);
ctx.scale(1, -1);

const vertices = [
    [ -179.2, 128 ],
    [ -102.4, 76.8 ],
    [ -64, 181.76 ],
    [ -25.6, 143.36 ],
    [ -25.6, 33.28 ],
    [ 102.4, 53.76 ],
    [ 0, -153.6 ],
    [ -76.8, -76.8 ],
    [ -153.6, -76.8 ],
    [ -115.2, 0 ]
];

drawPolygon(vertices);

function drawPolygon(vertices, fillStyle = "red") {
  ctx.beginPath();
  ctx.moveTo(...vertices[0]);
  for (let i = 1; i < vertices.length; i ++) {
      ctx.lineTo(...vertices[i]);
  }
  ctx.closePath();
  ctx.fillStyle = fillStyle;
  ctx.fill();
}

1. 调用API

对于Canvas2D而言，有一个API自带的方法，就是CanvasRenderingContext2D的isPointInPath方法。

这个方法使用起来非常简单，我们在这个时候直接增加一个鼠标移动事件的监听就可以。

const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
  const {x: pageX, y: pageY} = e;
  // 坐标转化
  const offsetX = x - left;
  const offsetY = y - top;
  // 清除画布
  ctx.clearRect(-256, -256, 512, 512);
  if (ctx.isPointInPath(offsetX, offsetY)) {
    drawPolygon(vetices, "green");
  } else {
    drawPolygon(vetices);
  }
});

但是这个API的使用存在很大的局限性，就是它只能针对当前绘制的图形生效。

就比如说，如果在完成这个多边形的绘制之后，又绘制了一个小三角形。

const triangle = [
  [100, 100], 
  [100, 200], 
  [150, 200]
];

drawPolygon(triangle, "blue");

为了保持这个小三角形，我们还需要修改鼠标监听事件，以达到更新画布时，三角形依旧被绘制。

canvas.addEventListener('mousemove', e => {
  const {pageX: x, pageY: y} = e;
  // 坐标转化
  const offsetX = x - left;
  const offsetY = y - top;
  // 清除画布
  ctx.clearRect(-256, -256, 512, 512);
  if (ctx.isPointInPath(offsetX, offsetY)) {
    drawPolygon(vertices, "green");
    drawPolygon(triangle, "blue");
  } else {
    drawPolygon(vertices);
    drawPolygon(triangle, "blue");
  }
});

此时我们再移动鼠标，就会发现，在鼠标移动到多边形内部时，多边形的填充颜色并不会变，但是当鼠标移动到小三角形内部时，多边形的填充色发生了变化；这就是Canvas2D Context的isPointInPath方法所存在的局限性。

2. 自定义isPointInPath

为了突破Canvas2D API中自带方法的局限性，最简单的方法就是，我们手动自定义一个自己的isPointInPath方法。

具体实现如下：

function isPointInPath(x, y) {
  // 根据ctx重新clone一个新的Canvas对象
  const cloned =  ctx.canvas.cloneNode().getContext('2d');
  cloned.translate(canvas.width / 2, canvas.height / 2);
  cloned.scale(1, -1);
  let ret = false;
  // 绘制多边形，判断点是否在图形内部
  drawPolygon(cloned, vertices, "red");
  ret |= cloned.isPointInPath(x, y);
  if (!ret) {
    // 如果不在，继续绘制小三角形，判断点是否在图形内部
    drawPolygon(cloned, triangle, "blue");
    ret |= cloned.isPointInPath(x, y);
  }
  return ret;
}
  • 首先，根据原画布的Context创建一个新的Canvas对象并获取它的上下文
  • 然后绘制多边形，并判断鼠标是否在多边形内部
  • 如果不在多边形内部，继续判断是否在三角形内部
  • 最后将结果返回

可以看到，在这个自定义的方法内部，我们依然是调用了Canvas2D Context的isPointInPath方法。

接着我们还需要修改鼠标的监听事件，把判断方法改为我们自定义的isPointInPath。

此时移动鼠标，可以看到，当鼠标移动到多边形或者三角形内部，都可以使多边形的填充色发生变化；这就是因为我们在自定义的isPointInPath中做的两次判断。

但是我们也能发现，虽然这种方式解决了我们在第一种方式中所碰到的问题，却也存在其他问题，第一，是增加了很多无谓的Canvas绘图操作；第二，是通用性差，如果图形有修改，那么isPointInPath方法就要跟着修改，并且这个方法依赖于Canvas2D的API，如果哪天修改了绘图方式，比如改为使用WebGL，就不能使用了。

3. 通用型isPointInPath

所以我们需要实现一个更具通用性的isPointInPath方法：直接通过点与几何图形的数学关系来判断点是否在图形内，也就是我们标题中所说的利用向量来判断。

但是直接判断点与几何图形的关系，还是比较困难的。这个时候，我们可以先对多边形进行三角剖分，三角剖分可以简单地理解为是把多边形表示成由多个三角形组合而成的形式；接着将点和对应的多个三角形的关系进行逐一判断；最后得出结果。

对于三角剖分，涉及的算法稍复杂，这里我们直接使用一个成熟的、使用起来比较简单的库——earcut；然后就剩下最关键的一步，就是点和三角形的位置判断。

判断点是否在三角形内部，就相对比较简单了：

假设三角形的三个点是A、B、C，把三角形的三条边分别使用向量表示，再将平面上一个点D连接三角形三个顶点得到三个向量，那么点D在三角形内部的充分必要条件就是：

AB x AD、BC x BD、CA x CD三组向量的叉乘结果符号相同。就如下图所示。

2
  • 如果点在三角形内部，就如图上的点D，可以看出AB 到 AD、BC 到 BD、CA 到 CD的旋转方向都是逆时针，旋转方向相同，所以最后的叉乘结果符号都是相同的；
  • 而如果点在三角形外部，就如图上的点D'，可以看出AB到AD'和CA到CD'的旋转方向是逆时针，但BC到BD'的旋转方向是顺时针，所以三组向量叉乘的结果符号并不相同

因此根据上述条件，就可以定义一个简单的判定函数：

function inTriangle(p1, p2, p3, point) {
    const a = p2.copy().minus(p1);
    const b = p3.copy().minus(p2);
    const c = p1.copy().minus(p3);

    const u1 = point.copy().minus(p1);
    const u2 = point.copy().minus(p2);
    const u3 = point.copy().minus(p3);

    const s1 = Math.sign(a.cross(u1));
    const s2 = Math.sign(b.cross(u2));
    const s3 = Math.sign(c.cross(u3));

    return s1 === s2 && s2 === s3;
}

这个函数的前三个参数是三角形的三个顶点，最后一个参数是待判断的点；这样就能判断点是否在三角形内部了。

但是这个函数中还缺少一种特殊情况的判断，就是点恰好在三角形某条边上的情况。

如果一个点在三角形的一条边上，那它需要满足以下2个条件：

  • 第一，它和所在边某个顶点形成的向量与这个顶点所在边的向量，这两个向量的叉乘结果为0，即这两个向量的夹角为180度或0度。比如点D在边AB上，则AB x AD为0

  • 第二，它和这个顶点形成的向量与这个顶点所在边的向量，这两个向量的点乘结果除以边长的平方，结果大于等于0且小于等于1。比如点D在边AB上，则0<= AB·AD/AB² <=1

    这个值也就是AD在AB上的投影的长度，与AB长度的比值，大于零，说明两个向量的夹角是0度，为同一方向，小于等于1，也就说明点D在线段AB上。

根据这两个条件，我们可以对上面的判定函数进行优化：

function inTriangle(p1, p2, p3, point) {
    const a = p2.copy().minus(p1);
    const b = p3.copy().minus(p2);
    const c = p1.copy().minus(p3);

    const u1 = point.copy().minus(p1);
    const u2 = point.copy().minus(p2);
    const u3 = point.copy().minus(p3);

    const s1 = Math.sign(a.cross(u1));
    let p = a.dot(u1) / a.length ** 2;
    if (s1 === 0 && p >= 0 && p <= 1) return true;
    const s2 = Math.sign(b.cross(u2));
    p = b.dot(u2) / b.length ** 2;
    if (s2 === 0 && p >= 0 && p <= 1) return true;
    const s3 = Math.sign(c.cross(u3));
    p = c.dot(u3) / c.length ** 2;
    if(s3 === 0 && p >= 0 && p <= 1) return true;

    return s1 === s2 && s2 === s3;
}

这样我们就可以使用inTriangle函数对某个点是否在三角形内部进行判断了。

现在我们来继续完成对点在多边形内部的判断：

  1. 首先使用earcut库对多边形进行三角剖分处理

    1. 引入earcut库

      <script src="https://unpkg.com/[email protected]/dist/earcut.dev.js"></script>

    2. 因为earcut库只接受扁平化的顶点数据，我们需要先用数组的flat方法将顶点扁平化

      const points = vertices.flat();

    3. 然后我们就可以把扁平化后的数据传给earcut进行处理了

      const triangles = earcut(points);
console.log(triangles);

      根据打印结果，可以看到earcut的处理结果是一个数组，这个triangles数组的元素是顶点数据在vertices数组中的下标；在这个数组中，每三个元素所对应的顶点就构成一个三角形。

    这样我们就完成了多边形的三角剖分。

  2. 接着逐个判断点是否在每个三角形内部。

    // 判断点是否在多边形内部
// 将多边形进行三角剖分，然后判断点是否在其中某个三角形内部
function isPointInPolygon({vertices, cells}, point) {
    let ret = false;
    for(let i = 0; i < cells.length; i += 3) {
        const p1 = new Vector2D(...vertices[cells[i]]);
        const p2 = new Vector2D(...vertices[cells[i + 1]]);
        const p3 = new Vector2D(...vertices[cells[i + 2]]);
        if (inTriangle(p1, p2, p3, point)) {
            ret = true;
            break;
        }
    }
    return ret;
}

    根据返回的布尔值就可以知道点是否在多边形内部。

  3. 最后就是修改鼠标监听事件的处理程序。

    const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
  const {pageX: x, pageY: y} = e;
  // 坐标转化
  const offsetX = x - left;
  const offsetY = y - top;
  ctx.clearRect(-256, -256, 512, 512);

  const point = new Vector2D((offsetX - canvas.width / 2), (canvas.height / 2 - offsetY)); // 因为Canvas经过坐标转换，所以这里需要把页面上点的坐标也转换一遍，才能正常判断
  if (isPointInPolygon({
        vertices,
        cells: triangles
      }, point)
  ) {
    drawPolygon(vertices, "green");
    drawPolygon(triangle, "blue");
  } else {
    drawPolygon(vertices);
    drawPolygon(triangle, "blue");
  }
});

    这里需要注意，Canvas2D自带的API在进行判断时，应该是自动对鼠标对应的点的坐标进行了转换，所以我们使用自定义的方法时，不能直接使用offsetX和offsetY，需要自己去将点的坐标根据坐标系的转换计算出对应在画布上的坐标。

此时，我们再去移动鼠标，就可以看到，当鼠标移动到多边形内部或者多边形的边时，多边形的填充色发生了改变，也就说明我们的判断生效了；这就成功应用了向量来判断多边形边界。

标签：canvas,多边形,ctx,vertices,可视化,const,三角形,向量
From： https://www.cnblogs.com/beckyyyy/p/17867036.html

相关文章

  • 数据之美：数据可视化引领信息时代
    数据可视化，作为当今信息时代的重要工具，正逐渐受到更多人的关注和重视。它的重要性不仅在于帮助人们更直观地理解数据，更在于为我们揭示数据背后的故事，以及对决策和发现见解的巨大价值。那么，为何数据可视化越来越被人们所重视呢？接下来，让我们一同深入探讨。视觉化理解：人类是视觉动......
  • 数据可视化软件之变：免费化趋势解析
    近年来，我们见证了数据可视化软件呈现出明显的免费化趋势。这个趋势的背后隐藏着许多关键原因，影响着整个数据行业的发展和走向。为何数据可视化软件开始朝着免费方向发展？让我们一同深入探讨。普及数字化需求：数字化已经深入到我们日常生活和工作的方方面面。随着大数据和信息化的......
  • 数据可视化：数据洪流中的引领者
    在当今信息爆炸的时代，数据量呈指数级增长，它们是我们日常生活和工作中的重要组成部分。然而，数据本身是无生命的数字和统计，若不能有效地被理解、传达和利用，其潜力就难以实现。这正是数据可视化变得越来越重要的原因所在。首先，数据可视化帮助我们更直观地理解信息。人类是视觉动物，......
  • R语言拟合改进的稀疏广义加性模型（RGAM）预测、交叉验证、可视化
    全文链接：https://tecdat.cn/?p=34409原文出处：拓端数据部落公众号简介这是一种拟合稀疏广义加性模型（GAM）的新方法。RGAM具有计算可扩展性，并且适用于连续、二进制、计数和生存数据。让我们生成一些数据： Rset.seed(1)n<-100;p<-12mu=rowSums(x[,1:3])+f4+f......
  • 十、Docker 可视化与监控
    6.1常用工具介绍当Docker部署规模逐步变大后，可视化监控容器环境的性能和健康状态将会变得越来越重要。Docker的图形化管理工具，提供状态显示面板、应用模板快速部署、容器镜像网络数据卷的基本操作（包括上传下载镜像，创建容器等操作）、事件日志显示、容器控制台操作、Swarm集......
  • Jmeter压测可视化监控平台
    许多小伙伴在使用Jmeter原生测试报告时，有以下四点困扰： 报告不具备实时性。报告文件的大小随着测试时间的增长而增长，而磁盘存在读写瓶颈，随时都可能崩溃。报告中的数据是测试时间段内的平均值。报告较为冗余，可读性较差。在实际测试过程中，我们一般只关心三条曲线的数据......
  • 哪里可了解低代码数据可视化开发平台？
    如果想要提升办公协作效率，可以用什么样的平台助力实现这一目标？其实，随着市场竞争的日益加剧，低代码技术平台的应用价值也逐渐凸显出来，其可视化、易操作、灵活便利等优势特点，是很多中大型企业倾向于使用的数据可视化开发平台。想要了解低代码数据可视化开发平台的相关信息，通过这篇文......
  • Java开发者的Python快速实战指南：探索向量数据库之文本搜索
    前言如果说Python是跟随我的步伐学习的话，我觉得我在日常开发方面已经没有太大的问题了。然而，由于我没有Python开发经验，我思考着应该写些什么内容。我回想起学习Java时的学习路线，直接操作数据库是其中一项重要内容，无论使用哪种编程语言，与数据库的交互都是不可避免的。然而，直接操作......
  • r语言有限正态混合模型EM算法的分层聚类、分类和密度估计及可视化|附代码数据
    原文链接：http://tecdat.cn/?p=23825最近我们被客户要求撰写关于有限正态混合模型EM算法的研究报告，包括一些图形和统计输出。简介本文介绍了基于有限正态混合模型在r软件中的实现，用于基于模型的聚类、分类和密度估计。提供了通过EM算法对具有各种协方差结构的正态混合模型进行参......
  • 多边形顶点顺时针排放
    效果 //凹多边形，凸多边形都能判断publicstaticboolIsVertsClockwise(Vector2[]verts){if(verts.Length<3)returnfalse;//劣角数量比优角数量多//假设是顺时针,那叉乘结果为正的次数比负多intpositionNum=0;intnegativeNum......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99