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.

enter image description here

  • $\begingroup$ You aren't allowed to rotate the rectangle? Then what are you allowed to do with the quadrilateral? $\endgroup$ Feb 21 '17 at 8:39
  • $\begingroup$ Also what are your constraints? Does this need to be done on a 8 bit micro controller in real time or can you use a mobile phone or a desktop PC or even a supercluster? $\endgroup$ Feb 21 '17 at 8:44
  • $\begingroup$ Also what exactly do you want to minimize (area, diameter,...)? $\endgroup$
    – fedja
    Feb 21 '17 at 20:04
  • $\begingroup$ @mathreadler, I don't understand your comment re rotation. I have put in a few notes to better clarify what I am trying to accomplish $\endgroup$
    – DroidOS
    Feb 22 '17 at 10:24
  • $\begingroup$ It looks like to me that you want to find the largest convex hull of your shape with an additional constraint that there be only four points in this convex hull. $\endgroup$
    – Ricky
    Feb 22 '17 at 10:52

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:

  1. $|v|=|v^{\perp}|$
  2. $\mbox{det}\begin{vmatrix} v^p_1 & v^p_2\\ v_1 & v_2\end{vmatrix} >0.$

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}}.$

  • $\begingroup$ Thank you. It will take me some time to understand and translate this to some working code. $\endgroup$
    – DroidOS
    Feb 22 '17 at 8:12

Are your polygons convex? Will the quadrilateral always be convex? If so then my intuition tells me that the minimum bounding quadrilateral will have sides that coincide with sides of the polygon. I don't know how to prove this but I'm pretty sure that at the very least making this assumption won't be a disaster. So to find a good solution you just enumerate all possible quadrilaterals that share all sides with polygon and then pick the one with the smallest area. This could be very ineffient though if the number of sides of the polygon is large.

  • $\begingroup$ No the polygons are not always convex. I think it would be reasonable to work to the assumption that I can live with a convex bounding quadrilateral $\endgroup$
    – DroidOS
    Feb 22 '17 at 8:10
  • $\begingroup$ Ummm... on reflection can a quadrilateral ever be anything other than convex? $\endgroup$
    – DroidOS
    Feb 22 '17 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.