1

I have a program that takes in a user input of three or more pairs of longitude and latitude. I am trying to find all the intersected/bounded quadrilateral coordinates in a table (each quadrilateral has 4 pairs of longitudes and latitudes) by the polygon constructed with the inputted coordinates.

It needs to cover the whole Earth (both poles) and be as precise as possible.

I tried converting it the spherical coordinates (using a fixed height), but then had no idea what to do next.

I am pretty sure this has been done before, but I can't find it by Googling.

I am using Java, but Python would work too.

I found a way to check whether the polygons intersect if they are Cartesian.

any help would be appreciated!

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
Mark
  • 11
  • 1
  • Have you looked at [spherical trigonometry](http://en.wikipedia.org/wiki/Spherical_trigonometry)? – toto2 Jul 26 '11 at 13:54
  • Note that a polygon on a sphere doesn't define an inside an outside - it just partitions the sphere into two pieces. You need more information to decide which part is 'inside'. – Spacedman Jul 26 '11 at 15:04

1 Answers1

2

If the points are in a database, you can use a spatial index to this. It is pretty easy to do a brute force intersect across all your polygons, but this would take a long time. Mysql, Oracle and SQLServer all have spatial extensions that allow you to create spatial indexes and do contains functions against them. This is probably the easiest way to go if you do not mind the DB load.

http://dev.mysql.com/doc/refman/5.5/en/spatial-extensions.html

If you want to do it all in Java, then you might want to look for an R-tree implementation. It is a way to create a B-tree like structure using rectangles and will make it easier to narrow down what polygons you need to do an intesect check with.

Oliver
  • 29
  • 1
  • +1. a variation on [collision-detection](http://stackoverflow.com/questions/4981866/quadtree-for-2d-collision-detection) could work as well. – alphazero Jul 26 '11 at 14:01
  • 1
    That's for planar geometry. I don't think you can use that on the surface of a sphere. – toto2 Jul 26 '11 at 14:02