Fitting rectangle - Page 2

ccorn · 2010-07-08, 22:31

Quote:

Originally Posted by cheesehead

I forgot that you were asking for a method to work with real-world measurements rather than mathematical ideals.

Actually, I have presented the problem as mathematically "idealistic" (given $\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n$ 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.

cheesehead · 2010-07-09, 03:05

Quote:

Originally Posted by ccorn

Actually, I have presented the problem as mathematically "idealistic" (given $\mathbb{x}_1\ldots\mathbb{x}_4\in\mathbb{R}^n$ etc.).

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:

Originally Posted by ccorn

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.

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.

Gotta think a bit.

ccorn · 2010-07-10, 17:00

Quote:

Originally Posted by cheesehead

But wblipp and you mentioned pixels.

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

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 $\mathbb{x}_2$ and $\mathbb{x}_3$ swapped. Any permutation of $\mathbb{x}_1\ldots\mathbb{x}_4$ leads to one of the three scenarios plotted so far.

How would you fit ~~sample data to~~ a linear function to sample data?

lavalamp · 2010-07-10, 22:14

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.

cheesehead · 2010-07-10, 22:43

Quote:

Originally Posted by ccorn

(You have probably thought of unkinked line segments

No, I was not restricting my thought to unkinked segments!

Quote:

Edit: I assume unbounded coordinates here.

I assumed bounded coordinates. A plotter has finite width.

ccorn · 2010-07-10, 23:52

Quote:

Originally Posted by lavalamp

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.

Indeed! In short, $\mathbb{x}_{\text{M}}=\frac{1}{4}(\mathbb{x}_1+\cdots+\mathbb{x}_4)$
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:

Originally Posted by lavalamp

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.

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:

Originally Posted by lavalamp

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.

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 $\mathbb{x}_{\text{M}}$ and two arbitrary displacement vectors $\mathbb{v}_1, \mathbb{v}_2$ of equal length (the radius). Add/subtract these to/from $\mathbb{x}_{\text{M}}$ , and you get the vertices of a rectangle. Reason: Circle of Thales. Thus, $\mathbb{v}_1, \mathbb{v}_2$ 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 $\mathbb{v}_1, \mathbb{v}_2$ ). 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 prove those properties.

ccorn · 2010-07-11, 00:14

Quote:

Originally Posted by cheesehead

I assumed bounded coordinates. A plotter has finite width.

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.

lavalamp · 2010-07-11, 00:19

Quote:

Originally Posted by ccorn

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.

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.

lavalamp · 2010-07-11, 00:24

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.

ccorn · 2010-07-11, 00:31

Quote:

Originally Posted by wblipp

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

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.

ccorn · 2010-07-11, 00:45

Quote:

Originally Posted by lavalamp

From the images you've uploaded, it looks as though you may have minimised the standard deviation of distances between xn and x'n.

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.

2010-07-10, 22:14	#15
lavalamp Oct 2007 Manchester, UK 10101001100₂ Posts	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. Last fiddled with by lavalamp on 2010-07-10 at 22:28

2010-07-11, 00:24	#20
lavalamp Oct 2007 Manchester, UK 2²·3·113 Posts	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. Last fiddled with by lavalamp on 2010-07-11 at 00:26

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