I want to translate points contained in polygon ABCD to their relative
positions in polygon A'B'C'D'

The formula will take as input the known set of points:
first polygon: (Ax,Ay) (Bx,By) (Cx,Cy) (Dx,Dy)
second polygon: (A'x,A'y) (B'x,B'y) (C'x,C'y) (D'x,D'y)
and the point from the first polygon: (Ex,Ey)

It must return the mapped point E' in the second polygon: (E'x,E'y)

This formula must perform as many of the objectives as possible:
- translate points in a square to points in a rectangle
- translate points in a square to points in a parallelogram
- translate points in a square to points in any polygon
- translate points in any polygon to points in any polygon.

Implement in Java

public Point getTranslatedPoint( Polygon polySource, Polygon polyDest,
Point ptSource )
{
   // perform translation
   // and return new relative point in destination
}

---

Clarification of Question by jamieyukes-ga on 17 May 2004 14:15 PDT

I've toyed with solving it visually.  I drew a line (AE) and looked at
the ratio of (angle BAE)/(angle BAD)... and then drew a line in the
new polygon such that the inside angle was also proportionate to
(angle B'A'D').  Doing this from each vertex usually makes a small
shape, of which I feel the midpoint is the proper position for E'. 
But that's just me eyeballing it.

---

Clarification of Question by jamieyukes-ga on 17 May 2004 14:21 PDT

"Doing this from each vertex usually makes a small shape, of which I
feel the midpoint is the proper position for E'."

I guess its not really a midpoint either... In this new small shape, I
calculate a "midpoint" as the intersection of lines connecting
opposite vertices.

---

Request for Question Clarification by josh_g-ga on 17 May 2004 16:09 PDT

Did you need a Java implementation, or would a pseudocode description
of a solution be sufficient?

---

Clarification of Question by jamieyukes-ga on 17 May 2004 16:51 PDT

I would be satisfied with a pseudocode solution so long as I can
readily implement and verify it in Java.  Also, the solution should be
fairly optimized.

---

Clarification of Question by jamieyukes-ga on 18 May 2004 16:41 PDT

That is correct.  I only need solutions for quadrilaterals.  Whoops.

---

Request for Question Clarification by maniac-ga on 20 May 2004 16:57 PDT

Hello Jamieyukes,

If the program already posted in a comment is acceptable - I suggest
you close this question so you won't get billed for an answer.

  --Maniac

Assume points D and D' did not exist and that E was not necessarily in
the interior of the first polygon.  Furthermore, assume A, B and C
(and resp. in the second polygon) are not collinear.  Then there
exists a unique affine transformation taking A to A', B to B', and C
to C'.  Therefore it remains to simply compute the image of E under
this transformation.

In slightly different terms:  this isn't too difficult using some
linear algebra and assuming both polygons are parallelograms. 
Whenever the polygons are parallelograms, this approach does the
"natural" transformation which, for example,
+ sends A to A', B to B', C to C', and D to D'
+ sends midpoints of sides of midpoints of sides
+ send the intersection of the diagonals to the intersection of diagonals
+ and mostly "does the Right Thing"

Because squares and rectangles are, in particular, parallelograms,
this accomplishes at least the first two of your desired operations.

The following code should do that in Java.  You probably already have
code for the classes Point and Polygon, and so you should modify the
appropriate linkage if necessary.  Furthermore, access modifiers like
"public" and "private" have been omitted where possible.

A sample main() routine has been provided to demonstrate the code.

[As a final note, it *is* possible to do what you want in full
generality with any kinds of four-sided figures.  Unfortunately, I
don't have much time and cannot work out the equations.]

Feel free to ask me any questions.  Hopefully I will be here to answer them.

========== Map.java ==========
import java.util.*;

class Map {
    public static void main( String[] args ) {
        // Test routine
        Polygon a = new Polygon( new Point( 0, 0 ),
                                 new Point( 1, 1 ),
                                 new Point( 0, 2 ),
                                 new Point(-1, 1 ) );
        Polygon b = new Polygon( new Point( 3, 3 ),
                                 new Point( 5, 3 ),
                                 new Point( 5, 4 ),
                                 new Point( 3, 4 ) );
        Point p = new Point( 0, 1 );

        Point q = getTranslatedPoint( a, b, p );

        System.out.println( "Project point p from polygon a to polygon
b resulting in point q:\n" );
        System.out.println( "a = " + a + "\nb = " + b + "\np = " + p +
"\nq = " + q );
    }

    static Point getTranslatedPoint( Polygon polySource, Polygon
polyDest, Point ptSource )
    {
        /* Use only the first three points of both Polygons */
        Point
            a = (Point) polySource.v.get( 0 ),
            b = (Point) polySource.v.get( 1 ),
            c = (Point) polySource.v.get( 2 ),

            ap = (Point) polyDest.v.get( 0 ),
            bp = (Point) polyDest.v.get( 1 ),
            cp = (Point) polyDest.v.get( 2 ),

            e = ptSource;

        /* Compute affine location coefficients */
        double wa = ref( b, c, e ) / ref( b, c, a );
        double wb = ref( c, a, e ) / ref( c, a, b );
        double wc = ref( a, b, e ) / ref( a, b, c );

        return weight( ap, bp, cp, wa, wb, wc );
    }

    static double ref( Point a, Point b, Point c ) {
        return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y );
    }

    static Point weight( Point a, Point b, Point c, double wa, double
wb, double wc ) {
        return new Point( a.x*wa + b.x*wb + c.x*wc, a.y*wa + b.y*wb + c.y*wc );
    }
}

/* I assume you have the following classes implemented similar to the
manner below */
class Point {
    double x;
    double y;

    Point( double x, double y ) {
        this.x = x; this.y = y;
    }

    public String toString( ) {
        return "(" + x + ", " + y + ")";
    }
}

class Polygon {
    Vector v;   /* Vector of Points, of course -- and in consecutive
order (either clockwise or counterclockwise) */

    Polygon( Point a, Point b, Point c, Point d ) {
        v = new Vector();
        v.add( a ); v.add( b ); v.add( c ); v.add( d );
    }

    public String toString( ) {
        int i;
        String result = "[ ";

        for( i = 0; i < v.size(); i++ ) {
            if( i > 0 )
                result += " ; ";
            result += v.get(i);
        }
        result += " ]";
        return result;
    }
}

I'm sorry my Java code got so mangled.


By the way, the code (and approach) I detailed should work as well
whenever you're mapping between two similar polygons, and in
particular, between two congruent polygons.

Finally, note that the order of the vertices in the polygons matters.

Nice job.  This approach yields similar precision to the solution that
I have already implemented.  However, the case for mapping to an
arbitrary polygon is really what is needed.  Here is my real world
test case:

1st polygon: (4497,1406), (6336,8896), (9425,7633), (8644, 562)
2nd polygon: (1377, 453), ( 286, 225), ( 280, 723), (1304, 976)

The polygons are fairly similar, but not close enough for this
solution.  (at least in my verification tests)

Okay, I scrounged up the time and brains to give this another shot.

Unfortunately, the new Java code is some 171 lines long.  Instead of
getting it mangled here and taking up huge amounts of space, I've
posted it online at
  http://www.mit.edu/~borisa/tmp/Map.java

This time it maps general quadrilaterals to general quadrilaterals (in
a natural, mathematical way -- although a bunch of linear algebra is
involved).  The sample main() routine is set up to work with the two
quadrilaterals you gave me in your last comment.  It's also
"interactive", in a sense.

The new approach is that there is a unique projective transformation
(kind of like a perspective image) that takes one quadrilateral to the
other, and so I simply compute the image of E under this map.  Affine
transformations, like those used in my previous solution, are in
particular projective transformations, so this solution still maps
between parallelograms in "the natural way" and between similar
figures in "the natural way" as before.

Unfortunately, some round-off error accumulates in this solution. 
It's approximately on the order of 10^-12 to 10^-14, however, so this
is not so bad.

Just as a last comment, my code assumes that no three points in either
quadrilateral are collinear.

How is this new code working?

That is a fair assumption.  I will try and get to testing it later tonight.

This answer looks good.