Как эффективно проверить, находится ли точка внутри повернутого прямоугольника?

11

Часть ради оптимизации, часть для целей обучения, я позволю себе спросить: как наиболее эффективно проверить, находится ли 2D-точка Pвнутри повернутого 2D-прямоугольника XYZW, используя C # или C ++?

В настоящее время я использую алгоритм «точка в треугольнике», описанный в книге «Обнаружение столкновений в реальном времени» , и запускаю его дважды (для двух треугольников, составляющих прямоугольник, скажем, XYZ и XZW):

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2.Dot(v0, v0);
 float dot01 = Vector2.Dot(v0, v1);
 float dot02 = Vector2.Dot(v0, v2);
 float dot11 = Vector2.Dot(v1, v1);
 float dot12 = Vector2.Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

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

Louis15
источник
У вас много точек или много прямоугольников? Это первый вопрос, который вы должны задать себе, прежде чем пытаться оптимизировать такую ​​маленькую задачу.
Сэм Хоцевар
Хорошая точка зрения. У меня будет очень много очков, но еще больше прямоугольников для проверки.
Louis15
Связанный вопрос о нахождении расстояния от точки до повернутого прямоугольника . Это вырожденный случай этого (проверка только для расстояния, равного 0). Конечно, здесь будут применены оптимизации, которых нет.
Анко
Рассматривали ли вы поворот точки в системе отсчета прямоугольника?
Ричард Тингл
@RichardTingle На самом деле я не знал с самого начала. Позже я сделал, потому что я думаю, что это относится к одному из ответов, приведенных ниже. Но только для пояснения: в том, что вы предлагаете, после поворота точки на систему отсчета прямоугольников, нужно проверять включение только путем логических сравнений между max.x, min.x и т. Д.?
Louis15

Ответы:

2

Простая и понятная оптимизация состояла бы в изменении конечного условия в PointInTriangle:

bool PointInRectangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P) {
  ...
  if(u >= 0 && v >= 0 && u <= 1 && v <= 1)
      { return true; } else { return false; }
  }
}

код уже был в значительной степени PointInRectangle, было условие, (u + v) < 1чтобы проверить, не находится ли он во «втором» треугольнике прямоугольника.

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

float isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) );
}
bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
    return (isLeft(X, Y, P) > 0 && isLeft(Y, Z, P) > 0 && isLeft(Z, W, P) > 0 && isLeft(W, X, p) > 0);
}
wondra
источник
Superb. Я не знаю, нравится ли мне больше ваше предложение, которое действительно быстрее и намного элегантнее моего, или мне нравится больше, что вы заметили, что мой код PointInTri может легко стать PointInRec! Спасибо
Louis15
+1 за isLeftметод. Он не требует триггерных функций (как Vector2.Dotи), что значительно ускоряет процесс.
Анко
Кстати, нельзя было подправить код (не тестировал; не знаю как на этом компьютере), включив isLeft непосредственно в основную функцию и заменив операторы "&&" на "||" через обратную логику? public static bool PointInRectangle(Vector2 P, Vector2 X, Vector2 Y, Vector2 Z, Vector2 W) { return !(( (Y.x - X.x) * (P.y - X.y) - (P.x - X.x) * (Y.y - X.y) ) < 0 || ( (Z.x - Y.x) * (P.y - Y.y) - (P.x - Y.x) * (Z.y - Y.y) ) < 0 || ( (W.x - Z.x) * (P.y - Z.y) - (P.x - Z.x) * (W.y - Z.y) ) < 0 || ( (X.x - W.x) * (P.y - W.y) - (P.x - W.x) * (X.y - W.y) ) < 0 ); }
Louis15
1
@ Louis15 Не думаю, что тебе нужно - и &&, и || прекратит выполнение дальнейших утверждений, если будет найден один отрицательный / положительный результат (или была другая причина?). Объявление isLeftвстроенного компилятора сделает для вас нечто похожее (и, вероятно, лучше, чем вы могли бы, потому что инженеры, пишущие компилятор, лучше знали процессоры, выбирая любой из самых быстрых вариантов), делая ваш код более читабельным с тем же или лучшим эффектом.
вондра
8

Редактировать: Комментарий ОП скептически относился к эффективности предлагаемой проверки отрицательной круговой границы для улучшения алгоритма, чтобы проверить, находится ли произвольная 2D-точка в повернутом и / или движущемся прямоугольнике. Немного покопавшись в моем 2D игровом движке (OpenGL / C ++), я дополняю свой ответ, предоставляя тест производительности моего алгоритма по сравнению с текущими алгоритмами проверки точки-прямоугольника ОП (и их вариациями).

