The context here is geo-location/geo-fencing. I need to compute the smallest enclosing quadrilaterals for a large sequence of irregular polygons (latitude/longitude value pairs) in order to approximately place a location in the right "polygon" with as little overhead as possible.
Finding the smallest bounding rectangle is a trivial task:just establish the min & max latitude + longitude values and define the bounding rectangle. However, I have been unable to establish the fastest possible route to establishing the coordinates of bounding quadrilateral. The more obvious Google searches I have tried have yielded little. I am hoping that someone here might be able to help.
A few explanations to help here in response to the various comments
- I can acquire the bounding quadrilateral coordinates once and for all on a decently powered computer so computational power should not be considered to be a constraint.
- It may not be assumed that the polygons are convex
- Finally, what needs to be minimized? = Area
I should explain what I am trying to accomplish here. Take a look at the image below. I have used the rotated outline map of Austria by way of example - it has concavity, has one "end" a whole lot bigger than the other etc: the characteristics I want to deal with efficiently. This is only an example. The "real" polygons I need to deal with cover much smaller geographic areas.
Bounding this shape in a rectangle "pulls in" a great deal of "unrequired" area since the top of the shape of the polygon is so much smaller than the bottom of the shape. Using a bounding quadrilateral helps to reduce the unrequired area.
As I have noted, I only require this to make an approximate location placement. The fact that this technique can lead to spurious placements of a point in more than one adjoining quadrilateral bound polygons is not a concern.