Home » Odeon Blogs » Tudor, UI/UX Maestro »

Geo-location Point Inside Area

Geo-location Point Inside Area

I was curious to detect if a known point is inside a polygon. Turns out that the algorithm is far simpler than I thought. Now think of this point as a person inside a building. Is the guy really inside the building?

Here is the test which can be used as an example use case:

  1. import unittest

  2. 

  3. from insidePolygon import Point, is_inside_polygon

  4. 

  5. class insidePolyTest(unittest.TestCase):

  6. 

  7.     def test_defaults(self):

  8.         p = Point()

  9.         self.assertEquals(p.x, 0)

  10.         self.assertEquals(p.y, 0)

  11. 

  12.     def test_defaults(self):

  13.         p = Point(3, 4)

  14.         self.assertEquals(p.x, 3)

  15.         self.assertEquals(p.y, 4)

  16. 

  17.     def test_is_inside_poly(self):

  18.         poly = [Point(1,5), Point(5,5), Point(3,2), Point(1,5)]

  19.         outside_point = Point(1,2)

  20.         self.assertFalse(is_inside_polygon(poly, outside_point))

  21.         inside_point = Point(3,4)

  22.         self.assertTrue(is_inside_polygon(poly, inside_point))

  23. 

  24.     def test_geo_data(self):

  25.         london = Point(51.501249,-0.126271)

  26.         berlin = Point(52.540227,13.420944)

  27.         madrid = Point(40.427994,-3.70182)

  28.         rome = Point(41.922444,12.48436)

  29.         paris = Point(48.860589,2.350674)

  30.         bucharest = Point(44.443945,26.101341)

  31.         # triangle

  32.         poly = [london, berlin, madrid, london]

  33.         self.assertTrue(is_inside_polygon(poly, paris))

  34.         self.assertFalse(is_inside_polygon(poly, bucharest))

  35.         # rectangle

  36.         poly = [london, berlin, rome, madrid, london]

  37.         self.assertTrue(is_inside_polygon(poly, paris))

  38.         self.assertFalse(is_inside_polygon(poly, bucharest))

  39. 

  40. unittest.main()

Ok. So Paris is inside the triangle made by London, Berlin and Madrid. Bucharest isn't.

Europe

Might not be a deal-breaker for some, but I'm really disappointed by "check-in" applications. First because just stating that I'm present at a certain point on the globe is not fun. Secondly, if the application associates that point to a venue, it should better check if the person checking-in is really at that venue, maybe with a small margin of error, like a 500m radius. Why am I allowed to check-in 15.000 km away and get points for that? Yes, I'm talking about Foursquare-ish apps.

Here's the Python code for calculating this:

  1. class Point:

  2.     x = 0

  3.     y = 0 

  4. 

  5.     def __init__(self, x = 0, y = 0):

  6.         self.x = x

  7.         self.y = y

  8. 

  9.     def __str__(self):

  10.         return "(%s, %s)" % (self.x, self.y)

  11.     

  12. def max(a, b):

  13.     if a > b:

  14.         return a

  15.     return b

  16. 

  17. def min(a, b):

  18.     if a < b:

  19.         return a

  20.     return b

  21. 

  22. def is_inside_polygon(poly, point):

  23.     n = len(poly) - 1

  24.     counter = 0

  25. 

  26.     p1 = poly[0]

  27.     for i in range(0, n + 1):

  28.         p2 = poly[i % n]

  29.         if point.y > min(p1.y, p2.y):

  30.             if point.y <= max(p1.y, p2.y):

  31.                 if point.x <= max(p1.x, p2.x):

  32.                     if p1.y != p2.y:

  33.                         xinters = (point.y - p1.y) * (p2.x - p1.x)/(p2.y - p1.y) + p1.x

  34.                         if p1.x == p2.x or point.x < xinters:

  35.                             counter += 1

  36.         p1 = p2

  37.     if counter % 2 == 0:

  38.         return False

  39.     return True

If Elvis was using Foursquare or Koprol - the cool new Geolocation Social Network from Yahoo - we would have known when he left the building.


Categories: curiosity iphone mobile sparks

Discussion

  1. gorsky on Jul 25, 2011 - 12:47 said:

    ..or use GeoDjango ;)


  2. Javier E. Cabanillas Rodríguez on Jan 10, 2012 - 15:25 said:

    Hi, do you have the code in C#?
    Thanks a lot, my mail is javica18@hotmail.com




Leave a Comment :

(required)


(required)




(required)




(required)






Leave a Comment


Page generated in: 0.18s