geometry - Efficiently find points inside a circle sector

Question

I have a set of 2d points distributed randomly. I need to perform a time intensive operation on a small subset of these points but I need to first figure out what points I need to perform this time intensive operation on. To determine what points I need they must pass a series of geometric criteria.

The most basic criteria is are they within a certain distance of a specific point. The second most basic criteria is whether they are contained within a circle sector (a 2-D cone) extending out from that specific point. (Edit: This operation is called regularly with a different specific point each time but the same set of 2d points.)

My initial thought was to create a grid containing the 2d points, then iterate along the cone grabbing grid squares that it intersects. Depending on the size of the grid it would filter out the vast majority of unneeded 2d points. Unfortunately the embedded system I'm running on is severely memory constrained so a large (by our standards not anyone elses) 2d array would be too memory intensive.

I have been trying to investigate using KD trees to speed up the calculation but I haven't been able to find an algorithm relating circle sectors and kd-trees.

Is there an efficient algorithm for finding what 2d points lie within a circle sector?

Just a note our particular system is slow at both floating point math and trigonometry so a solution that involves less of those is superior one that requires a lot of it.

score 118 · Accepted Answer

可以检查一个点是否在一个扇区内，只有整数算术和加法、减法和乘法的基本运算。

要使一个点在圆形扇区内，它必须满足以下测试：

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

顺时针测试

要测试向量 v2 是否顺时针指向另一个向量 v1，请执行以下操作：

求 v1 的逆时针法向量。法线向量与原始向量成 90 度角。这很简单：如果v1=(x1,y1)，则逆时针法线为n1=(-y1,x1)。
求 v2 在法线上的投影大小。这可以通过计算v2 和法线的点积来完成。

projection = v2.x*n1.x + v2.y*n1.y
如果投影是正数，则 v2 与 v1 逆时针定位。否则，v2 对 v1 顺时针方向。

这是一个逆时针的例子：逆时针示例

还有一个顺时针的例子：顺时针示例

步骤可以组合：

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.com/oriyes/8/edit。

示例源代码

<!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 平方并将它们相乘。确保使用足够位的整数来保存结果。

score 5 · Accepted Answer

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

score 0 · Accepted Answer

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

geometry - Efficiently find points inside a circle sector

3 回答 3

顺时针测试

半径测试

把它放在一起

示例源代码

注释、警告和限制

Related

Reference