Точка на оси выровненного прямоугольника?

Question

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

Учитывая точку х, у Какой самый быстрый способ узнать, если x, y находится внутри прямоугольника? Я буду делать много из них, поэтому скорость важна.

Answer 1

Вот как я обычно это делаю. Учитывая точку, которая находится за пределами прямоугольника, это будет делать меньше тестов в 3 из 4 случаев. И иногда проводится только один тест.

if(point.x < rect.x) return false;
if(point.y < rect.y) return false;
if(point.x >= rect.x + rect.width) return false;
if(point.y >= rect.y + rect.height) return false;
return true;

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

Answer 2

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

Во-первых, используя компилятор, который знает инструкции Intel SSE, тест, который правильно комбинирует & и &&, немного быстрее. Это объединяет два теста в один, но ускоряет вторые два теста:

if((p.x>=r.lx)&(p.x<=r.hx)&&(p.y>=r.ly)&(p.y<=r.hy))
    ptisinrect=true;

В настоящее время компиляция с использованием 128-битных инструкций SSE выполняется быстрее всех &&, но использование 256-битной настройки AVX2 было медленнее, даже со всеми &.

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

Итак, взгляните на этот упрощенный пример не векторизованного кода, который ищет «подсчитать» пункты и завершает работу, если найдено достаточно:

for(unsigned a=0;a<n;++a)
{
    if((pp[a].x>=r.lx)&&(pp[a].x<=r.hx)&&(pp[a].y>=r.ly)&&(pp[a].y<=r.hy))
    {
        ++found;
       if(found>count)
            return true;
    }

}

Следующий код является примером того же самого, он только векторизует поиск от 0 до n узлов, но по-прежнему завершает работу, когда найдены точки подсчета в прямоугольнике. Обратите внимание, что этот код может иметь доступ на чтение 32 точек после n, поэтому массив должен быть выделен с 32 дополнительными точками пространства:

typedef struct ab
{
    int64_t a[4];
};
typedef struct{
union{
    ab ab;
    int8_t o[32];
    };
}xmmb;
xmmb o;
for(unsigned i=0;i<n;i+=32)
{
    for(unsigned a=0;a<32;++a)
    {
        o.o[a]=((pp[i+a].x>=r.lx)&(p[i+a].x<=r.hx)&(p[i+a].y>=r.ly)&(p[i+a].y<=r.hy));
    }

    for(unsigned kk=0;kk<4;++kk)
    {
        if(o.ab.a[kk])
       for(unsigned a=kk<<3;a<(kk+1)<<3;++a)
       {
            if(o.o[a]) 
            {
                if(i+a<n)
                {
                    ++found;
                    if(found>count)
                        return true;
                }
            }
        }
    }
}

Несмотря на то, что он выглядит довольно странно, этот код НАМНОГО быстрее, чем в предыдущем примере! Он выполняет тесты ptrect в векторно-параллельном режиме и сохраняет значения true / false в массиве из 32 8-битных байтов. Затем он проверяет 8 из них за раз (таким образом, объединение с 4 64-битными), чтобы сохранить тесты. Затем просматривает все, которые имеют истинное значение, и добавляет их в счетчик.

Опять же, обратите внимание, что это работает только с 128-битным SSE и в настоящее время (февраль 2015 г.) медленнее при компиляции для 256-битного AVX2, поэтому используйте ключи или прагмы, чтобы сохранить его SSE Наконец, в этом коде могут быть синтаксические ошибки и тому подобное, потому что ввод его в этот формат был непростым делом: D

теги: быстрая точка, быстрая точка, точная точка в прямоугольнике

Answer 3

В C ++ (можно тривиально перевести на C):

bool pointInRectangle( Point const & p, Rectangle const & r ) {
    return 
        ((r.x <= p.x) && (p.x <= (r.x + r.width ))) &&
        ((r.y <= p.y) && (p.y <= (r.y + r.height)));
}

Answer 4

if (p.x > x && p.y > y && p.x < x+width && p.y < y+height)

Это должно быть лишь несколько инструкций по сборке.

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

Answer 5

Если вы ориентируетесь на конкретный процессор, например, x86, вы можете использовать SIMD (то есть SSE), чтобы выполнить очень быстрый тест без ответвлений.Хитрость заключается в том, чтобы использовать 4 x 32 битных представления для представления прямоугольника, который отображается в вектор SIMD (он должен иметь размер 16 байтов и выравнивание по 16 байтов).