Fitting rectangle
 

Here comes a nice gem for those of you who occasionally want to check "rectangularity" of the polygon given by four points [tex]\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n[/tex], [tex]n\geq 2[/tex]. (The method I have in mind is quite dimension-independent.)

The ordering of the points shall matter; points with index distance 2 are interpreted as diagonally opposite. If you get this wrong, you have a shape containing an X or Z, and that shall be considered far from rectangular.

The task is to find a measure for un-rectangleness in the form of just one nonnegative real value, 0 being equivalent to "perfectly rectangular". A plurality of tests* e.g. for checking angles and lengths separately does not fulfill these requirements.

Second, besides the measure, you need to choose a reference entity to compare with, such that if the measure exceeds some given fraction of the reference, the quadrilateral** given by the vertices [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] shall be considered "not rectangular enough". The measure and the reference shall scale equally, so that the test is scale-invariant. Moreover, the choice of reference shall be such that it bounds angle tolerance and relative length tolerance and is suitable for safe detection of point misordering (crossing sides) regardless of aspect ratio.

The basic idea has already been given in the title: Think of [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] as arbitrary, independent points, and construct a "fitting rectangle" with vertices [tex]\mathbb{x}_1'\ldots\mathbb{x}_4'[/tex] that get as close as possible to the given points [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] respectively, while maintaining perfect rectangleness.

(1) What would you "naturally" choose as measure for un-rectangleness then?
(2) Find mid-point, diagonal directions and diagonal length of the "fitting rectangle". Compare with the given quadrilateral.
(3) Choose a suitable reference for the measure. Demonstrate that it bounds errors in angles, relative side lengths, and is suitable for ruling out X shapes even when we are dealing with large aspect ratios.

*: Is "plurality of [...]" common language, or Patentese only?
**: Tetragon? Quadrangle? What do you prefer?

Note: Using algebra and local optimization is allowed, as are Lagrange multipliers. This should ease dimension-independent reasoning. The results shall be interpreted geometrically however.

Figure
 

Here is a figure.

[QUOTE=ccorn;220590]Here comes a nice gem for those of you who occasionally want to check "rectangularity" of the polygon given by four points [tex]\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n[/tex], [tex]n\geq 2[/tex]. (The method I have in mind is quite dimension-independent.)

The ordering of the points shall matter; points with index distance 2 are interpreted as diagonally opposite. If you get this wrong, you have a shape containing an X or Z, and that shall be considered far from rectangular.

The task is to find a measure for un-rectangleness in the form of just one nonnegative real value, 0 being equivalent to "perfectly rectangular". A plurality of tests* e.g. for checking angles and lengths separately does not fulfill these requirements.

Second, besides the measure, you need to choose a reference entity to compare with, such that if the measure exceeds some given fraction of the reference, the quadrilateral** given by the vertices [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] shall be considered "not rectangular enough". The measure and the reference shall scale equally, so that the test is scale-invariant. Moreover, the choice of reference shall be such that it bounds angle tolerance and relative length tolerance and is suitable for safe detection of point misordering (crossing sides) regardless of aspect ratio.

The basic idea has already been given in the title: Think of [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] as arbitrary, independent points, and construct a "fitting rectangle" with vertices [tex]\mathbb{x}_1'\ldots\mathbb{x}_4'[/tex] that get as close as possible to the given points [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] respectively, while maintaining perfect rectangleness.

(1) What would you "naturally" choose as measure for un-rectangleness then?
(2) Find mid-point, diagonal directions and diagonal length of the "fitting rectangle". Compare with the given quadrilateral.
(3) Choose a suitable reference for the measure. Demonstrate that it bounds errors in angles, relative side lengths, and is suitable for ruling out X shapes even when we are dealing with large aspect ratios.

*: Is "plurality of [...]" common language, or Patentese only?
**: Tetragon? Quadrangle? What do you prefer?[/QUOTE]

So can't you just check that all four corners are 90 degrees? Pthagorus could do it.

[QUOTE=lfm;220772]So can't you just check that all four corners are 90 degrees? Pthagorus could do it.[/QUOTE]

Or just check 3, the 4th has to fit.

Don't you need to check planarity in addition to right angles when n>2?

[quote=wblipp;220780]Don't you need to check planarity in addition to right angles when n>2?[/quote]If three of the angles are 90 degrees, I don't see how the fourth angle could be 90 degrees if the four points are not coplanar.

In 3D: Suppose three points A,B,C are vertices of a right triangle (Angle ABC = 90 degrees). At vertex A construct a disc that's perpendicular to AB. At vertex C construct a disc that's perpendicular to BC.

