Какой алгоритм я могу использовать для определения точек в полукруге?

У меня есть список двумерных точек, и я хочу получить, какие из них попадают в полукруг.

Первоначально форма цели была прямоугольником, выровненным с осью x и y. Таким образом, текущий алгоритм сортирует пары по их координатам X и двоичным поискам до первого, который может попадать в прямоугольник. Затем он последовательно повторяется по каждой точке. Он останавливается, когда он попадает на тот, который находится за пределами верхней и нижней границы объекта X и Y целевого прямоугольника.

Это не работает для полукруга, так как вы не можете определить эффективные верхние/нижние границы x и y для него. Полукруг может иметь любую ориентацию.

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

Ответ 1

Проверка того, находится ли точка внутри или вне полукруга (или прямоугольника, если на то пошло), является постоянной операцией.

Проверка N точек лежит внутри или вне полукруга или прямоугольника O (N).

Сортировка ваших N баллов - O (N * lg (N)).

Асимптотически быстрее проверять все точки последовательно, чем сортировать, а затем быстро отбирать точки, основанные на двоичном поиске.

Это может быть один из тех случаев, когда то, что кажется быстрым и что быстро, - это две разные вещи.

ИЗМЕНИТЬ

Там также простейший способ проверить герметичность точки в полукруге без смещения с поворотами, преобразованиями и т.п.

Представьте полукруг как две компоненты:

отрезок от точки a до b, представляющий диаметр полукруга
ориентация либо слева, либо справа указывает, что полукруг находится либо слева, либо справа от сегмента линии ab при перемещении от a до б

Вы можете использовать правое правило, чтобы определить, находится ли точка внутри полукруга.

Затем некоторый псевдокод для проверки, если точка p находится в полукруге, например:

procedure bool is_inside:
    radius = distance(a,b)/2
    center_pt = (a+b)/2    
    vec1 = b - center_pt
    vec2 = p - center_pt
    prod = cross_product(vec1,vec2) 
    if orientation == 'left-of'
        return prod.z >= 0 && distance(center_pt,p) <= radius
    else
        return prod.z <= 0 && distance(center_pt,p) <= radius

Этот метод обладает дополнительным преимуществом: не использовать какие-либо триггерные функции, и вы можете устранить все квадратные корни по сравнению с квадратом расстояния. Вы также можете ускорить его, кэшируя вычисление "vec1", вычисление радиуса, вычисление center_pt и переупорядочивая пару операций, которые нужно выполнить заблаговременно. Но я пытался понять.

"cross_product" возвращает значение (x, y, z). Он проверяет, является ли z-компонента положительной или отрицательной. Это также можно ускорить, не используя истинный кросс-продукт и только вычисляя z-компонент.

Ответ 2

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

Затем вы можете рассматривать его как круг, игнорируя все отрицательные значения y, и просто проверяйте, используя квадратный корень из суммы квадратов X и Y, и посмотрите, меньше или равно радиусу.

Ответ 3

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

Если у вас есть GPU в вашем распоряжении, тогда есть больше способов сделать это. Например, используя буфер трафарета:

очистите буфер трафарета и установите операцию трафарета для увеличения
отрисуйте полукруг буфера трафарета
показать свои точки.
прочитайте пиксели и проверьте значения в своих точках.
точки, находящиеся внутри полуокружности, были бы увеличены дважды.

В этой статье описывается, как буферы трафаретов можно использовать в OpenGL.

Ответ 4

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

Ответ 5

Вы можете найти точки в круге и указать на одной стороне данного уклона, правильно?

Просто соедините два.

Ответ 6

Здесь часть функции, которую я написал, получает дугу для конуса для оружия в игре на основе плитки.

float lineLength;
float lineAngle;
for(int i = centerX - maxRange; i < centerX + maxRange + 1; i++){
    if(i < 0){
        continue;
    }
    for(int j = centerY -  maxRange; j < centerY + maxRange + 1; j++){
        if(j < 0){
            continue;
        }

        lineLength = sqrt( (float)((centerX - i)*(centerX - i)) + (float)((centerY - j)*(centerY - j)));
        lineAngle = lineAngles(centerX, centerY, forwardX, forwardY, centerX, centerY, i, j);

        if(lineLength < (float)maxRange){
            if(lineAngle < arcAngle){
                if( (float)minRange <= lineLength){ 
                    AddToHighlightedTiles(i,j);
                }
            }
        }
    }
}

Переменные должны быть самоочевидными, а функция углов линий принимает 2 линии и находит угол между ними. ForwardX и forwardY - это всего лишь одна плитка в правильном направлении от центра X и Y на основании того, на какой угол вы указываете. Их можно легко получить с помощью оператора switch.

float lineAngles(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
    int a = x2 - x1;
    int b = y2 - y1;
    int c = x4 - x3;
    int d = y4 - y3;

    float ohSnap = ( (a * c) + (b * d) )/(sqrt((float)a*a + b*b) * sqrt((float)c*c + d*d) );
    return acos(ohSnap) * 180 / 3.1415926545f;
}

Ответ 7

