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

Question

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

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

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

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

Answer 1

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

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

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

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

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

EDIT

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

Представляет полукруг как две составляющие:

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

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

Затем некоторый псевдокод для проверки, находится ли точка 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-компонент.

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

Просто объедините их.

Answer 6

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

Answer 7

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

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

Во-первых, чтобы рассчитать промежутки (если вам нужно делать это несколько раз), вам, вероятно, стоит поискать старую копию программирования дзен-графики Майкла Абраша. Это описало хорошо известный линейный алгоритм Брезенхамса и не очень известный алгоритм окружности Харденбурга. Не должно быть слишком сложно объединить ориентированные на промежутки версии двух, чтобы быстро рассчитать пролеты для полукруга.

IIRC, Харденбург использует x ^ 2 + y ^ 2 = radius ^ 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 слишком большим) и нескольких дополнений. Это сделано только для одного октанта (единственный способ обеспечить однопиксельные шаги) и расширено до полного круга посредством симметрии.

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

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

Answer 8

Может показаться, что здесь будет работать простая схема.

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

2. Можно легко утверждать, что ограничивающий полукруг минимального радиуса должен иметь одно ребро (две точки) выпуклой оболочки, совпадающее по диаметру полукруга. То есть, если какой-то край корпуса не лежит в диаметре, то существует другой полукруг меньшего диаметра, который содержит тот же набор точек.

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

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

Answer 9

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

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

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

---

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

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

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

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

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

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

Answer 10

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

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

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