Consider any point D that is on the intersection line of the two discs. Then DAB = BCD = 90 degrees. If D is not coplanar with A,B,C then angle CDA must be less than 90 degrees. As D slides along the intersection line, angle CDA reaches a maximum (90 degrees), and lengths AD and CD both reach a minimum, exactly when D is on the A,B,C plane.

If D is not coplanar with A,B,C then the lines CD and AD are hypotenuses of right triangles with a vertex D' where the discs' intersection line meets plane ABC. Then, DD' has nonzero length, CD must be longer than CD', AD must be longer than AD', and angle CDA must be less than the right angle CD'A.

Draw the diagonal AC. Then length AC = the square root of the sum of the squares of AD' and CD'. Since AD > AD' and CD > CD', AC is less than the square root of the sum of the squares of AD and CD, so AC can't be the hypotenuse of a right triangle ADC.

I think this holds true in higher dimensions, too.

[QUOTE=cheesehead;220807]If three of the angles are 90 degrees, I don't see how the fourth angle could be 90 degrees if the four points are not coplanar.[/QUOTE]

Yes. The simplest visualization I have found is to draw one of the diagonals. The two triangles clearly have sum of angles of 180 degrees. But the quadrateral angle at the diagonal is less than the sum of the triangle angles unless the triangles are coplanar.

Hence it is NOT sufficient to check 3 angles, but it is sufficient to check all four angles. This suggests a solution to the puzzle - calculate the pythagorean error at all four vertices, and take
a. The largest or
b. The sum of the absolute values
d. The sum of he squared deviations

A useful solution probably includes some kind of scaling to adjust for the pixel granularity.

William

Those are interesting observations. In particular, they show some aspects of why checking a number of angles can be insufficient.

Already in 2D, even checking four angles is not sufficient. With large enough aspect ratio, you can have crossing sides (the X shape) with all four angles arbitrarily close to 90 degrees, and with opposite sides having exactly the same length.

Anyway, as I mentioned in the description of the problem, doing several isolated tests (here: checking several angles) shall be considered a general no-no.

The idea I want to convey is that of a "fitting rectangle". If "fitting" somehow does not trigger enough neurons, think of "regression" instead. If the task were to fit sample data to a function of some given form, you would know what to do. Well, actually, yes, this is the task.

I have illustrated the problem with a figure in post #3. The blue rectangle tries to fit the yellow quadrilateral. (That the blue rectangle's sides happen to be parallel to the pixel coordinate axes is [I]not[/I] a requirement; I arranged for that in order to enable you to verify most easily that it is a rectangle.) It cannot fit perfectly because the yellow quadrilateral is not rectangular. However, the blue rectangle tries to come close to the yellow quadrilateral. There is a fairly standard criterion to define what is "close", and you know it. Use it, then questions (1), (2), (3) can be addressed in a straightforward manner. Depending on how clever you map the problem to mathematical expressions, you get the puzzle done with 1...3 sheets of paper, with remarkable results.

example X shape
 

Here is the same set of four given vertices as in post #3, but [tex]\mathbb{x}_1[/tex] and [tex]\mathbb{x}_2[/tex] are swapped (presumably by error). Watch how the fitting rectangle changes.

[quote=ccorn;220844]With large enough aspect ratio, you can have crossing sides (the X shape) with all four angles arbitrarily close to 90 degrees,[/quote]I forgot that you were asking for a method to work with real-world measurements rather than mathematical ideals.

[QUOTE=cheesehead;220847]I forgot that you were asking for a method to work with real-world measurements rather than mathematical ideals.[/QUOTE]Actually, I have presented the problem as mathematically "idealistic" (given [tex]\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n[/tex] etc.). But indeed, this thread is about a concept that can approximate the idealistic concept of "rectangleness" by a measure of "un-rectangleness" and reasonable tolerance thereof. The method works, is amazingly simple and has interesting mathematical features. Let's work it out.

[quote=ccorn;220862]Actually, I have presented the problem as mathematically "idealistic" (given [tex]\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n[/tex] etc.).[/quote]But wblipp and you mentioned pixels. One could have ideal pixels but an ideal mathematical triangle still wouldn't work well with ideal pixels. Pixels don't allow "angles arbitrarily close to 90 degrees" -- it's either 90 degrees, or some finite pixelated amount away from 90 degrees, not in-between.

[quote=ccorn;220862]But indeed, this thread is about a concept that can approximate the idealistic concept of "rectangleness" by a measure of "un-rectangleness" and reasonable tolerance thereof.[/quote]It reminds me of my very first summer job, programming to run a digital plotter.