Первоначально я предложил оставить алгоритм на месте (так как он почти оптимален), но упростил с помощью простой игровой логики: (1) использование предварительно обработанного круга вокруг исходного прямоугольника; (2) сделать проверку расстояния и находится ли точка в заданном круге; (3) использовать OP или любой другой простой алгоритм (я рекомендую алгоритм isLeft, как указано в другом ответе). Логика, лежащая в основе моего предложения, заключается в том, что проверка, находится ли точка внутри круга, значительно эффективнее, чем проверка границы повернутого прямоугольника или любого другого многоугольника.

Мой первоначальный сценарий для теста производительности состоит в том, чтобы запустить большое количество появляющихся и исчезающих точек (чье положение меняется в каждом игровом цикле) в ограниченном пространстве, которое будет заполнено примерно 20 вращающимися / движущимися квадратами. Я опубликовал видео ( ссылка на YouTube ) в целях иллюстрации. Обратите внимание на параметры: количество случайно появляющихся точек, число или прямоугольники. Я сравню со следующими параметрами:

OFF : простой алгоритм, предоставляемый OP, без отрицательных проверок границы круга

НА : использование обработанных (граничных) окружностей вокруг прямоугольников в качестве первой проверки исключения

ON + Стек : создание круговых границ во время выполнения в цикле в стеке

ON + квадратное расстояние : использование квадратного расстояния в качестве дополнительной оптимизации, чтобы избежать использования более дорогого алгоритма квадратного корня (Pieter Geerkens).

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

введите описание изображения здесь

Ось X показывает повышенную сложность, добавляя больше точек (и таким образом замедляя цикл). (Например, при 1000 случайно появляющихся точечных проверках в конфиденциальном пространстве с 20 прямоугольниками цикл повторяется и вызывает алгоритм 20000 раз.) Ось Y показывает время (мс), необходимое для завершения всего цикла с использованием высокого разрешения Таймер производительности. Более 20 мс было бы проблематично для приличной игры, так как для интерполяции плавной анимации не использовались бы высокие fps, и игра иногда могла бы выглядеть таким образом «бурной».

Результат 1 : Предварительно обработанный алгоритм с круговой границей с быстрой отрицательной проверкой в ​​цикле повышает производительность на 1900% по сравнению с обычным алгоритмом (5% от исходного времени цикла без проверки). Результат примерно пропорционален числу итераций в цикле, поэтому не имеет значения, проверяем ли мы 10 или 10000 случайно появляющихся точек. Таким образом, на этой иллюстрации можно безопасно увеличить количество объектов до 10 тыс. Без потери производительности.

Результат 2 : В предыдущем комментарии было высказано предположение, что алгоритм может быть быстрее, но интенсивнее использовать память. Однако обратите внимание, что сохранение числа с плавающей запятой для предварительно обработанного размера круга занимает всего 4 байта. Это не должно создавать никаких проблем, если ОП не планирует запускать одновременно более 100 000 объектов. Альтернативный и эффективный подход к памяти заключается в том, чтобы вычислить максимальный размер круга в стеке в цикле и позволить ему выходить из области действия при каждой итерации и, таким образом, практически не использовать память при неизвестной цене скорости. Действительно, результат показывает, что этот подход действительно медленнее, чем использование предварительно обработанного размера круга, но он все еще показывает значительное улучшение производительности примерно на 1150% (т.е. 8% от первоначального времени обработки).

Результат 3 : я дополнительно улучшаю алгоритм результата 1, используя квадратные расстояния вместо реальных расстояний и, таким образом, используя вычислительно дорогую операцию квадратного корня. Это лишь незначительно повышает производительность (2400%). (Примечание: я также пробую хеш-таблицы для предварительно обработанных массивов для приближений квадратных корней с похожим, но немного худшим результатом)

Результат 4 : я также проверяю перемещение / столкновение прямоугольников вокруг; однако это не меняет основных результатов (как и ожидалось), поскольку логическая проверка остается практически неизменной.

Результат 5 : я изменяю количество прямоугольников и нахожу, что алгоритм становится тем эффективнее, чем меньше переполнено пространство (не показано в демонстрации). Результат также несколько ожидаем, поскольку вероятность появления точки в крошечном пространстве между кругом и границами объекта уменьшается. С другой стороны, я пытаюсь увеличить количество прямоугольников слишком на 100 в одном и том же ограниченном крошечном пространстве и динамически изменять их размер во время выполнения внутри цикла (sin (итератор)). Это все еще работает очень хорошо с увеличением производительности на 570% (или 15% от первоначального времени цикла).

Результат 6 : я тестирую альтернативные алгоритмы, предложенные здесь, и нахожу очень небольшую, но незначительную разницу в производительности (2%). Интересный и более простой алгоритм IsLeft работает очень хорошо с повышением производительности на 17% (85% от первоначального времени расчета), но далеко от эффективности алгоритма быстрой отрицательной проверки.

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

