|
|
|
better range calculation algorithm
Monday, October 31 2011
Yesterday I'd found that the point-in-relationship-to-a-polygon algorithm I'd been using was too CPU-intensive for practical use in determining whether a particular organism lives in a particular area. Today, though, I came up with a much simpler, faster algorithm that actually worked better for my purposes than a point-in-relationship-to-a-polygon algorithm. It was so simple that I could just write it out without resorting to a polygon library. I basically reversed the question I was asking. Instead of wondering whether my house (say) lies within a creature's range, I asked instead whether each vertex of a creature's range lies within a quadrangle centered around my house. Testing to see whether or not a point lies within a quadrangle is trivially easy, so even if a creature's range polygon is defined by thousands of verticies, it takes only a second or two to determine if the creature's range intrudes into the target quadrangle. If so, it can be considered to live in the quadrangle. The only downside to this algorithm is that it only works for reasonably-large quadrangles, ideally ones that intercept a natural boundary (such as a coastline) beyond which creatures would not live. But that's fine for creating field guides, which typically cover an area half the size of a continent or larger. If the quadrangle is too small, there's a danger that some creatures' ranges will exist entirely throughout it and there will be no verticies from those ranges to be detected within the quadrangle, and so the algorithm will fail to determine that the creatures lived in that quadrangle.
To help me visualize some of the ranges in the web-based database manipulation tool I was using, I finally got around to researching how to display polygons on a Google map. Part of what I had to do was use a more current Google Map API, which makes a lot of stuff that used to be complicated much easier. Once that was working, it wasn't difficult to then display data normally targeted for ESRI maps to Google maps. See some examples of these things in action here:
A sample guide, with its quadrangle on a Google Map.
Birds and Mammals algorithmically calculated to live in that quadrangle.
The record for Cooper's Hawk, complete with its ESRI map data displayed on a Google Map.
Now that I have all this database support built out, I can begin the project of caching and displaying this data on an iPad.
For linking purposes this article's URL is:
http://asecular.com/blog.php?111031 feedback
previous | next |
