point_in_polygon

point_in_polygon.rb

class Point
  attr_accessor :x, :y
  def initialize(x, y)
    @x = x
    @y = y
  end
end

# >0 left
# =0 on line
# < 0 right
def direction(line_start_point, line_end_point, point)
  (line_end_point.x - line_start_point.x) * (point.y - line_start_point.y) - (point.x - line_start_point.x) * (line_end_point.y - line_start_point.y)
end

# Edge Crossing Rules
# 1. an upward edge includes its starting endpoint, and excludes its final endpoint;
# 2. a downward edge excludes its starting endpoint, and includes its final endpoint;
# 3. horizontal edges are excluded
# 4. the edge­ray intersection point must be strictly right of the point P.

def cn_poly(point, polygon_points, edge_count)
  cross_number_count = 0
  (edge_count).times do |i|
    if (polygon_points[i].y <= point.y && polygon_points[i + 1].y > point.y) || # upward edge
      (polygon_points[i].y > point.y && polygon_points[i + 1].y <= point.y) # downward edge
      vt = (point.y - polygon_points[i].y).to_f / (polygon_points[i + 1].y - polygon_points[i].y)
      if point.x < polygon_points[i].x + vt * (polygon_points[i + 1].x - polygon_points[i].x)
        cross_number_count += 1
      end
    end
  end
  puts "crossing number counter: #{cross_number_count}, point in polygon? #{cross_number_count.odd?}"
  cross_number_count.odd?
end

def wn_pn_poly(point , polygon_points, edge_count)
  winding_number_count = 0

  edge_count.times do |i|
    if polygon_points[i].y <= point.y && polygon_points[i + 1].y > point.y && direction(polygon_points[i], polygon_points[i+1], point) > 0
      winding_number_count += 1
    elsif polygon_points[i].y > point.y && polygon_points[i + 1].y <= point.y && direction(polygon_points[i], polygon_points[i+1], point) < 0
      winding_number_count -= 1
    end
  end
  puts "winding number counter: #{winding_number_count}, point in polygon? #{winding_number_count != 0}"
  winding_number_count != 0
end

polygon1 = [
  Point.new(1, 0),
  Point.new(2, 1),
  Point.new(4, 2),
  Point.new(5, 0),
  Point.new(4, -2),
  Point.new(3, 1),
  Point.new(2, -2),
  Point.new(1, 0)
]

polygon2 = [
  Point.new(2, 0),
  Point.new(2, 2),
  Point.new(0, 2),
  Point.new(0, 0),
  Point.new(2, 0)
]

polygon3 = [
  Point.new(0,0),
  Point.new(7,0),
  Point.new(7,4),
  Point.new(1,4),
  Point.new(1,3),
  Point.new(5,3),
  Point.new(5,2),
  Point.new(4,2),
  Point.new(4,5),
  Point.new(0,5),
  Point.new(0,0),
]

polygon4 = [
  Point.new(0,0),
  Point.new(7,0),
  Point.new(7,4),
  Point.new(4,4),
  Point.new(4,5),
  Point.new(0,5),
  Point.new(0,0),
]

test_point1 = Point.new(2, 3.5)
test_point2 = Point.new(4.5, 2.5)

wn_pn_poly(test_point1, polygon3, 10)
cn_poly(test_point1, polygon3, 10)

# wn_pn_poly(test_point, polygon4, 6)
# cn_poly(test_point, polygon4, 6)