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

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 - очень умный способ иметь дело с круговым списком, который обертывается к началу; Я никогда этого не видел.