Алгоритм многоугольника в прямоугольнике?

Question

У меня есть алгоритм, который может найти точку в заданном многоугольнике:

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y)
 {
     int i, j, c = 0;
     for (i = 0, j = npts-1; i < npts; j = i++) {
         if ((((yp[i] <= y) && (y < yp[j])) ||
             ((yp[j] <= y) && (y < yp[i]))) &&
             (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
             c = !c;
     }
     return c;
 }

учитывая это, как я могу проверить, находится ли он внутри прямоугольника, определяемого Ptopleft и Pbottomright вместо одной точки?

Спасибо

По сути, вы знаете, как в Adobe Illustrator можно перетаскивать, чтобы выделить все объекты, попадающие в прямоугольник выбора? ну, я имею в виду это. -

Answer 1

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

Answer 2

Как упоминалось ранее, для этой конкретной проблемы эта функция является избыточным.Однако, если вам необходимо его использовать, обратите внимание, что:
1. Он работает только для выпуклых многоугольников,
2. Массивы, содержащие вершины многоугольника, должны быть отсортированы так, чтобы последовательные точки в массиве относились к смежным вершинам.вашего многоугольника.
3. Для правильной работы вершины должны быть упорядочены в порядке «правила правой руки».Это означает, что когда вы начинаете «ходить» по краям, вы делаете только левые повороты.

Тем не менее, я думаю, что есть ошибка в реализации.Вместо:

// c initialized to 0 (false), then...
c = !c;  

у вас должно быть что-то вроде:

// c initialized to 1 (true), then...
// negate your condition:
if ( ! (....))
    c = 0;

Answer 3

РЕДАКТИРОВАТЬ: да, я неправильно понял вопрос. Если вы хотите убедиться, что многоугольник закодирован прямоугольником, выполните проверку для каждой точки многоугольника. Вы можете сделать это дешевле с минимальными / максимальными координатами x и y и проверяя, находится ли этот прямоугольник внутри прямоугольника запроса.

РЕДАКТИРОВАТЬ 2: Упс, означает горизонтальные, а не вертикальные края.

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

Answer 4

int isPointInRect( Point point, Point ptopleft, Point pbottomright) {

   float xp[2] ;
   xp[0] = ptopleft.x, 
   xp[1] = pbottomright.x;

   float yp[2] ;
   yp[0] = ptopleft.y ;
   yp[1] = pbottomright.y ;

   return CGlEngineFunctions::PointInPoly(2, xp, yp, point.x, point.y);
}