1234567890123456789012345678901234567890123456789012345678901234567890

Mean Distance to a Rectangle

Q: How can "the" distance of a points cloud to a rectangle be defined?

A: By subdividing the plane into twelve (12) regions (green lines) and
   then defining a distance (red balls & black lines) for each of the
   points. Then determine e.g. the mean value of the distances found.

A picture says more than a thousand words:

http://hdebruijn.soo.dto.tudelft.nl/jaar2010/rechthoek.jpg

Any (maybe better) ideas? For other figures as well?

Han de Bruijn


1234567890123456789012345678901234567890123456789012345678901234567890

Best Fit Rectangle

Q: Given a contour (simple piecewise smooth closed curve in the plane)
   what would be the Best Fit Rectangle for that contour?

I need this for the (pattern) recognition of "buttons". And could come
up with three possible answers.

1: Length L and area O of the contour can be determined with numerical
   calculation. Let the edges of the rectangle be a and b. Then one of
   the edges is the following and the other is easily found.
 
    2.(a + b) = L   and  a.b = O  ==>  a = L/4 + sqrt((L/4)^2 - O)

   There is a nasty ambiguity, though, in the interpretation of a and
   b (as a width or as a height) which needs to be resolved. Accuracy
   (due to errors in L) can be quite disappointing.
 
2: Second order moments of the contour as collection of LINE segments
   can be calculated numerically. The same for a rectangle with edges
   a and b can be calculated exactly:   s_xy = 0
 
   s_xx = a^2.(a/6 + b/2)(2*(a+b))  ;  s_yy = b^2.(b/6 + a/2)(2*(a+b))

   But calculating a and b from s_xx and s_yy is a non-linear problem!
   (Which can be resolved eventually by Newton-Rhapson iteration)

3: Second order moments of the contour as collection of AREA segments
   can be calculated numerically. The same for a rectangle with edges
   a and b can be calculated exactly:
 
    s_xx = a^2/12  ;  s_yy = b^2/12  ;  s_xy = 0

   Calculating a and b from s_xx and s_yy of the contour is easy now:

    a = 2.sqrt(3.s_xx)  ;  b = 2.sqrt(3.ss_yy)

A picture says more than a thousand words:

http://hdebruijn.soo.dto.tudelft.nl/jaar2010/yamaha.jpg

Answers 1 : Green, 2 : Yellow, 3 : Blue, Red : other.

It is "seen" that the accuracy of (1) is disappointing, (2) is better,
and (3) is the simplest and most accurate.

Han de Bruijn