高效地找到圆扇形内的点

Question

我有一组随机分布的二维点，我需要对这些点的一小部分进行耗时操作，但我需要先弄清楚我需要对哪些点进行这个耗时操作。我需要对这些点的一小部分进行时间密集型操作，但我需要首先弄清楚我需要对哪些点进行时间密集型操作。要确定我需要什么点，它们必须通过一系列的几何标准。

最基本的标准是它们是否在特定点的一定距离内。第二个最基本的标准是它们是否包含在从那个特定点延伸出来的圆扇形（一个二维圆锥）内。(编辑：这个操作是有规律地调用的，每次调用的具体点不同，但二维点的集合相同)。

我最初的想法是创建一个包含二维点的网格，然后沿着圆锥体抓取与之相交的网格方块进行迭代。根据网格的大小，它将过滤掉绝大多数不需要的二维点。不幸的是，我所运行的嵌入式系统受到了严重的内存限制，所以一个大的（按照我们的标准，而不是任何人的标准）二维数组将太耗费内存。

我一直在尝试研究使用KD树来加快计算速度，但我一直没能找到与圆扇形和KD树相关的算法。

有没有一种有效的算法可以找到圆扇形内的二维点？

只是说明一下，我们的特殊系统在浮点数学和三角学方面都很慢，所以一个涉及较少的解决方案比一个需要大量的解决方案要优越。

Answer 1

只用整数算术和加减乘除的基本运算就可以检查一个点是否在一个扇形内。

对于一个点是否在一个循环行业它必须满足以下测试。

它必须从扇区的起始 "臂 "逆时针方向定位。
它必须从扇形的末端臂顺时针定位。
它必须比扇形的半径更接近圆心。

顺时针测试

要测试一个向量v2与另一个向量v1是否为顺时针方向，请执行以下操作。

找出逆时针方向的法向量法向量与原向量成90度角。这就是简单易行：如果 v1=(x1,y1)那么逆时针方向的法线是 n1=(-y1,x1).
找出v2在法线上投影的大小。这可以通过计算点产品和法线的投影。
projection = v2.x*n1.x + v2.y*n1.y
如果投影是一个正数，那么v2的位置是逆时针方向的v1，否则v2的位置是顺时针方向的v1。

这是一个逆时针的例子。 Counter-clockwise example

还有一个顺时针的例子 Clockwise example

这些步骤可以结合起来

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 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);
}

下面的示例页面展示了几千个点的测试结果。你可以在下面的代码进行实验。http: /jsbin.comoriyes8edit.

Screenshot

源代码示例

<!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>

注释、警告和限制

您必须用向量来指定扇形的边界。例如，上面的截图显示了一个在(4,1)和(1,4)向量之间延伸的扇形。
如果您的扇形是用其他的术语来指定的，例如角度，您必须先将其转换为向量，例如使用 tan() 功能。幸运的是，你只需要做一次。
这里的逻辑适用于内角小于 180 度的扇形。如果你的扇形可以跨越更大的角度，你将不得不修改它。
此外，这段代码假设你知道扇形的哪个边界向量是 "开始"，哪个是 "结束"。如果您不知道，您可以运行 areClockwise() 来找出答案。
需要注意的是，虽然这些都可以用整数运算来完成，但半径和顺时针的测试都使用了较大的数字范围，这是因为要将x和y进行平方，并将它们相乘。确保使用足够位数的整数来保持结果。

Answer 2

我知道你不想要三角函数，但你可以将每个点（在你的子集中）转换为它的极坐标（其中原点是你的特定点）和阈值。r,theta 哪儿 r < R 和 T1 < theta < T2 对应的扇区。当然，它的内存效率很高!

Answer 3

@Oren Trutner的回答非常棒，所以我决定做一个可视化的例子，并做一些改进，让它在各个角度都能工作。

不多说了，看看下面的例子。

$(document).on('keypress',function (e) {
        if(e.which === 13)
        {
            $("#calc").click();
        }
    });

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

    function vector(x = 0, y = 0) {
        return {x:x,y:y}
    }

    function degToRad(degree) {
        return degree * Math.PI / 180;
    }

    function isIn()
    {
        let illustration = $("#illustration");
        illustration.html("");
        let r = 250;
        let fieldOfViewAngle = 150;
        let x = Number($("#x").val());
        let y = Number($("#y").val());
        let startAngle = Number($("#startAngle").val());
        let startSectorAngle = degToRad(startAngle);
        let endSectorAngle = degToRad(startAngle+fieldOfViewAngle);

        $("#startLine").attr("x2",250 + r*Math.cos(-startSectorAngle)).attr("y2",250 + r*Math.sin(-startSectorAngle));
        $("#endLine").attr("x2",250 + r*Math.cos(-endSectorAngle)).attr("y2",250 + r*Math.sin(-endSectorAngle));
        $("#point").attr("cx",250 +x).attr("cy",250 -y);

        let sectorStartVector = vector(r * Math.cos(startSectorAngle),r * Math.sin(startSectorAngle));
        let sectorEndVector = vector(r * Math.cos(endSectorAngle),r * Math.sin(endSectorAngle));
        let relPoint = vector(x,y);

        if(!this.areClockwise(sectorStartVector, relPoint) &&
            this.areClockwise(sectorEndVector, relPoint))
            $("#result").html("Result: in");
        else{
            $("#result").html("Result: out")
        }
    }

.flixy {
            display: flex;
            flex-direction: column;
        }

        .flixy > div {
            margin-bottom: 20px;
            width:300px
        }

        .flixy > div > input {
            float: right;
        }

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<div id="result"></div>
<div class="flixy">
    <div class="input-group">
        <label>X</label>
        <input id="x">
    </div>
    <div class="input-group">
        <label>Y</label>
        <input id="y">
    </div>

    <div class="input-group">
        <label>Start angle</label>
        <input id="startAngle">
    </div>

    <div class="input-group">
        <label>Radius</label>
        <input value="250" disabled>
    </div>

    <div class="input-group">
        <label>Theta</label>
        <input value="150" disabled>
    </div>
</div>

<button onclick="isIn()" id="calc">calc</button>

<div style="width: 500px;height: 500px; overflow: visible">
    <svg width="500" height="500" style="overflow: visible">
        <circle cx="250" cy="250" r="250" stroke="black" stroke-width="3" fill="yellow"></circle>
        <line id="startLine" x1="250" y1="250" x2="500" y2="250" style="stroke:#2fa360;stroke-width:2" />
        <line id="endLine" x1="250" y1="250" x2="500" y2="250" style="stroke:#1d68a7;stroke-width:2" />
        <circle id="point" cx="250" cy="250" r="5" fill="red"></circle>
    </svg>
</div>

高效地找到圆扇形内的点

问题描述投票：27回答：3

3个回答

顺时针测试

半径测试

把它放在一起

源代码示例

注释、警告和限制

最新问题

高效地找到圆扇形内的点

问题描述 投票：27回答：3

3个回答

顺时针测试

半径测试

把它放在一起

源代码示例

注释、警告和限制

最新问题

问题描述投票：27回答：3