eXorithm – Execute Algorithm: View / Run Algorithm point_in_polygon

Logo Beta

function point_in_polygon ($point, $polygon_points

{

  // check points

  if ((count$polygon_points)%2)!=0) {

    throw new Exception'The points must be a list like x1, y1, x2, y2, etc. The number of points therefore must be divisible by two.');

  }

  

  // count the number of times a flat line originating from the point and moving right crosses

  // the edges of the polygon -- even number: outside polygon, odd number: inside polygon

  $ints = 0;

  

  $count = count$polygon_points);

  

  $x = $point[0];

  $y = $point[1];

  

  for ($i=2;$i<=$count$i$i+2) {

    $vertex1x = $polygon_points$i-2]; 

    $vertex1y = $polygon_points$i-1]; 

    $vertex2x = $polygon_points$i % count$polygon_points)];

    $vertex2y = $polygon_points[($i+1) % count$polygon_points)];

    // boundary condition: if the point is one of the vertices then we are inside

    if (($x == $vertex1x) && ($y == $vertex1y)) {

      return true;

    }

    if ($vertex1y == $vertex2y) { // horizontal edge

      // boundary condition: if point is on a horizontal polygon edge then we are inside

      if (($vertex1y == $y) && ($x > min$vertex1x, $vertex2x)) && ($x < max$vertex1x, $vertex2x))) {

        return true;

      }

    } else {

      if (($y > min$vertex1y, $vertex2y)) && ($y <= max$vertex1y, $vertex2y)) && ($x <= max$vertex1x, $vertex2x))) { 

        $xinters = ($y - $vertex1y) * ($vertex2x - $vertex1x) / ($vertex2y - $vertex1y) + $vertex1x; 

        // boundary condition: if point is on the polygon edge then we are inside

        if ($x == $xinters) {

          return true;

        }

        if ($x < $xinters) { 

          $ints++; 

        }

      } 

    } 

  }

  

  // if line crosses edges even number of times, then we are outside polygon

  if (($ints % 2) == 0) {

    return false;

  } else {

    return true;

  }

}