mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-07-04, 20:15   #1
ccorn
 
ccorn's Avatar
 
Apr 2010

32×17 Posts
Default Fitting rectangle

Here comes a nice gem for those of you who occasionally want to check "rectangularity" of the polygon given by four points \mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n, n\geq 2. (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 \mathbb{x}_1\ldots\mathbb{x}_4 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 \mathbb{x}_1\ldots\mathbb{x}_4 as arbitrary, independent points, and construct a "fitting rectangle" with vertices \mathbb{x}_1'\ldots\mathbb{x}_4' that get as close as possible to the given points \mathbb{x}_1\ldots\mathbb{x}_4 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?

Last fiddled with by ccorn on 2010-07-04 at 20:21
ccorn is offline   Reply With Quote
Old 2010-07-04, 22:48   #2
ccorn
 
ccorn's Avatar
 
Apr 2010

32×17 Posts
Default

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.
ccorn is offline   Reply With Quote
Old 2010-07-08, 03:17   #3
ccorn
 
ccorn's Avatar
 
Apr 2010

100110012 Posts
Default Figure

Here is a figure.
Attached Thumbnails
Click image for larger version

Name:	rect.png
Views:	146
Size:	10.3 KB
ID:	5445  
ccorn is offline   Reply With Quote
Old 2010-07-08, 06:31   #4
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default

Quote:
Originally Posted by ccorn View Post
Here comes a nice gem for those of you who occasionally want to check "rectangularity" of the polygon given by four points \mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n, n\geq 2. (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 \mathbb{x}_1\ldots\mathbb{x}_4 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 \mathbb{x}_1\ldots\mathbb{x}_4 as arbitrary, independent points, and construct a "fitting rectangle" with vertices \mathbb{x}_1'\ldots\mathbb{x}_4' that get as close as possible to the given points \mathbb{x}_1\ldots\mathbb{x}_4 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?
So can't you just check that all four corners are 90 degrees? Pthagorus could do it.
lfm is offline   Reply With Quote
Old 2010-07-08, 06:38   #5
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default

Quote:
Originally Posted by lfm View Post
So can't you just check that all four corners are 90 degrees? Pthagorus could do it.
Or just check 3, the 4th has to fit.
lfm is offline   Reply With Quote
Old 2010-07-08, 10:23   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×593 Posts
Default

Don't you need to check planarity in addition to right angles when n>2?
wblipp is offline   Reply With Quote
Old 2010-07-08, 16:38   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by wblipp View Post
Don't you need to check planarity in addition to right angles when n>2?
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.

Last fiddled with by cheesehead on 2010-07-08 at 17:20 Reason: Not elegantly minimized, but Oll Korrect now, I think.
cheesehead is offline   Reply With Quote
Old 2010-07-08, 18:55   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·593 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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.
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
wblipp is offline   Reply With Quote
Old 2010-07-08, 20:41   #9
ccorn
 
ccorn's Avatar
 
Apr 2010

32·17 Posts
Default

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 not 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.

Last fiddled with by ccorn on 2010-07-08 at 21:01
ccorn is offline   Reply With Quote
Old 2010-07-08, 20:56   #10
ccorn
 
ccorn's Avatar
 
Apr 2010

32×17 Posts
Default example X shape

Here is the same set of four given vertices as in post #3, but \mathbb{x}_1 and \mathbb{x}_2 are swapped (presumably by error). Watch how the fitting rectangle changes.
Attached Thumbnails
Click image for larger version

Name:	rect2.png
Views:	128
Size:	12.7 KB
ID:	5451  

Last fiddled with by ccorn on 2010-07-08 at 21:06
ccorn is offline   Reply With Quote
Old 2010-07-08, 21:00   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by ccorn View Post
With large enough aspect ratio, you can have crossing sides (the X shape) with all four angles arbitrarily close to 90 degrees,
I forgot that you were asking for a method to work with real-world measurements rather than mathematical ideals.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 09:36.


Fri Aug 12 09:36:18 UTC 2022 up 36 days, 4:23, 2 users, load averages: 1.06, 1.13, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