Помогите с этим алгоритмом

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

Моя единственная проблема в том, что она предполагает странное правило намотки. Под этим я подразумеваю, что если многоугольник самопересекающийся, определенные части, которые он считал бы «пустыми», вернутся как ложные. Что бы мне понадобилось, даже если оно само пересекается, все, что находится внутри многоугольника, вернет true.

Спасибо

Answer 1

Осторожно : этот ответ неправильный . У меня нет времени, чтобы исправить это прямо сейчас, но посмотрите комментарии.

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

c = !c;

Таким образом, четное количество пересечений означает четное количество переключений, поэтому c будет 0 в конце. Нечетное количество пересечений означает нечетное количество переключателей, поэтому c будет равно 1.

Вместо этого вы хотите установить флаг c, если любое пересечение происходит:

c = 1;

И для правильной меры вы можете затем полностью исключить c и досрочно завершить:

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y)
 {
     int i, j;
     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]))
             return 1;
     }
     return 0;
 }

Answer 2

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

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

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y) 
 { 
     int i, j;
     bool hasSegmentLeft = false;
     bool hasSegmentRight = false;
     for (i = 0, j = npts-1; i < npts; j = i++) { 
         if ((((yp[i] <= y) && (y < yp[j])) || 
             ((yp[j] <= y) && (y < yp[i]))))
         {
             if (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])
             {
                 hasSegmentRight = true;
                 if (hasSegmentLeft)  // short circuit early return
                     return true;
             }
             else
             {
                 hasSegmentLeft = true;
                 if (hasSegmentRight)  // short circuit early return
                     return true;
             }
     } 
     return hasSegmentLeft && hasSegmentRight; 
 }

P.S. эта конструкция оператора for является очень умным способом работы с циклическим списком, который переносится в начало; Я никогда не видел этого раньше.