Эффективно находить точки внутри сектора круга

У меня есть набор из 2d точек, распределенных случайным образом. Мне нужно выполнить интенсивную операцию на небольшом подмножестве этих точек, но мне нужно сначала выяснить, какие моменты мне нужно для выполнения этой интенсивной операции. Чтобы определить, какие точки мне нужны, они должны пройти ряд геометрических критериев.

Наиболее основные критерии заключаются в том, что они находятся на определенном расстоянии от конкретной точки. Второй наиболее базовый критерий заключается в том, содержатся ли они в круговом секторе (двумерный конус), выходящем из этой конкретной точки. (Изменить: эта операция вызывается регулярно с другой конкретной точкой каждый раз, но тот же набор из 2d точек.)

Моя первоначальная мысль заключалась в том, чтобы создать сетку, содержащую 2d точек, а затем итерацию вдоль конуса, захватывающего квадраты сетки, которые он пересекает. В зависимости от размера сетки он отфильтровывает подавляющее большинство ненужных 2d точек. К сожалению, встроенная система, над которой я работаю, сильно ограничена памятью, поэтому большой (по нашим стандартам, не любой) массив 2d будет слишком интенсивным для памяти.

Я пытаюсь исследовать использование деревьев KD для ускорения вычисления, но мне не удалось найти алгоритм, связанный с секторами окружности и kd-деревьями.

Существует ли эффективный алгоритм поиска того, какие 2d-точки лежат внутри сектора круга?

Просто заметьте, что наша конкретная система медленна как по математике с плавающей запятой, так и по тригонометрии, поэтому решение, которое включает в себя меньше, превосходит тот, который требует многого.

Ответ 1

Можно проверить, находится ли точка внутри сектора с целочисленной арифметикой и основными операциями сложения, вычитания и умножения.

Чтобы точка находилась внутри кругового сектора она должна отвечать следующим тестам:

Он должен располагаться против часовой стрелки от начала "руки" сектора.
Он должен располагаться по часовой стрелке от конечного рычага сектора.
Он должен быть ближе к центру круга, чем радиус сектора.

Проверки по часовой стрелке

Чтобы проверить, равен ли вектор v2 по часовой стрелке другому вектору v1, выполните следующие действия:

Найдите против часовой стрелки нормальный вектор v1. Нормальный вектор находится под углом 90 градусов к исходному вектору. Это прямое выполнение: если v1=(x1,y1), то норма против часовой стрелки n1=(-y1,x1).
Найдите размер проекции v2 на нормальный. Это можно сделать, вычислив dot product 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() на них, чтобы узнать.
Обратите внимание, что, хотя все это можно сделать с помощью целочисленной арифметики, как в радиусе, так и в тестах по часовой стрелке используется больший диапазон чисел из-за возведения в квадрат х и у и их умножения. Не забудьте использовать целые числа с достаточным количеством бит для хранения результатов.

Ответ 2

Я знаю, что вам не нужна тригонометрия, но вы можете преобразовать каждую точку (в подмножество) в ее полярные координаты (где происхождение - ваша конкретная точка) и порог r,theta, где r < R и T1 < theta < T2 соответствуют к сектору. Это, безусловно, эффективная память!