Fitting rectangle - Page 3

lavalamp · 2010-07-11, 00:58

Quote:

Originally Posted by ccorn

You almost got it. It's not exactly what you stated, but related. Think even simpler. And some ingredient of standard deviation is in there.

Method of least squares?

ccorn · 2010-07-11, 01:00

Quote:

Originally Posted by lavalamp

As an aside, just naturally thinking about an "equivalent rectangle" for a shape, I would suggest that the rectangle should have the same area as the original shape, and that it's four corners lie in such a way as to minimise the standard deviation of their distances to the corners of the original shape.

Though this is obviously a different direction to the one you have taken.

The area is not exactly preserved, though its relative change is quadratic in a parameter epsilon which you may define as (difference of diagonal lengths) / (sum of diagonal lengths) of the given quadrilateral. Edit: The quadrilateral depicted in post #3 has epsilon = 1/3, so the fitting rectangle ~~should have (1-epsilon^2) = 8/9~~ has 1/(1-epsilon^2) = 9/8 the area of the quadrilateral. In this (quite extreme) example, the area grows by 1/8. Smaller epsilons result in (roughly) quadratically smaller area growth.

There is a way to preserving the area, but it requires "weighing" the distances, and that approach is slightly more complicated. Do the given problem first, then you can take off and perhaps rise to findings of area-preserving and barycenter-centered fitting rectangles.

ccorn · 2010-07-11, 01:03

Quote:

Originally Posted by lavalamp

Method of least squares?

YES. State it in its applied form here, and you have the key to questions (1) and (2) of this puzzle.

ccorn · 2010-07-15, 18:55

Quote:

Originally Posted by lavalamp

Method of least squares?

As said above, yes. Regrettably, no concretization has followed. After four days, I find that I have to spell it out myself.

Given the vertices $\mathbb{x}_1\ldots\mathbb{x}_4$ of a quadrilateral, find a rectangle with vertices $\mathbb{x}_1'\ldots\mathbb{x}_4'$ such that $\mathbb{x}_1,\mathbb{x}_3$ are diagonally opposite and $S =^{\text{def}} \sum_{i=1}^4 \left|\mathbb{x}_i-\mathbb{x}_i'\right|^2 = \text{min.!}$

Note that this is a constrained optimization problem. The constraint is that the closed polygon $(\mathbb{x}_1'\ldots\mathbb{x}_4')$ shall form a rectangle. This may be expressed most easily by the circle-of-Thales approach from post #17: Substitute
$\begin{array}{rl} \mathbb{x}_1' &= \mathbb{x}_{\text{M}} - \mathbb{v}_1\\ \mathbb{x}_2' &= \mathbb{x}_{\text{M}} - \mathbb{v}_2\\ \mathbb{x}_3' &= \mathbb{x}_{\text{M}} + \mathbb{v}_1\\ \mathbb{x}_4' &= \mathbb{x}_{\text{M}} + \mathbb{v}_2 \end{array}$
and take into account the constraint $\left|\mathbb{v}_1\right|^2-\left|\mathbb{v}_2\right|^2 = 0$ .

The minimized error square sum S is a measure for un-rectangleness. That is the answer to question (1). (You still have to find a suitable reference entity to compare with. That is question 3).

Answering question (2) is straightforward if you know how to do optimizations of the above form. Briefly, you have to look for stationary points of $S_{\text{c}}(\mathbb{x}_{\text{M}},\mathbb{v}_1, \mathbb{v}_2,\lambda) = \sum_{i=1}^4 \left|\mathbb{x}_i-\mathbb{x}_i'\right|^2 + \lambda\,\left(\left|\mathbb{v}_1\right|^2-\left|\mathbb{v}_2\right|^2\right)$ (substitute $\mathbb{x}_1'\ldots\mathbb{x}_4'$ on the right-hand side using $\mathbb{x}_{\text{M}},\mathbb{v}_1,\mathbb{v}_2$ ).

Doing this exercise, you will quickly find $\mathbb{x}_{\text{M}} = \frac{1}{4}\left(\mathbb{x}_1+\cdots+\mathbb{x}_4\right)$ , as recognized by lavalamp in post #15. Go on and find $\mathbb{v}_1, \mathbb{v}_2$ , then interpret the result geometrically. (You will also have to find the optimal value for the Lagrange multiplier $\lambda$ for that).

ccorn · 2010-07-25, 17:08

Here is the figure of post #3, this time with the diagonals of the quadrilateral indicated.

ccorn · 2010-08-19, 15:17

If the problem was not interesting enough, how about its solution?

(1) Solved above, indicated by lavalamp. The minimized distance-squared sum is chosen as a measure for un-rectangleness.

(2) Midpoint found by lavalamp. The diagonals of the fitting rectangle are parallel to the diagonals of the given quadrilateral (i. e. diagonal directions are preserved), and the length of each fitting rectangle's diagonal is the arithmetic mean of the lengths of the given quadrilateral's diagonals (i. e. the sum of the diagonal lengths is preserved). These results can be found by analytically optimizing $S_\text{c}$ .

(3) Now you have the fitting rectangle with side lengths a, b and the minimized distance-squared sum S. Without loss of generality, let $a \ge b$ , thus $b = \min\{a,b\}$ . Now choose some dimensionless positive number $\mu$ and compare S with $\mu^2 b^2$ . If and only if S is greater, call the quadrilateral not rectangular enough. Reducing $\mu$ reduces the tolerance of un-rectangleness. This test is clearly scale-invariant, and choosing $b^2$ as reference for S ensures an upper bound of $O(\mu)$ for errors in angles and relative errors in opposite side lengths. Furthermore, choosing $\mu < 1$ excludes X-like shapes.

2010-07-25, 17:08	#27
ccorn Apr 2010 2·3·5² Posts	Here is the figure of post #3, this time with the diagonals of the quadrilateral indicated. Attached Thumbnails

2010-08-19, 15:17	#28
ccorn Apr 2010 226₈ Posts	Solution If the problem was not interesting enough, how about its solution? (1) Solved above, indicated by lavalamp. The minimized distance-squared sum is chosen as a measure for un-rectangleness. (2) Midpoint found by lavalamp. The diagonals of the fitting rectangle are parallel to the diagonals of the given quadrilateral (i. e. diagonal directions are preserved), and the length of each fitting rectangle's diagonal is the arithmetic mean of the lengths of the given quadrilateral's diagonals (i. e. the sum of the diagonal lengths is preserved). These results can be found by analytically optimizing $S_\text{c}$ . (3) Now you have the fitting rectangle with side lengths a, b and the minimized distance-squared sum S. Without loss of generality, let $a \ge b$ , thus $b = \min\{a,b\}$ . Now choose some dimensionless positive number $\mu$ and compare S with $\mu^2 b^2$ . If and only if S is greater, call the quadrilateral not rectangular enough. Reducing $\mu$ reduces the tolerance of un-rectangleness. This test is clearly scale-invariant, and choosing $b^2$ as reference for S ensures an upper bound of $O(\mu)$ for errors in angles and relative errors in opposite side lengths. Furthermore, choosing $\mu < 1$ excludes X-like shapes.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Rectangle Packing	henryzz	Puzzles	4	2012-02-05 16:23