PROSAGA码农传奇-雾计算/网格计算-有效地在圆圈区域内找到点

<div class =“post-text”itemprop =“text”>
  <P>
    可以检查点是否在仅具有整数运算的扇区内以及加法，减法和乘法的基本运算。
  </p>
  <P>
    对于一个点在一个内部
    <a href="http://en.wikipedia.org/wiki/Circular_sector" rel="noreferrer">
      循环部门
    </A>
    ，它必须满足以下测试：
  </p>
  <OL>
    <LI>
      它必须从扇区的起始“臂”逆时针定位。
    </LI>
    <LI>
      它必须从扇区的末端臂顺时针定位。
    </LI>
    <LI>
      <P>
        它必须比扇形半径更接近圆心。
      </p>
      <P>
        <img src =“https://i.stack.imgur.com/jMHJw.png”alt =“对于要在a内的点，它必须满足以下测试”/>
        <img src =“https://i.stack.imgur.com/YrKuj.png”alt =“它必须从扇区”/>的起始“臂”逆时针定位
        <img src =“https://i.stack.imgur.com/c1gsP.png”alt =“它必须从扇区的末端臂顺时针定位”/>
        <img src =“https://i.stack.imgur.com/lofmc.png”alt =“它必须更接近圆的中心而不是扇区的半径”/>
      </p>
    </LI>
  </醇>
  <H2>
    顺时针测试
  </H2>
  <P>
    要测试向量v2是否顺时针到另一个向量v1，请执行以下操作：
  </p>
  <OL>
    <LI>
      <P>
        找逆时针
        <a href="http://en.wikipedia.org/wiki/Normal_%28geometry%29" rel="noreferrer">
          法向量
        </A>
         v1。法向量与原始向量成90度角。这是
        <a href="https://stackoverflow.com/questions/1243614/how-do-i-calculate-the-normal-vector-of-a-line-segment">
          直截了当
        </A>
        ：如果
         <code>
          v1=(x1,y1)
        </code>
        ，那么逆时针正常就是
         <code>
          n1=(-y1,x1)
        </code>
        。
      </p>
    </LI>
    <LI>
      <P>
        找到正常情况下v2投影的大小。这可以通过计算来完成
        <a href="http://en.wikipedia.org/wiki/Dot_product" rel="noreferrer">
          点积
        </A>
         v2和正常。
      </p>
      <P>
         <code>
          projection = v2.x*n1.x + v2.y*n1.y
        </code>
      </p>
    </LI>
    <LI>
      <P>
        如果投影是正数，则v2逆时针定位到v1。否则，v2顺时针旋转到v1。
      </p>
    </LI>
  </醇>
  <P>
    这是一个逆时针的例子：

<img src =“https://i.stack.imgur.com/rG3JS.png”alt =“逆时针示例”/>
  </p>
  <P>
    顺时针的例子：

<img src =“https://i.stack.imgur.com/W0FPK.png”alt =“顺时针示例”/>
  </p>
  <P>
    这些步骤可以合并：

</p>
   <pre>
    <code>
      function areClockwise(v1, v2) {
  return -v1.x*v2.y + v1.y*v2.x > 0;
}

</code>
  </pre>
  <H2>
    半径测试
  </H2>
  <P>
    半径测试很简单。只需检查点距圆心的距离是否小于所需半径。为了避免计算平方根，我们可以将距离的平方与半径的平方进行比较。

</p>
   <pre>
    <code>
      function isWithinRadius(v, radiusSquared) {
  return v.x*v.x + v.y*v.y <= radiusSquared;
}

</code>
  </pre>
  <H2>
    把它放在一起
  </H2>
  <P>
    完整的扇区测试看起来像：

</p>
   <pre>
    <code>
      function isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared) {
  var relPoint = {
    x: point.x - center.x,
    y: point.y - center.y
  };

return !areClockwise(sectorStart, relPoint) &&
         areClockwise(sectorEnd, relPoint) &&
         isWithinRadius(relPoint, radiusSquared);
}