The plot consisted of pixels 0.01-inch wide. Subroutines were called with line endpoints as floating-point x,y pairs. One needed to convert each floating-point x,y pair to a series of integer x-pixel,y-pixel positions that lay closest to the line between the given endpoints. The pixel-plot was built up from those series, for each line segment.

[quote]The method works, is amazingly simple and has interesting mathematical features. Let's work it out.[/quote]Gotta think a bit.

[QUOTE=cheesehead;220880]But wblipp and you mentioned pixels.[/QUOTE]
wblipp did. I didn't. Well, ok, I did, but only in the description of the second plot, in order to explain that such things do [I]not[/I] matter. It would not hurt in the end, but we cannot consider pixel aspects yet when we have not worked out a precise concept of a polygon's (un)rectangularity.

[QUOTE]Pixels don't allow "angles arbitrarily close to 90 degrees" -- it's either 90 degrees, or some finite pixelated amount away from 90 degrees, not in-between.[/QUOTE]
As long as you measure an angle by the endpoints of a triangle, you can get arbitrarily close to any angle, even with pixels. (You have probably thought of unkinked line segments---well, then, you could have multiples of 45 degrees only.) Edit: I assume unbounded coordinates here.

But all this leads us away from the track I have in mind.

I have attached a third plot. Again the same set of quadrilateral vertices as in post #3, but this time with [tex]\mathbb{x}_2[/tex] and [tex]\mathbb{x}_3[/tex] swapped. Any permutation of [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] leads to one of the three scenarios plotted so far.

How would you fit [strike]sample data to[/strike] a linear function to sample data?

From the looks of it, the point x_m has co-ordinates that are simply the average of the x and y co-ordinates for the other 4 points.

There are then three important values, the area in common with the shape, the area of the rectangle that does not overlap the shape, and the area of the shape that is not overlapped by the rectangle.

If I had to guess I'd say you find the rectangle centred on point x_m that has the highest area in common with the shape divided by area outside the shape, while also trying to minimise the area of the shape outside the rectangle.

As to go about finding that, I don't know.

Edit: Alternatively, perhaps you pick the points x'1 to x'4 by finding four points on the circumference of a circle centred at x_m, that form a rectangle, and also minimise the distance to the original four points. A generalisation of this to higher dimensions would be to use a sphere, then hypershere etc. This method would mean you only need to pick two points that will form one of the sides of the rectangle, then from these calculate the positions of the other two points.

