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

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

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

"Возможно, они могут скот вызывать его, так как им выделили полный GPU им".

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

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

Эта статья описывает, как буферы шаблонов могут использоваться в OpenGL.

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

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

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

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

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 на основе того, в каком угле Вы указываете. Они могут быть получены легко с оператором переключения.

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

• переведите центр дуги к источнику
• вычислите угол между осью ординаты и конечными точками радиусов semi-cirlce
• переведите рассматриваемый вопрос тем же дуплексом, dy

• вычислите расстояние от источника до переведенного x, y точки, если d> радиус круга/дуги устраняет

  • вычислите угол между осью ординаты и конечной точкой
  • если угол не между запуском и конечной дугой semi-cirlce, устранить

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

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

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

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

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

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

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

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

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

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

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

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

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

Я сделал всю физику для Прохладного Пула (от Горной цепи Онлайн). Это все сделано в векторах, и это заполнено точками и крестами. Решения для векторов быстры. Прохладный Пул смог работать на P60, и сделал разумные повреждения и даже вращается.

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

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

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

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

If your points have integer co-ordinates, the fastest solution may be a lookup table. Since a semicircle is convex, for each y co-ordinate, you get a fixed range of x, so each entry in your lookup table gives maximum and minimum X co-ordinates.

Of course you still need to precalculate the table, and if your semicircle isn't fixed, you may be doing that a lot. That said, this is basically one part of what would once have been done to render a semicircle - the full shape would be rendered as a series of horizontal spans by repeatedly calling a horizontal line drawing function.

To calculate the spans in the first place (if you need to do it repeatedly), you'd probably want to look for an old copy of Michael Abrash's Zen of Graphics Programming. That described Bresenhams well-known line algorithm, and the not-so-well-known Hardenburghs circle algorithm. It shouldn't be too hard to combine the span-oriented versions of the two to quickly calculate the spans for a semi-circle.

IIRC, Hardenburgh uses the x^2 + y^2 = radius^2, but exploits the fact that you're stepping through spans to avoid calculating square roots - I think it uses the fact that (x+1)^2 = x^2 + 2x + 1 and (y-1)^2 = y^2 - 2y + 1, maintaining running values for x, y, x^2 and (radius^2 - y^2), so each step only requires a comparison (is the current x^2 + y^2 too big) and a few additions. It's done for one octant only (the only way to ensure single-pixel steps), and extended to the full circle through symmetry.

Once you have the spans for the full circle, it should be easy to use Bresenhams to cut off the half you don't want.

Of course you'd only do all this if you're absolutely certain that you need to (and that you can work with integers). Otherwise stick with stbuton.