CODEWITHSUNDEEP
ruby
Alexander Joseph Norton
Alexander Joseph Norton

Reputation: 153

creating polygon object for geofencing ruby

In Ruby I want to write a Polygon object that will take an array of points in longitude and latitude (each point connecting to the next one in array order). Now my main question is what is the best way to go about representing the edges (lines) between the two points so that I can then plugin a point and see if its inside or outside the polygon?

Is there a gem that easily adds this functionality?

This is all the code I have written so far

class Polygon
  attr_reader :vertices
  def initialize(vertices)
    @vertices = vertices
  end
end

Upvotes: 1

Views: 838

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110755

Here's one way to determine if a given point is inside a convex polygon (or on an edge). (Note that the OP confirmed in a comment on the question that the polygons are convex.)

Code

def inside?(vertices, test_point)
  vs = vertices + [vertices.first]
  xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e|
    e.to_f/vertices.size } # interior point
  x, y = test_point
  vs.each_cons(2).all? do |(x0,y0),(x1,y1)|
    if x0 == x1 # vertical edge
      (xi > x0) ? (x >= x0) : (x <= x0)
    else
      k, slope = line_equation(x0,y0,x1,y1)
      (k + xi*slope > yi) ? (k + x*slope >= y) : (k + x*slope <= y)
    end
  end  
end
    
def line_equation(x0,y0,x1,y1)
  s = (y1-y0).to_f/(x1-x0)
  [y0-s*x0, s]
end

I have assumed the polygon is not a straight line (i.e., all vertices are not co-linear).

Example

vertices = [[5,1],[2,4], [2,8], [6,10], [9,6]]

inside?(vertices, [6,7]) #=> true
inside?(vertices, [9,9]) #=> false
inside?(vertices, [5,1]) #=> true

Explanation

Here's a graph of the polygon in the example.

enter image description here

Each edge of the polygon, if extended infinitely in both directions, forms a line that divides the plane into two parts. For a given point to be within the polygon (including points on edges), it must be on the sides of all of the lines formed by the edges that contain the polygon.

In the example, arrows indicate the applicable sides for lines going through [5,1] and [2,4], and through [2,4] and [2,8]. The equation for the line through [5,1] and [2,4] is found to be:

y = 6.0 - x

Points on either side of this line are therefore given by 6.0 - x <= y and 6.0 - x >= y. To determine which inequality applies for each edge, we need an interior point of the polygon. Since it's convex, many convex combinations of the vertices would do. If, for example, no three consecutive vertices were co-linear, we could use, say, the average of any two non-adjacent vertices. I have chosen to use the point that is the average of all the vertices, which will be an interior point even if three or more (but not all) consecutive vertices are co-linear:

xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e|
           e.to_f/vertices.size }
  #=> [4.8, 5.8]

Returning now to the line that passes through the first two vertices, we see that:

6.0 - x = 6.0 - 4.8 = 1.2 => (1.2 < 5.8) => true

Hence, the interior point lies in the half-space given by:

6 - x <= y

We therefore apply the following test to see if the point of interest, [6,7], lies within this half-space:

6.0 - 6.0 = 0 <= 7.0

It does, as does the point [9,9]. If we were to consider the point [2,2], we would find:

6.0 - 2.0 = 4.0 > 2.0

so would conclude the opposite, and return false from inside?.

Now consider the line passing through [6,10] and [9,6], whose equation is:

y = 18.0 - 1.333*x

As

18.0 - 1.33*xi => 18.0 - 1.333*4.8 = 11.6 => (11.6 < 5.8) => false

The half-space associated with this line that contains the polygon is therefore given by the inequality:

18.0 - 1.333*x >= y

We can use this inequality to test if points fall within this half-space. For [6,7]:

18.0 - 1.333*6 #=> (10.0 >= 7) #=> true

For [9,9]:

18.0 - 1.333*9 #=> (6.0 >= 7) #=> false

Upvotes: 3

Sujeev
Sujeev

Reputation: 306

The Accepted answer did not work for me, however after searching more I found this solution, which I converted into Ruby:

def inside?(vertices, test_point)
    sides = vertices.count - 1
    j = sides - 1
    point_status = false
    x, y = test_point
    vertices.each_with_index do |item_i, index|
        item_j = vertices[j]
        if item_i.y < y && item_j.y >= y || item_j.y < y && item_i.y >= y
            if item_i.x + (y - item_i.y) / (item_j.y - item_i.y) * (item_j.x - item_i.x) < x
                point_status = !point_status
            end
        end
        j = index
    end
    point_status
end

The original post is at: https://www.codeproject.com/Articles/62482/A-Simple-Geo-Fencing-Using-Polygon-Method

The Poster has also used another source which is: http://alienryderflex.com/polygon/

Hope this helps someone.

Upvotes: 2

Related Questions