I need to process millions of latitude/longitude points every day to see if they are located within a defined lat/lon bounded polygon. The polygon may be rectangular, or it may be some irregular 3.. n sided shape. The points of the polygons will all be straight lines between points defined by lat/lon, no curves to complicate things. Allowing for great circle would be great. Many of the polygons will transit the anti-meridian or meridian. Every approach that I have tried so far fails with anti-meridian crossing and some don't handle meridian crossings.

I'm working mostly with node.js which uses the Javascript language, sometimes I use Python.

There do not appear to be any proven or well documented JavaScript wrappers for libraries like OGR. OGR is available for Python but my development work is mostly moving away from Python toward Node.js

I would appreciate it if someone could show me an algorithm (in the form of JavaScript or pseudo code) that can do this point in polygon operation.

I'm completely useless with mathematics and probably not trainable at this point so classical math notation will fly directly over my head.

The math functions that are available in my environment include all the standard geometry elements (a full list of available math functions can be seen at this link

I don't expect anyone to write code for me, but I'm hoping that someone can show me an algorithmic example in the pseudo-code like form of: (ignore the content, it's meaningless)

c = atan2(lon) * 4800
ca = sin(c)  

Something like that would be really helpful.

  • $\begingroup$ Not sure you will find this useful, but here it goes. Try looking at cs.haifa.ac.il/~gordon/plane.pdf. IF you are working with convex polygons then your computations will be a breeze to calculate(compared to concave polygons). $\endgroup$ – ReverseFlow Sep 2 '14 at 6:18
  • $\begingroup$ Thanks for the link, but as I feared, the article flew directly over my head, pausing only to express disdain for my lack of math knowledge. I couldn't even get close to seeing how the content would apply to my need :-( $\endgroup$ – RoyHB Sep 2 '14 at 6:21
  • $\begingroup$ Essentially, define some point on your coordinates to be the center. Select your points to be the edge of the convex polygon, and get the equation for the convex hull. Test points on this equation, if it passes they are in your polygon if not ditch them out. Look at 3 in en.wikipedia.org/wiki/Convex_hull. $\endgroup$ – ReverseFlow Sep 2 '14 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.