Polygon.contains? bug

[xsxVeNxsx]

arr = [Geometry::Point.new(1.6, 1.0), Geometry::Point.new(1.6, 2.0), 
     Geometry::Point.new(1.2, 2.0), Geometry::Point.new(1.2, 1.0)]
point = Geometry::Point.new(1.5, 1.5)
result = Geometry::Polygon.new(arr).contains?(point)

Result = true. It's ok. But:

arr = [Geometry::Point.new(1.6, 1.0), Geometry::Point.new(1.6, 2.0),
     Geometry::Point.new(1.2, 2.0), Geometry::Point.new(1.2, 1.0)]
point = Geometry::Point.new(1.5, 1.5)
result = Geometry::Polygon.new(arr).contains?(point)
(0..100).each{result &&= Geometry::Polygon.new(arr).contains?(point)}

result = false

[DanielVartanov]

Thanks for reporting a very interesting bug. I'll investigate what's happening there.

[seangransee]

Yes, it appears that Point.contains? is nondeterministic. Here's another example:

point = Geometry::Point.new(509, 553)

polygon = Geometry::Polygon.new([
  Geometry::Point.new(297, 581),
  Geometry::Point.new(464, 414),
  Geometry::Point.new(545, 495),
  Geometry::Point.new(383, 662)
])

results = Array.new(10000).map do
  polygon.contains?(point)
end

puts "contains? returned true #{results.count(true)} times"
puts "contains? returned false #{results.count(false)} times"

Running this prints the following output for me:

contains? returned true 515 times
contains? returned false 9485 times

I suspect this has something to do with the randomness introduced in point_in_polygon.rb line 54.

In my application, I've monkey-patched the Point.contains? method with this algorithm: PNPOLY - Point Inclusion in Polygon Test.

[DanielVartanov]

Hey @seangransee, can you please form a PR with your patch? This problem is indeed very serious.

[seangransee]

Sure! I'll try to take care of it sometime this week.

[DanielVartanov]

Thanks in advance!

[seangransee]

PR created in #17. It's not perfect yet, but it's a starting point.