Массив, содержащий точки многоугольника.Можем ли мы пройти через его границу?

Question

Допустим, у нас есть массив, заполненный точками (x, y) (плитка), все в псевдокоде, которые образуют замкнутый и заполненный 2-мерный многоугольник. Как мы можем перебирать только те точки, которые образуют границу многоугольника?

Answer 1

Примените алгоритм упаковки подарков , также известный как марш Джарвиса, который будет выводить только те точки, которые образуют границу.

jarvis(S)

    // S is the set of points
    pointOnHull = leftmost point in S // which is guaranteed to be part of the CH(S)

   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]      // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|
         if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0]      // wrapped around to first hull point