[quote=ccorn;221002](You have probably thought of unkinked line segments[/quote]No, I was not restricting my thought to unkinked segments!

[quote]Edit: I assume unbounded coordinates here.[/quote]I assumed bounded coordinates. A plotter has finite width.

[QUOTE=lavalamp;221013]From the looks of it, the point x_m has co-ordinates that are simply the average of the x and y co-ordinates for the other 4 points.[/QUOTE]
Indeed! In short, [tex]\mathbb{x}_{\text{M}}=\frac{1}{4}(\mathbb{x}_1+\cdots+\mathbb{x}_4)[/tex]
For a rectangle this is identical to the barycenter, but for a general quadrilateral it is not. Therefore I just call it the mid-point. Your definition by average is the precise one.

So an answer to a part of question (2) is: The mid-points of the given quadrilateral and of the fitting rectangle are the same.

[QUOTE=lavalamp;221013]There are then three important values, the area in common with the shape, the area of the rectangle that does not overlap the shape, and the area of the shape that is not overlapped by the rectangle.

If I had to guess I'd say you find the rectangle centred on point x_m that has the highest area in common with the shape divided by area outside the shape, while also trying to minimise the area of the shape outside the rectangle.[/QUOTE]
For fitting / optimization you need one and only one objective function. You have named two conflicting ones here. Therefore the description is not clear enough to yield a recipe. And it's not precisely those areas that are balanced. But you are getting closer. Hint: look at question (2).

[QUOTE=lavalamp;221013]Edit: Alternatively, perhaps you pick the points x'1 to x'4 by finding four points on the circumference of a circle centred at x_m, that form a rectangle, and also [B]minimise the distance to the original four points[/B]. A generalisation of this to higher dimensions would be to use a sphere, then hypershere etc. This method would mean you only need to pick two points that will form one of the sides of the rectangle, then from these calculate the positions of the other two points.[/QUOTE]
That trace is hot!
As for the circle/sphere etc: That is simply an easy way to create a guaranteed rectangle: Choose an arbitrary mid-point [tex]\mathbb{x}_{\text{M}}[/tex] and two arbitrary displacement vectors [tex]\mathbb{v}_1, \mathbb{v}_2[/tex] of equal length (the radius). Add/subtract these to/from [tex]\mathbb{x}_{\text{M}}[/tex], and you get the vertices of a rectangle. Reason: Circle of Thales. Thus, [tex]\mathbb{v}_1, \mathbb{v}_2[/tex] serve as half-diagonals.

And indeed, The fitting of the rectangle is done by minimizing the distances of its vertices to the original four points. To make that precise, name a simple expression that takes those four distances and combines them into a single scalar that one could try to minimize. Then you have the answer to question (1), and the rest is a straightforward exercise in optimization with a constraint (equal lengths of [tex]\mathbb{v}_1, \mathbb{v}_2[/tex]). The solution has nice geometric properties, and you have already found some of them. Maybe you will find them without algebra and calculus at all, but that sort of exercise would [I]prove[/I] those properties.

[QUOTE=cheesehead;221015]I assumed bounded coordinates. A plotter has finite width.[/QUOTE]
Yeah. For finite width and resolution, a less extreme version of the problem persists: For most practical purposes, you can still construct an actually inacceptable quadrilateral (with side crossings) with all very-close-to-90-degrees angles, by using a large aspect ratio. Angle-checking is not the way to go, and you have been the first to mention some of the difficulties.

Reconsider fitting a rectangle to the given quadrilateral, as described in post #1. We are making progress. Fill in the remaining blanks. I'd like the answers to the questions in post #1 to be found in order, but that requires analytical skills whereas geometrically-minded people might find the answer to question (2) by just looking at the provided figures.

[QUOTE=ccorn;221019]The fitting of the rectangle is done by minimizing the distances of its vertices to the original four points. To make that precise, name a simple expression that takes those four distances and combines them into a single scalar that one could try to minimize.[/QUOTE]From the images you've uploaded, it looks as though you may have minimised the standard deviation of distances between xn and x'n. But that only means that the x'n points will have similar errors, not proximity to xn.

Making a huge rectangle would result in a smaller standard deviation. However it is possible that you placed a bound on the size of the circle, that it may not fully encompass the entirety of the original shape for example.

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.

[QUOTE=wblipp;220834]This suggests a solution to the puzzle - calculate the pythagorean error at all four vertices, and take
a. The largest or
b. The sum of the absolute values
d. The sum of he squared deviations
[/QUOTE]
The sought solution is easier (from my point of view, at least). But I appreciate your suggestions on how to combine pointwise errors into one objective function. Among those proposals, clearly there is one that is analytically easiest to handle.

[QUOTE=lavalamp;221021]From the images you've uploaded, it looks as though you may have minimised the standard deviation of distances between xn and x'n.[/QUOTE]
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.

[QUOTE=ccorn;221024]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.[/QUOTE]Method of least squares?

[QUOTE=lavalamp;221022]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.[/QUOTE]
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 [strike]should have (1-epsilon^2) = 8/9[/strike] 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.

[QUOTE=lavalamp;221025]Method of least squares?[/QUOTE]
YES. State it in its applied form here, and you have the key to questions (1) and (2) of this puzzle.

[QUOTE=lavalamp;221025]Method of least squares?[/QUOTE]
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 [tex]\mathbb{x}_1\ldots\mathbb{x}_4[/tex] of a quadrilateral, find a rectangle with vertices [tex]\mathbb{x}_1'\ldots\mathbb{x}_4'[/tex] such that [tex]\mathbb{x}_1,\mathbb{x}_3[/tex] are diagonally opposite and [tex]S =^{\text{def}} \sum_{i=1}^4 \left|\mathbb{x}_i-\mathbb{x}_i'\right|^2 = \text{min.!}[/tex]

Note that this is a constrained optimization problem. The constraint is that the closed polygon [tex](\mathbb{x}_1'\ldots\mathbb{x}_4')[/tex] shall form a rectangle. This may be expressed most easily by the circle-of-Thales approach from post #17: Substitute
[tex]\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}[/tex]
and take into account the constraint [tex]\left|\mathbb{v}_1\right|^2-\left|\mathbb{v}_2\right|^2 = 0[/tex].

The minimized error square sum [I]S[/I] 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 [tex]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)[/tex] (substitute [tex]\mathbb{x}_1'\ldots\mathbb{x}_4'[/tex] on the right-hand side using [tex]\mathbb{x}_{\text{M}},\mathbb{v}_1,\mathbb{v}_2[/tex]).

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

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

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 [tex]S_\text{c}[/tex].

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