Creating a dataset for possible integration into MySQL and the Google Maps API for a website? (a la point-in-polygon, collision theorem, etc.),

Question

Over the past few months, I have been able to teach myself PHP, PDO and SQL, as well as create a basic dynamic website with the function of registering users / email and logging in, following the best practices of PHP / SQL. Now I'm stuck in the next task ...

I created a huge dataset of squares / polygons (3 million +), each of which is 1 minute of latitude and longitude, stored in a PHP array with one set of coordinates (upper left corner). To extrapolate the square shape, I simply add 0.016 degrees (~ 1 minute) in each direction and generate the other 3 coordinates.

Now I need to check that every polygon in the indicated array is completed, at least on some part of the earth in the United States ... i.e. if one was to create a graphical output of my completed dataset and take a look at San Francisco, they would see something like this .

This is similar to the point-in-polygon problem, except that it touches another polygon instead of a point, the other polygon is the country's border, and I don't just look at intersections. I want to check if:

• The polygon / square intersects the polygon. (Think of the coastline / border).
• The polygon / square is inside the polygon. (Think of continental US).
• The polygon / square contains part of the polygon. (Think of a small island).

This is illustrated by my roughly painted image:

If it matches any of these three conditions, I want to keep the square. If it does not interact at all with a large polygon (i.e., Above water), discard it.

I thought that the big polygon would be a shapefile in the USA, which is a KML file from which I could remove the coordinates to create a very complex polygon.

Then I thought that I was passing these squares and square ID over to a csv file for integration into a MySQL table containing the set of coordinates of each square (in fact, I'm not even sure of the best practice for processing tables of this size in MySQL, but I will come to this, when needed). The ultimate goal would be to develop a map using the Google Maps API through Javascript to display these squares above the map on the website that I am coding (obviously only showing the squares in point of view to make sure that I do not levy db tax on death ) I am sure that I will also have to pass such information through PHP. But all this seems relatively easy compared to the task of actually creating the specified dataset.

This is obviously something that cannot be done manually, so it needs automation. I know a little Python, so will this help? Any other tips on where to start? Does anyone want to write code for me?

Answer 1

Here is a solution that will be effective and as simple as possible to implement. Please note that I am not saying it simply, but as simple as possible. This is a difficult problem, as it turned out.

1) Get the polygon data in the USA using Shapefiles or KFL, which will give a set of polygonal shapes (land mass), each of which is determined by a list of vertices.

2) Create a set of rectangular rectangles (AABBs) for the United States: one for Alaska and each Alaskan island, one for each Hawaiian island, one for the continental United States and one for each small island on the coast of the Continental United States (for example, Bald Head Island in NC, Catalina off the coast of California). Each bounding rectangle is defined as a rectangle with angles that are the minimum and maximum latitude and longitude for the shape. I assume that there will be several hundred. For example, for the large island of Hawaii, latitude ranges from 18 ° 55'N to 28 ° 27'N, and longitude is 154 ° 48'W to 178 ° 22'W. Most of your global lat / long pairs are thrown out at this stage, since they are not in any of these several hundred bounding rectangles. For example, your bounding box at 10 ° 20'W, 30 ° 40'N (a spot in the Atlantic Ocean near Las Palmas, Africa) does not block Hawaii because 10 ° 20'W is less than 154 ° 48'W. This the bit will be easy to code in Python.

3) If the lat / long DOES pair overlaps one of several hundred AABB rectangles, you need to test it against one polygon in the AABB rectangle. For this, it is highly recommended to use the Minkowski Difference (MD). Please read this site carefully:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

In particular, watch the demo of "poly versus poly" halfway down the page and play with it a bit. When you do this, you will see that when you take the MD of two shapes, if this MD contains the origin, then the two shapes overlap. So, all you have to do is take the Minkowski difference from the two polygons, which in itself leads to the appearance of a new polygon (B - A, in the demo), and then see if this polygon contains the origin.

4) There are many documents on the Internet regarding algorithms for implementing MD, but I don’t know if you can read the document and translate it into code. Since this is complex vector math, to take an MD from two polygons (the tested lat / long rectangle and the polygon contained in the bounding box that overlaps the lat / long rectangle), and you told us that your experience level is not high yet, I would suggested using a library that already implements MD, or even better, implements conflict detection.

For example:

http://physics2d.com/content/gjk-algorithm

Here you can see the corresponding pseudocode that you can port to Python:

if aO cross ac > 0 //if O is to the right of ac if aO dot ac > 0 //if O is ahead of the point a on the line ac simplex = [a, c] d =-((ac.unit() dot aO) * ac + a) else // O is behind a on the line ac simplex = [a] d = aO else if ab cross aO > 0 //if O is to the left of ab if ab dot aO > 0 //if O is ahead of the point a on the line ab simplex = [a, b] d =-((ab.unit() dot aO) * ab + a) else // O is behind a on the line ab simplex = [a] d = aO else // O if both to the right of ac and to the left of ab return true //we intersect! 

If you cannot transfer this yourself, you may be able to contact one of the authors of the two links that I have included here - both of them have implemented the MD algorithm in Flash, perhaps you could license the source code.

5) Finally, assuming you have processed collision detection, you can simply store a boolean in the database as to whether the lat / long pair is part of the United States. After that, I have no doubt that you can do what you want using your part of Google Maps.

So, to summarize, the only difficult task here is to either 1) implement the GJK collision detection algorithm, or, alternatively, 2) write an algorithm that first calculates the Minkowski difference between your lat / long pair and the ground polygon contained in your AABB, and then secondly, see if this MD polygon contains the origin. If you use this approach, Ray Casting (a typical point-in-polygon solution) will do the trick with the second part.

Hope this gives you a start in the right direction!

Answer 2

I think this other question answers the good part of what you are trying to do.

How to determine if two convex polygons intersect?

The other part is that if you are using a database, I would load all the polygons next to your viewpoint from both sets (the set of map polygons and the set of other polygons that you generated), and then execute the above algorithm on this smaller a set of polygons, and you can generate a list of all the polygons in your set that should be superimposed on the map.