概要

在图形学中判断一个点是否在多边形内，若多边形不是自相交的，那么可以简单的判断这个点在多边形内部还是外部；若多边形是自相交的，那么就需要根据非零环绕数规则或者奇-偶规则判断。

判断多边形是否是自相交的：多边形在平面内除顶点外还有其他公共点

  • 奇-偶规则（Odd-even Rule）：奇数表示在多边形内，偶数表示在多边形外。
    从该点p任意方向的一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。
  • 非零环绕数规则（Nonzero Winding Number Rule）：若环绕数非零则表示在多边形内，否则是外部点。
    首先使多边形的边变为矢量。将环绕数初始化为零。再从该点p作任意方向的一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从左到右穿过射线时，环绕数加1，从右到左时，环绕数减1（也可以通过顺时针、逆时针来判断，入股与路径的顺时针相交，则加1，如果与路径的逆时针相交，则减1）。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。

image.png

用途

掌握原理很简单，关键是怎么转换到实际应用中，用途极多，下面我们来看看 fill 和 events。

fill

用过canvas的同学应该都比较熟悉 fill() 方法，当使用 rect() 、arc()、beginPath() 等相关方法创建路径时，路径其实是不可见的，好比隐形墨水，用隐形墨水绘制的内容并不会立刻显示出来，必须进行一些后续的操作，例如加热、涂抹化学药品、照射红外线等，这些操作在 canvas 中好比fill()、stroke() 等方法。当我们在页面上随便绘制一系列路径并调用 fill() 方法时，该方法会对我们的路径或图形进行填充操作，填充原理就是非零环绕原则。
image.png

  1. <!DOCTYPE html>
  2. <html lang="en">
  3.   <head>
  4.     <meta charset="UTF-8" />
  5.     <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  6.     <meta http-equiv="X-UA-Compatible" content="ie=edge" />
  7.     <title>非零环绕原则</title>
  8.   </head>
  9.   <body>
  10.     <canvas
  11.       id="canvas"
  12.       width="500"
  13.       height="600"
  14.       style="border: 1px solid #c3c3c3;"
  15.     >
  16.       您的浏览器不支持 HTML5 canvas 标签。
  17.     </canvas>
  18.   </body>
  19.   <script>
  20.     const canvas = document.getElementById("canvas");
  21.     const ctx = canvas.getContext("2d");
  22.     ctx.strokeStyle = "blue";
  23.     ctx.lineWidth = 2;
  24.     ctx.fillStyle = "#FF0000";
  25.     ctx.beginPath();
  26.     ctx.moveTo(10, 10);
  27.     ctx.lineTo(100, 10);
  28.     ctx.lineTo(45, 55);
  29.     ctx.stroke();
  30.     ctx.fill();
  32.     const offsetY1 = 100;
  33.     ctx.beginPath();
  34.     ctx.moveTo(10, 10 + offsetY1);
  35.     ctx.lineTo(100, 10 + offsetY1);
  36.     ctx.lineTo(45, 55 + offsetY1);
  37.     ctx.closePath();
  38.     ctx.stroke();
  39.     ctx.fill();
  41.     const offsetY2 = 200;
  42.     ctx.beginPath();
  43.     ctx.moveTo(10, 10 + offsetY2);
  44.     ctx.lineTo(100, 10 + offsetY2);
  45.     ctx.lineTo(10, 55 + offsetY2);
  46.     ctx.lineTo(100, 55 + offsetY2);
  47.     ctx.stroke();
  48.     ctx.fill();
  50.     const offsetY3 = 350;
  51.     ctx.beginPath();
  52.     ctx.moveTo(10, 10 + offsetY3);
  53.     ctx.lineTo(100, 55 + offsetY3);
  54.     ctx.lineTo(150, 55 + offsetY3 - 100);
  55.     ctx.lineTo(40, 55 + offsetY3 + 40);
  56.     ctx.lineTo(60, 10 + offsetY3);
  57.     ctx.lineTo(125, 55 + offsetY3);
  58.     ctx.lineTo(180, 10 + offsetY3);
  59.     ctx.closePath();
  60.     ctx.stroke();
  61.     ctx.fill();
  62.   </script>
  63. </html>

events

想给 canvas 元素添加事件，是不能直接指定的，通常是通过鼠标对象来判断事件元素。例如想给下图元素添加点击事件，点击事件只能绑定在整个 canvas 上，通过 mouseEvent 对象来判断点击的图形，对于不规则图形，有些库做法很粗暴，直接判断是否在最小包围盒范围内， 比较准确的判断规则可以借助非零环绕原则来判断。
image.png