перевести центр дуги в начало
вычислить угол между осью ординат и конечными точками радиусов полуцикла
перевести рассматриваемую точку такими же dx, dy
вычислить расстояние от начала до переведенного x, y точки, если d > радиус окружности/дуги исключить
- вычислить угол между осью ординат и конечной точкой
- если угол не находится между начальной и конечной дугой полуциркуляции, устраните
Повторение точек должно быть внутри полукруга

Ответ 8

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

Я бы сделал это шагами...
1. Я бы посмотрел, если я в кругу... если да, посмотрите, на какой стороне круга.
2. Вычерчивая нормальный вектор, который исходит из вектора, сделанного полусферой. Я мог бы знать, стоит ли мне за или перед вектором... и если вы знаете, какая сторона - полусфера, а какая сторона - пустота... Это будет довольно легко найти, если вы находитесь в пределах полусфера. Вы должны сделать точечный продукт.

Я не уверен, достаточно ли это достаточно, но тест не должен быть таким трудным... В конце концов, вам нужно искать отрицательное или положительное значение... если он 0, вы на вектор полусферы, чтобы вы могли сказать, вне его или внутри полусферы.

Ответ 9

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

Существует несколько способов сделать это с помощью векторов. Вы можете масштабировать круг до единичного круга и использовать кросс-продукты и смотреть на результирующие векторы. Вы можете использовать точечные продукты и посмотреть, как потенциальная точка приземляется на другие векторы.

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

Изменить: я забыл, что полукругом всегда является половина круга. Я думал о любом произвольном участке круга.

Теперь, когда я вспомнил, что такое полукруг, вот как я это сделаю. Он похож на решение с stbuton, но он по-разному представляет полукругу.

Я представлял бы полукруг как единичный вектор, который делит пополам полукруг. Вы можете легко получить это из любого из векторов, которые указывают границу полукруг (потому что они находятся на 90 градусов от представления) путем замены x и y и отрицания одного из них.

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

Я сделал всю физику для Cool Pool (из Sierra Online). Все это делается в векторах и заполнено точками и крестами. Векторы решения бывают быстрыми. Прохладный пул смог работать на P60 и делал разумные разрывы и даже вращаться.

Примечание. Для решений, в которых вы проверяете sqrt (xx + yy), даже не делайте sqrt. Вместо этого держите квадрат радиуса вокруг и сравните с ним.

Ответ 10

Казалось бы, здесь будет работать простая схема.

Уменьшить количество точек в наборе, предварительно вычислив выпуклую оболочку. Только точки на выпуклой оболочке будут вносить вклад в любое взаимодействие с любой выпуклой ограниченной формой. Поэтому сохраните только подмножество точек по периметру корпуса.
Легко утверждать, что минимальный радиус, ограничивающий полукруг, должен иметь одно ребро (две точки) выпуклой оболочки, совпадающее по диаметру полукруг. Если некоторое ребро оболочки не лежит в диаметре, то существует другой полукруг меньшего диаметра, содержащий один и тот же набор точек.
Проверяйте каждый ребро последовательно. (У выпуклой оболочки часто имеется относительно немного ребер, так что это будет идти быстро.) Теперь это становится простой задачей минимизации 1-го уровня. Если мы решили предположить, что рассматриваемое ребро лежит на диаметре, то нам просто нужно найти центр сферы. Он должен лежать вдоль текущей линии, которую мы рассматриваем как диаметр. Так как функция положения точки вдоль диаметра тока, просто найдите точку, которая лежит дальше от номинального центра. Минимизируя это расстояние, мы находим радиус минимального полукруга вдоль этой линии как диаметр.

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

Ответ 11

Если ваши точки имеют целые координаты, самым быстрым решением может быть таблица поиска. Поскольку полукруг выпуклый, для каждой координаты y вы получаете фиксированный диапазон x, поэтому каждая запись в вашей таблице поиска дает максимальные и минимальные координаты X.

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

Чтобы рассчитать промежутки в первую очередь (если вам нужно сделать это многократно), вы, вероятно, захотите найти старую копию Michael Abrash Zen Graphics Programming. Это описал известный линейный алгоритм Брешенемаса и не очень известный алгоритм окружности Харденбурга. Нельзя слишком сложно комбинировать версии, ориентированные на диапазон, чтобы быстро вычислить промежутки для полукруг.

IIRC, Харденбург использует x ^ 2 + y ^ 2 = радиус ^ 2, но использует тот факт, что вы переходите через промежутки, чтобы избежать вычисления квадратных корней - я думаю, что он использует тот факт, что (x + 1) ^ 2 = x ^ 2 + 2x + 1 и (y-1) ^ 2 = y ^ 2 - 2y + 1, поддерживая текущие значения для x, y, x ^ 2 и (радиус ^ 2 - y ^ 2), поэтому каждый шаг требует только сравнения (это текущий x ^ 2 + y ^ 2 слишком большой) и несколько дополнений. Это сделано только для одного октанта (единственный способ обеспечить однопиксельные шаги) и расширен до полного круга через симметрию.

Как только у вас есть промежутки для полного круга, должно быть легко использовать Bresenhams, чтобы отрезать половину, которую вы не хотите.

Конечно, вы сделали бы все это, только если абсолютно уверены, что вам нужно (и что вы можете работать с целыми числами). В противном случае придерживайтесь stbuton.