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

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

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

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

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

Есть ли эффективный алгоритм для нахождения того, что 2d-точки лежат внутри сектора круга?

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

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

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

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

    Чтобы точка была внутри a, она должна соответствовать следующим тестамОн должен располагаться против часовой стрелки от начала «рычага» сектораОн должен располагаться по часовой стрелке от конечного рычага сектораОн должен быть ближе к центру круга, чем радиус сектора

Тесты по часовой стрелке

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

  1. Найдите обычный вектор v1 против часовой стрелки. Нормальный вектор находится под углом 90 gradleусов к исходному вектору. Это прямолинейно : если v1=(x1,y1) , то норма против часовой стрелки равна n1=(-y1,x1) .

  2. Найдите размер проекции v2 на нормальный. Это можно сделать, вычислив точечный продукт v2 и нормальный.

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

  3. Если проекция представляет собой положительное число, то v2 устанавливается против часовой стрелки до v1. В противном случае v2 по часовой стрелке до v1.

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

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

Этапы могут быть объединены:

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

Радиус

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

 function isWithinRadius(v, radiusSquared) { return vx*vx + vy*vy <= 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 .

Скриншот

Пример исходного кода

         

Примечания, оговорки и ограничения

  1. Вы должны указать границы сектора в терминах векторов. На скриншоте выше, например, показан сектор, простирающийся между векторами (4,1) и (1,4).

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

  3. Логика здесь работает для секторов с внутренним углом менее 180 gradleусов. Если ваши сектора могут охватывать больший угол, вам придется его модифицировать.

  4. Кроме того, код предполагает, что вы знаете, какой из ограничивающих векторов сектора является «стартом» и который является «концом». Если вы этого не сделаете, вы можете запустить areClockwise() на них, чтобы узнать.

  5. Обратите внимание, что, хотя все это можно сделать с помощью целочисленной арифметики, как радиус, так и по часовой стрелке используют больший диапазон чисел из-за возведения в квадрат x и y и их умножения. Не забудьте использовать целые числа с достаточным количеством бит для хранения результатов.

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

  • Пересечение линии с прямоугольником AABB?
  • Эффективно находим пересечение переменного числа множеств строк
  • Пересечение двух списков в C #
  • Давайте будем гением компьютера.