有效地找到圈内的点

问题描述

我有一组随机分布的2d点。我需要对这些点的一小部分进行时间密集型操作，但我需要先弄清楚我需要执行这项时间密集型操作。为了确定我需要什么点，他们必须通过一系列的几何标准。

最基本的标准是它们在特定点的某个距离内。第二个最基本的标准是它们是否包含在从该特定点延伸出的圆形扇区（二维圆锥体）内。 （编辑：此操作每次定期调用不同的特定点，但同一组2d点。）

我最初的想法是创建一个包含2d的网格点，然后迭代它与相交的锥形抓取网格平方。根据网格的大小，它会过滤绝大多数不需要的2D点。不幸的是，我运行的嵌入式系统受到严重的内存限制，所以一个大的（根据我们的标准，不是任何人都可以）2d数组会太过内存密集型的。

我一直试图调查使用KD树来加速计算，但我一直未能找到一个有关圈部门和kd-trees的算法。

有没有一种有效的算法来找出圈内的2d点？

特定的系统在浮点数学和三角学方面都很慢，所以涉及较少这些的解决方案是优越的，需要大量的解决方案。

解决方案

有可能检查点是否在只有整数运算的扇区内，以及加法，减法和乘法的基本操作。

对于位于。法向矢量与原始矢量成90度角。这是 。

示例源代码

 <！DOCTYPE html> 
< html> 
< head> 
< script src =http://code.jquery.com/jquery-1.8.2.min.js>< / script> 
< style> 
 .canvas {
 position：absolute; 
背景：＃f4f4f4; 
 border：8px solid＃f4f4f4; 
 width：400px; 
 height：400px; 
} 
 
 .dot {
 position：absolute; 
字体：16px Arial; 
} 
 .out {color：#ddd; } 
 .in {color：＃00dd44; } 
< / style> 
< script> 
函数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）; 
} 
 
函数areClockwise（v1，v2）{
 return -v1.x * v2.y + v1.y * v2.x> 0; 
} 
 
函数isWithinRadius（v，radiusSquared）{
 return v.x * v.x + v.y * v.y  
 $ b $（$）
 
 $ b $ var $ canvas $ = 4000; 
 
 //定义扇区
 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; 
 $ b $ //创建，绘制和测试随机点的数目
（var i = 0; i  
 //产生一个随机点
 var point = {
x：Math.random（）* canvasSize，
y：Math.random（）* canvasSize 
}; 
 
 //测试点是否在扇区内
 var isInside = isInsideSector（point，center，sectorStart，sectorEnd，radiusSquared）; 
 
 //绘制点
 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 =canvasclass =canvas>< / div> 
< / body> 
< / html> 
  

注意，注意事项和限制

1. 您必须根据向量来指定扇区的边界。例如，上面的屏幕截图显示了一个在（4,1）和（1,4）向量之间延伸的扇区。

如果您的扇区被指定换句话说，例如角度，你必须先将它转换成矢量，例如使用 tan（）函数。幸运的是，你只需要做一次。


2. 这里的逻辑适用于内角小于180度的扇区。如果您的部门可以跨越更大的角度，则必须对其进行修改。




3. 另外，代码假定您知道哪些边界向量部门是起点，哪个是终点。如果你不这样做，你可以运行 areClockwise（）来找出它。

请注意，虽然所有这些都可以用整数算术完成，但由于将x和y平方并将它们相乘，因此半径测试和顺时针测试都使用较大范围的数字。确保使用足够的位数来保存结果。

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.

解决方案

It's possible to check if a point is inside a sector with only integer arithmetic and the basic operations of addition, subtraction and multiplication.

For a point to be inside a circular sector, it has to meet the following tests:

1. It has to be positioned counter-clockwise from the start "arm" of the sector.
2. It has to be positioned clockwise from the end arm of the sector.

3. It has to be closer to the center of the circle than the sector's radius.

Clockwise tests

To test if a vector v2 is clockwise to a another vector v1, do the following:

1. Find the counter-clockwise normal vector of v1. The normal vector is at a 90 degrees angle to the original vector. This is straightforward to do: if v1=(x1,y1), then the counter-clockwise normal is n1=(-y1,x1).

2. Find the size of the projection of v2 on the normal. This can be done by calculating the dot product of v2 and the normal.

   projection = v2.x*n1.x + v2.y*n1.y

3. If the projection is a positive number, then the v2 is positioned counter-clockwise to v1. Otherwise, v2 is clockwise to v1.

Here's a counter-clockwise example:

And a clockwise example:

The steps can be combined:

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

Radius test

The radius test is straightforward. Just check if the distance of the point from the center of the circle is less than the desired radius. To avoid computing square roots, we can compare the square of the distance with the square of the radius instead.

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

Putting it together

The complete sector test looks something like:

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

The following sample page demonstrates this over several thousand points. You can experiment with the code at: http://jsbin.com/oriyes/8/edit.

Sample source 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>

Notes, caveats and limitations

1. You have to specify the boundaries of the sector in terms of vectors. The screenshot above, for example, shows a sector stretching between the vectors of (4,1) and (1,4).

2. If your sector is specified in other terms, e.g. angles, you will have to convert that to vectors first, e.g. using the tan() function. Fortunately, you only have to do this once.

3. The logic here works for sectors with an inner angle of less than 180 degrees. If your sectors can span a larger angle, you'll have to modify it.

4. Additionally, the code assumes that you know which of the bounding vectors of the sector is the "start" and which is the "end". If you don't, you can run the areClockwise() on them to find out.

5. Note that while all this can be done with integer arithmetic, both the radius and clockwise tests use a larger range of numbers, due to squaring x's and y's and multiplying them together. Make sure to use integers of sufficient bits to hold the results.

这篇关于有效地找到圈内的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！