</code>
  </pre>
  <P>
    以下示例页面展示了几千个点。您可以在以下位置试验代码：
    <a href="http://jsbin.com/oriyes/8/edit" rel="noreferrer">
      http://jsbin.com/oriyes/8/edit
    </A>
    。
  </p>
  <P>
    <img src =“https://i.stack.imgur.com/0PbMe.png”alt =“截图”/>
  </p>
  <H2>
    示例源代码
  </H2>
   <pre class="lang-html prettyprint-override">
    <code>
      <!DOCTYPE html>
<html>
  <head>
    <script src="http://code.jquery.com/jquery-1.8.2.min.js"></script>
    <style>
      .canvas {
        position: absolute;
        background: #f4f4f4;
        border: 8px solid #f4f4f4;
        width: 400px;
        height: 400px;
      }

.dot {
        position: absolute;
        font: 16px Arial;
      }
      .out { color: #ddd; }
      .in { color: #00dd44; }
    </style>
    <script>
      function isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared) {
        var relPoint = {
          x: point.x - center.x,
          y: point.y - center.y
        };

return !areClockwise(sectorStart, relPoint) &&
               areClockwise(sectorEnd, relPoint) &&
               isWithinRadius(relPoint, radiusSquared);
      }

function areClockwise(v1, v2) {
        return -v1.x*v2.y + v1.y*v2.x > 0;
      }

function isWithinRadius(v, radiusSquared) {
        return v.x*v.x + v.y*v.y <= radiusSquared;
      }

$(function() {
        var $canvas = $("#canvas");
        var canvasSize = 400;
        var count = 4000;

// define the sector
        var center = { x: canvasSize / 2, y: canvasSize / 2 };
        var sectorStart = { x: 4, y: 1 };
        var sectorEnd = { x: 1, y: 4 };
        var radiusSquared = canvasSize * canvasSize / 4;

// create, draw and test a number of random points
        for (var i = 0; i < count; ++i) {

// generate a random point
          var point = {
            x: Math.random() * canvasSize,
            y: Math.random() * canvasSize
          };

// test if the point is inside the sector
          var isInside = isInsideSector(point, center, sectorStart, sectorEnd, radiusSquared);

// draw the point
          var $point = $("<div class='dot'></div>")
              .css({
                left: point.x - 3,
                top:  canvasSize - point.y - 8 })
              .html("&#8226;")
              .addClass(isInside ? "in" : "out")
              .appendTo($canvas);
        }
      });
    </script>
  </head>
  <body>
    <div id="canvas" class="canvas"></div>
  </body>
</html>

</code>
  </pre>
  <H2>
    注意事项，警告和限制
  </H2>
  <OL>
    <LI>
      <P>
        您必须根据向量指定扇区的边界。例如，上面的屏幕截图显示了在（4,1）和（1,4）的向量之间拉伸的扇区。
      </p>
    </LI>
    <LI>
      <P>
        如果您的部门以其他术语指定，例如角度，你必须首先将其转换为矢量，例如使用
         <code>
          tan()
        </code>
         功能。幸运的是，你只需要这样做一次。
      </p>
    </LI>
    <LI>
      <P>
        这里的逻辑适用于内角小于180度的扇区。如果您的扇区可以跨越更大的角度，则必须对其进行修改。
      </p>
    </LI>
    <LI>
      <P>
        此外，代码假定您知道扇区的哪个边界向量是“开始”，哪个是“结束”。如果你不这样做，你可以运行
         <code>
          areClockwise()
        </code>
         在他们身上找出答案。
      </p>
    </LI>
    <LI>
      <P>
        请注意，虽然所有这些都可以通过整数运算来完成，但是半径和顺时针测试都使用更大的范围数字，由于平方x和y并将它们相乘。确保使用足够位的整数来保存结果。
      </p>
    </LI>
  </醇>
</DIV>