Я предлагаю всегда пытаться тестировать любой сложный алгоритм на этапе разработки игры, поскольку простое рассмотрение простого кода может не раскрыть правду о фактической производительности во время выполнения. Предложенный алгоритм может даже не понадобиться здесь, если, например, кто-то хочет просто проверить, находится ли курсор мыши внутри прямоугольника или нет, или когда большинство объектов уже касаются. Если большинство проверок точек находятся внутри прямоугольника, алгоритм будет менее эффективным. (Однако тогда можно было бы установить границу «внутреннего круга» как вторичную отрицательную проверку.) Проверка границ круга / сферы очень полезна для любого приличного обнаружения столкновений большого числа объектов, которые, естественно, имеют некоторое пространство между ними. ,

Rec Points  Iter    OFF     ON     ON_Stack     ON_SqrDist  Ileft Algorithm (Wondra)
            (ms)    (ms)    (ms)    (ms)        (ms)        (ms)
20  10      200     0.29    0.02    0.04        0.02        0.17
20  100     2000    2.23    0.10    0.20        0.09        1.69
20  1000    20000   24.48   1.25    1.99        1.05        16.95
20  10000   200000  243.85  12.54   19.61       10.85       160.58
Majte
источник
Хотя мне нравился необычный подход и нравился справочник Да Винчи, я не думаю, что работа с кругами, не говоря уже о радиусе, была бы такой эффективной. Кроме того, это решение является разумным, только если все прямоугольники зафиксированы и известны заранее
Louis15
Положение прямоугольника не нужно фиксировать. Используйте относительные координаты. Думайте об этом также как это. Этот радиус остается неизменным, независимо от вращения.
Majte
Это отличный ответ; еще лучше, потому что я не думал об этом. Вы можете заметить, что достаточно использовать квадраты расстояний вместо реальных расстояний, избавляя от необходимости когда-либо вычислять квадратный корень.
Питер Гиркенс
Интересный алгоритм быстрого положительного / отрицательного тестирования! Проблема может заключаться в дополнительной памяти для сохранения предварительно обработанных ограничивающих кругов (и ширины), это может быть хорошей эвристикой, но также следует отметить, что она имеет ограниченное использование - в основном для случаев, когда память не имеет большого значения (прямоугольники статического размера на больших объектах = игровые объекты спрайта) и успеть на предварительную обработку.
Wondra
Отредактировано + добавлено тестирование производительности.
Majte
2

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

Peethor
источник
Хм, спасибо за предложение, но вращение и получение обратного вращения не кажется таким эффективным. На самом деле это вряд ли будет так же эффективно, как мое решение - не говоря уже о Уондре
Louis15
Можно заметить, что вращение трехмерной точки с матрицей - это 6 умножений, 3 сложения и один вызов функции. Решение @ wondra в лучшем случае эквивалентно, но гораздо менее ясное намерение; и более подвержены ошибкам обслуживания из-за нарушения DRY
Pieter Geerkens
@ Питер Geerkens пересечение претензий, как любое из моих решений нарушает DRY (и является ли DRY одним из ключевых принципов программирования? Никогда не слышал об этом до сих пор)? И самое главное, какие ошибки имеют эти решения? Всегда готов учиться.
Wondra
@wondra: DRY = Не повторяйся. Ваш фрагмент кода предлагает кодировать детали матрицы с помощью векторного умножения везде, где функциональность появляется в коде вместо вызова стандартного метода «приложение-матрица-вектор».
Питер Гиркенс
@PieterGeerkens, конечно, он предлагает только часть из этого - 1) у вас нет явной матрицы (выделение новой матрицы для каждого запроса сильно ухудшит производительность) 2) я использую только конкретный случай умножения, оптимизированный для этого случая, отбрасывая число общих один. Это операция низкого уровня, и она должна оставаться инкапсулированной, чтобы предотвратить непредвиденное поведение.
Wondra
1

У меня не было времени для этого, но я предложил бы сохранить матрицу преобразования, которая преобразует прямоугольник в выровненный по осям квадрат в диапазоне x и y от 0 до 1. Другими словами, сохраните матрицу, которая превращает один угол прямоугольника в (0,0), а противоположный в (1,1).

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

Но, как всегда, скорость этого алгоритма во многом зависит от вида проверок, которые вы ожидаете выполнить. Если большинство точек даже близко не расположены к прямоугольнику, выполнение простой проверки расстояния (например, (point.x - firstCorner.x)> aLargeDistance) может привести к значительному ускорению, а может даже замедлить работу, если почти все точки находятся внутри прямоугольника.

РЕДАКТИРОВАТЬ: Вот как будет выглядеть мой класс Rectangle:

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

Вот полный список моих тестов:

