• # It’s a markgraf… it’s a landgraf… it’s GeoGraf!

By · Sunday, August 11, 2013 · Tech

Yes, it’s GeoGraf! Strange visitor from another planet who came to Earth with powers and abilities to tell whether it’s Germany or Brazil that’s on the coast of Baltic Sea! …ok, I think I got carried away.

## The problem

Anyway, here at Wimdu we were tasked with the following problem: we had a vast amount of geographical shapes for countries and regions that didn’t know about each other. In order to offer more detailed suggestions to our users, we wanted to know which regions and countries were associated, i.e. what shapes are contained within other shapes.

Some of the shapes are not fully contained in others, but intersect only to some degree, so we also wanted to know the percentage of the containment.

## RGeo to the rescue!

As we mostly use this lovely language called Ruby, we decided to check out the RGeo gem – turns out it can be used to “perform standard spatial analysis operations such as finding intersections, creating buffers, and computing lengths and areas”. Isn’t finding intersections of countries and regions the thing we need? Well, why, it totally is!

To handle geometrical operations, RGeo uses the GEOS engine written in C++. Let’s try it out!

``````require 'rgeo'

factory = RGeo::Cartesian.preferred_factory()

baltic_sea_coords = [
[53.895438, 8.349609],
[54.082958, 21.269531],
[65.703800, 24.461059]
] # Well, everyone knows Baltic Sea is a triangle!

germany_coords = [
[47.071057, 9.635009],
[54.496365, 6.910400],
[54.953174, 14.29321]
] # Who would have thought, Germany's a triangle too!

def create_polygon_from(coords, factory)
factory.polygon(
factory.linear_ring(
coords.map { |coord| factory.point(*coord.reverse) }
)
)
end

baltic_sea_polygon = create_polygon_from(baltic_sea_coords, factory)
germany_polygon = create_polygon_from(germany_coords, factory)

baltic_sea_polygon.area # => 74.77094844188204
germany_polygon.area # => 28.032141370742576

baltic_sea_polygon.intersects?(germany_polygon) # => true
``````

Fantastic! Now let’s pretend that Baltic Sea is Chukotka! And by that I mean: let’s pretend it’s some place that wraps over the 180th meridian. I will just move `baltic_sea_coords` to the east by 160 degrees and subtract 360 degrees from any longitude that’s over 180 degrees (so for example 182 degrees would become -178 degrees):

``````chukotka_coords = [
[53.895438, 168.349609],
[54.082958, -178.730469],
[65.703800, -175.538941]
]
chukotka_polygon = create_polygon_from(chukotka_coords, factory)

chukotka_polygon.area # => 2016.9806115581184
baltic_sea_polygon.area # => 74.77094844188204``````

Why the difference? Please note the factory that we’ve initialized before:

``factory = RGeo::Cartesian.preferred_factory()``

No wonder a simple Cartesian coordinate system doesn’t consider a geographical meridian of 180 degrees, why would it? Instead, let’s use a different factory!

``factory = RGeo::Geographic.simple_mercator_factory``

A mercator projection is a simple way of projecting the surface of the Earth onto a flat surface. There are many more, but this one is enough for us.

Now, after regenerating the polygons using the new factory, we get:

``````germany_polygon.area # => 552096488499.9086
baltic_sea_polygon.area # => 1870855717943.564
chukotka_polygon.area # => 1870855717943.5645``````

As we see, the units are different, but Baltic Sea’s and Chukotka’s areas make much more sense now. But how is it achieved, I wonder? Let’s take a look at Chukotka’s polygon:

``````chukotka_polygon # =>
#<RGeo::Geographic::ProjectedPolygonImpl:0x3fdb85294384
"POLYGON ((
168.349609 53.895438,
181.269531 54.082958,
184.461059 65.7038,
168.349609 53.895438
))">``````

Oh, so internally RGeo actually uses only positive values, also over 180 degrees, to represent this polygon!
…but wait, so how will it deal with polygons that actually start with the negative longitude values? Let’s create a different Chukotka representation (the same points but with
a different starting one) and find out!

``````alternative_universe_chukotka_coords = [
[65.703800, -175.538941],
[53.895438, 168.349609],
[54.082958, -178.730469]
]

alternative_universe_chukotka_polygon = create_polygon_from(alternative_universe_chukotka_coords, factory) # =>
#<RGeo::Geographic::ProjectedPolygonImpl:0x3fdb85185740
"POLYGON ((
-175.538941 65.7038,
-191.650391 53.895438,
-178.730469 54.082958,
-175.538941 65.7038
))">

alternative_universe_chukotka_polygon.intersects?(chukotka_polygon) # => false``````

Eh, this isn’t good. But don’t worry, we will solve this problem as well.

## The Phantom Menace

Yes, it will be as good.

Our idea was to create our own wrapper class for RGeo
polygons with an `intersection` method that would not only
take into account the original shapes, but, if any of them
wraps around the 180th meridian, it would create a
counterpart with an offset of 360 or -360 degrees:

``````def initialize(coordinates, factory)
@rgeo_polygons = [create_polygon(coordinates, factory)]

end``````

YES A SHADOW POLYGON I TOLD YOU IT’S GONNA BE GOOD

``````def create_shadow_polygon_if_required(coordinates, factory)
if line_180(factory).intersects?(rgeo_polygons.first)
rgeo_polygons << create_polygon(coordinates, factory, longitude_offset: -360)
elsif line_minus_180(factory).intersects?(rgeo_polygons.first)
rgeo_polygons << create_polygon(coordinates, factory, longitude_offset: 360)
end
end``````

Yes, we need to check the shapes against both 180 and -180 degrees meridian; it’s the same problem – according to RGeo they’re not exactly the same thing.

And finally:

``````def intersection(other)
intersection = nil

rgeo_polygons.each do |polygon|
other.rgeo_polygons.each do |other_polygon|
intersection = polygon.intersection(other_polygon)
return intersection if intersection && !intersection.is_empty?
end
end
intersection
end``````

Ok, now that we have it ready, it’s time for a…

## Test-drive!

``````require 'geo_graf'

GeoGraf.intersections_for(
[
{
id: 'Baltic Sea',
polygon_coords: [
[53.895438, 8.349609],
[54.082958, 21.269531],
[65.703800, 24.461059]
]
},
{
id: 'Germany',
polygon_coords: [
[47.071057, 9.635009],
[54.496365, 6.910400],
[54.953174, 14.29321]
]
},
{
id: 'Poland',
polygon_coords: [
[54.491181, 14.326172],
[54.646227, 23.532715],
[49.090506, 23.906250]
]
},
{
id: 'Brazil',
polygon_coords: [
[-6.520001, -34.804688],
[1.215271, -69.257813],
[-33.002905, -52.910156]
]
}
]
)

# =>
[
{:id=>"Poland", :contained_area_percentage=>14, :container_id=>"Baltic Sea"},
{:id=>"Germany", :contained_area_percentage=>17, :container_id=>"Baltic Sea"}
]``````

## Sweet!

The gem is available on RubyGems and GitHub. Contributions are most welcome!

That’s it, cats and kittens! Thanks for tuning in!