1. Re: Digest for EUforum at topica.com, issue 3457
> Date: Thu, 18 Mar 2004 13:14:27 +0100
> From: Tommy Carlier Subject: Polygon coordinates transformation
>I want to add a routine to Win32Dib, that can draw a part of a bitmap on
another bitmap, but
>stretched to a polygon. To do this, I need to find an algorithm that transforms
>coordinates from
>1 polygon to another one. I have 2 polygons with each 4 points:
>
>polygon_source ={u1, v1}, {u2, v2}, {u3, v3}, {u4, v4}}
>polygon_destination ={x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}}
>
>I need to find a formula that transforms a coordinate {x, y} inside
>polygon_destination to
>a coordinate {u, v} inside polygon_source.
As emphasized in the previous answers, there isn't a clean way to do
this in a linear fashion, as you have 4 points and an affine referential is
made of 3 points in the plane.
Also, we have to define that notion of "corresponding point". There is a lot
of ways to do this actually. You need to specify a continuous family of
transformations in the plane that starts from source_polygon and lands at
dest_polygon. This is called an homotopy.
You can find an affine map that transform sourc__polygon into
interm_polygon, the latter havong the points:
{(u1,v1),(u2,v2),(u3,v3),(s4,t4)}. Now the problem is: how to go from here to
dest_polygon? Not in a linear way.
Any line starting from (x1,y1), determined by the angle a it makes with the
line ((x1,y1),(x2,y2)), cuts the boundary of interm_polygon at a distance
r1(a) and the boundary of dest_polygon at a distance r2(a). Now, you can apply
the dilatation by r2(a)/r1(a) to any point of interm_polygon on this line.
This is not linear, as the ratio varies with a.
Doing so leaves the edges starting from (x1,y1) fixed, is convex and
transforms the boundary of interm_polygon into the one of dest_polygon, all in
a continuous way, which should eliminate unsightly distorsions.
Well, the coding of these are "left as an exercise". Instead of using the
angle a, which causes sine and cosine slow calculations, you could use the
barycentric position of the intersection of the line starting fro (x1,y1) with
the line ((x2,y2),(x3,y3)) as a parameter instead; should be faster.
CChris
