Re: Mapping a square grid to a rectangular grid

Karel Bruneel <karel.bruneel@xxxxxxxx> writes in article <drcqj0$7hc$1@xxxxxxxxxxxxxxx> dated Fri, 27 Jan 2006 11:38:31 +0100:
> dsg(a,b)=sqrt((xa-xb)^2+(ya-yb)^2)

>I'm looking for a mapping that maps every grid point of
>the square grid to a grid point of the rectangular grid.
>This mapping should be injective
>
> f:SG -> RG
>
>Therefore |SG| should be less or equal to |RG|. Lets
>presume this is true.
>
>I would like grid points that were close to each other
>in the square grid would still be close to each other
>in the rectangular grid after the mapping. Mathematically
>I formulated this as.
>
> cost=1/2 SUM ( SUM ( drg( f(g) , f(h) ) ) )
> g in SG h in (g's neighbors)
>
>By g's neighbors I mean the grid points that are only a distance
>1 away from g.

That's an excellent problem description. (I snipped a lot, others should
see the referenced article for more detail.)

The "intuitively obvious" solution is to keep as much of the square as
possible intact and center it on the rectangle as closely as possible.
Then pack whatever part you had to snip into the empty part of the
rectangle.

In your example this might mean translating the 12-unit section with corners
at (0,1) and (3,3) to the one at (1,0) and (4,2). Break the non-intact
section in half and rotate it to the side so that the original corner is
still a corner.

(0,0)-->(0,0)
(1,0)-->(0,1)
(3,0)-->(5,0)
(2,0)-->(5,1)

This has an incremental cost of 2*(sqrt(5)-1)+4, I think.

The 3-piece method works for rectangles which are at least half the height
of the square. Is there a case where it's not optimal?

Are you working with any rectangles that have aspect ratio worse than 4:1?

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
.

Relevant Pages
Loading