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.
Best Answer
Let $P\subset \mathbb{R}^3 $ be a polygon and let $S^1$ be a unit circle in $\mathbb{R^3}.$ Consider a function $\delta^* :S^1 \to \mathbb{R} $ defined by $$\delta^* (v) =\sup_{(x,y)\in P} (xv_1 +yv_2 ) $$ where $v=(v_1, v_2 )\in S^1.$ For a vector $v\in \mathbb{R}^3 $ let $v^{\perp} =(v^p_1 ,v^p_2 )$ a vector perpendicular to $v$ satisfying two conditions:
Then define two function $\kappa:S^1\to \mathbb{R}, $ by
$$k(v) =\max\left\{ \delta^* (v) +\delta^* (-v) , \delta^* (v^{\perp} ) +\delta^* (-v^{\perp} )\right\}. $$ Let $\chi\in S^1$ be a vector such that $$\kappa(\chi) =\min_{v\in S^1} \kappa(v)$$ and let $l_{\chi} $ be a stright lines perpendicular $\chi $ and let $l_{\chi^{\perp}}$ be a stright lines perpendicular $\chi^{\perp} $ then the minimal quadrilateral has sides lying on some translations of lines $l_{\chi}$ and $l_{\chi^{\perp}}.$