#include <cstdlib>
#include <math.h>
#include <iostream>

#include <sys/time.h>

using namespace std;

class Vector2
{
public:
    float _x;
    float _y;

    Vector2()
    :_x(0)
    ,_y(0)
    {}

    Vector2(float p_x, float p_y)
        : _x (p_x)
        , _y (p_y)
        {}

    Vector2 operator-(const Vector2& p_other) const
    {
        return Vector2(_x-p_other._x, _y-p_other._y);
    }

    Vector2 operator+(const Vector2& p_other) const
    {
        return Vector2(_x+p_other._x, _y+p_other._y);
    }

    Vector2 operator*(float p_factor) const
    {
        return Vector2(_x*p_factor, _y*p_factor);
    }

    static float Dot(Vector2 p_a, Vector2 p_b)
    {
        return (p_a._x*p_b._x + p_a._y*p_b._y);
    }
};

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2::Dot(v0, v0);
 float dot01 = Vector2::Dot(v0, v1);
 float dot02 = Vector2::Dot(v0, v2);
 float dot11 = Vector2::Dot(v1, v1);
 float dot12 = Vector2::Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

class Matrix3x3
{
public:
    Vector2 _columns[3];

    Vector2 transform(Vector2 p_in)
    {
        return _columns[0] * p_in._x + _columns[1] * p_in._y + _columns[2];
    }
};

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

void runTest(float& outA, float& outB)
{
    Rectangle r;
    r.setCorners(Vector2(0,0.5), Vector2(0.5,1), Vector2(0.5,0));

    int numTests = 10000;

    Vector2 points[numTests];

    Vector2 cornerA[numTests];
    Vector2 cornerB[numTests];
    Vector2 cornerC[numTests];
    Vector2 cornerD[numTests];

    bool results[numTests];
    bool resultsB[numTests];

    for (int i=0; i<numTests; ++i)
    {
        points[i]._x = rand() / ((float)RAND_MAX);
        points[i]._y = rand() / ((float)RAND_MAX);

        cornerA[i]._x = rand() / ((float)RAND_MAX);
        cornerA[i]._y = rand() / ((float)RAND_MAX);

        Vector2 edgeA;
        edgeA._x = rand() / ((float)RAND_MAX);
        edgeA._y = rand() / ((float)RAND_MAX);

        Vector2 edgeB;
        edgeB._x = rand() / ((float)RAND_MAX);
        edgeB._y = rand() / ((float)RAND_MAX);

        cornerB[i] = cornerA[i] + edgeA;
        cornerC[i] = cornerA[i] + edgeB;
        cornerD[i] = cornerA[i] + edgeA + edgeB;
    }

    struct timeval start, end;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        r.setCorners(cornerA[i], cornerB[i], cornerC[i]);
        results[i] = r.isInside(points[i]);
    }
    gettimeofday(&end, NULL);
    float elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outA += elapsed;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        resultsB[i] = PointInRectangle(cornerA[i], cornerB[i], cornerC[i], cornerD[i], points[i]);
    }
    gettimeofday(&end, NULL);
    elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outB += elapsed;
}

/*
 * 
 */
int main(int argc, char** argv) 
{
    float a = 0;
    float b = 0;

    for (int i=0; i<5000; i++)
    {
        runTest(a, b);
    }

    std::cout << "Result: " << a << " / " << b << std::endl;

    return 0;
}

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

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

Ларс Кокемор
источник
Интересно, но не забывайте, что вам нужно также применить вращение матрицы и к точкам. В моей игровой машине у меня есть операция гниения матрицы, и я могу позже протестировать ваш алгоритм. Что касается вашего последнего комментария. Затем вы также можете определить «внутренний круг» и сделать двойную отрицательную проверку, если точка находится вне внутреннего круга и внутри внешнего круга, как описано выше.
Majte
Да, это помогло бы, если бы вы ожидали, что большинство точек будет близко к середине треугольника. Я представлял ситуацию, подобную прямоугольной гоночной трассе, где вы, например, определяете прямоугольную дорожку, используя внешний прямоугольник, внутри которого должен находиться персонаж, и меньший внутренний прямоугольник, из которого он должен оставаться. В этом случае каждая проверка будет близка к границе прямоугольника, и эти проверки круга, вероятно, только ухудшат производительность. Конечно, это сконструированный пример, но я бы сказал, что это действительно может произойти.
Ларс Кокемор
Такие вещи могут случиться, да. Интересно, что такое сладкое пятно против алгоритма. В конце все сводится к вашей цели. Если у вас есть время, можете ли вы опубликовать свой код, используя сообщение ОП, и я могу сравнить ваш алгоритм? Посмотрим, верна ли ваша интуиция. Мне любопытно, как ваша идея работает против алгоритма IsLeft.
Majte