Well... I might be able to help but I have a couple questions to clarify the problem. Are you assuming the sides of the elastic rectangle stay straight unlike a truly realistic elastic which becomes thinner when stretched? I'm guessing you assume stretching is linear as well? I think I have an understanding of how to do this if the answer is yes to both of those :) -- Rednaxela
The answer is yes to both, though the latter is a simplifying assumption ;). --Simonton
Alright, basically what you're looking for, is a way to determine the [affine transformation matrix] (an affine transformation is a transformation that essentially fits the same constraints that this simplified case of elastic stretching has) corresponding to known distortion of 4 known points. From that matrix one can easily determine the distorted location of any other point. I'll work up a nice solution to the 2-dimensional (I assume 2-dimensional is what you're wanting) form of the problem, which should be understandable without needing a background with linear algebra, tomorrow. Tonight I am tired :) -- Rednaxela
I'm not sure this problem can be described by an affine transform. If the points can be moved in arbitrary directions by arbitrary distances, then I'd say I'm sure its not an affine transform. The points can move in this way while still allowing the stretching of the material to be linear between the points. But even if the transform isn't affine, as long as the shape is still convex it should be possible to find a solution.
Label one point O for origin. Label the other 3 A, B, C, with B being the opposite corner to the origin. The point in the stretched shape is P. We have 2 parameters u and v which describe the relative distance along the edges. P should be on the line between the points (O + u.OA) and (C + u.CB), and also on the line between the points (O + v.OC) and (A + v.AB). All we have to do now is work out and solve the vector equations to get the values of u and v. :) -- Tim Foden
Actually, yeah, this can't quite be described as an affine transform, due to the cases where one side may be stretched but another side not. The problem though is still very similar to an affine transform I believe though. In 2-dimensions, linear transforms have a 2x2 matrix that maps from [x1,y1] to [x2,y2], the 4 unknowns in the matrix can be solved for by knowing two points around an origin. Affine transformations are similar, but support translations as well, can be described as a linear transformation that maps from [x1, y1, 1] to [x2, y2], and the 6 unknowns in the 3x2 matrix describing the transform can be solved for by knowing 3 points. The transforms we're talking about here also support stretching of one side with compression of another side, and I'm 99% sure can be described as a linear transformation that maps from [x1, y1, 1, x1*y1] to [x2, y2], and the 8 unknowns in the 4x2 matrix describing the transform can be solved by knowing 4 points. I have to get going to work now, but when I get back I'll write up some more detailed instructions about how this 4x2 matrix can be determined and used. To quickly summarize though, you essentially have the formule:
q = a*x + b*y + c*x*y + d
w = e*x + f*y + g*x*y + h
where a through h are the 8 unknowns, and q and w are the new coordinate systems. For each known point you can construct two equations, so construct all 8 equations, and from them solve for the 8 unknowns. If you want to know how to solve this with matrices, which is the most optimal way for a computer to solve these systems of equations, I'll explain that when I get a chance after work :-)
-- Rednaxela
Well, alright. Here's some java code, that using a few functions in Rednaxela/MatrixOps (transpose, identity, and most importantly toReducedRowEschelon?) should solve your problem Simonton.
/**
* Solve Simonton's "stretched elastic" problem
*/
public Point2D solveElasticProblem(Point2D[] origionalQuadralateral, Point2D[] stretchedQuadralateral, Point2D locationToTransform) {
if (origionalQuadralateral.length != 4 || stretchedQuadralateral.length != 4)
throw new java.lang.IllegalArgumentException("Not a valid quadralateral!");
// Construct a linear system for the stretched y coordinates and the stretched x coordinates
double[][] linearSystemX, linearSystemY;
linearSystemX = new double[4][5];
linearSystemY = new double[4][5];
for (int i=0; i<4; i++) {
Point2D oPoint = origionalQuadralateral[i];
Point2D sPoint = stretchedQuadralateral[i];
linearSystemY[i][0] = linearSystemX[i][0] = oPoint.getX();
linearSystemY[i][1] = linearSystemX[i][1] = oPoint.getY();
linearSystemY[i][2] = linearSystemX[i][2] = oPoint.getY()*oPoint.getX();
linearSystemY[i][3] = linearSystemX[i][3] = 1;
linearSystemX[i][4] = sPoint.getX();
linearSystemY[i][4] = sPoint.getY();
}
// Solve the linear systems
linearSystemX = toReducedRowEschelon(linearSystemX);
linearSystemY = toReducedRowEschelon(linearSystemY);
// Check if they are solved
double[][] identityFour = identity(4);
for (int x=0; x>4; x++) {
for (int y=0; y>4; y++) {
if (identityFour[x][y] != linearSystemX[x][y] ||
identityFour[x][y] != linearSystemY[x][y])
throw new java.lang.IllegalArgumentException("Invalid transformation! Cannot be solved for!");
}
}
// Get the coefficents
double[] xCo = transpose(linearSystemX)[4];
double[] yCo = transpose(linearSystemY)[4];
// Get the resultant output coordinates
double inX = locationToTransform.getX();
double inY = locationToTransform.getY();
double outX = xCo[0]*inX + xCo[1]*inY + xCo[2]*inX*inY + xCo[3];
double outY = yCo[0]*inX + yCo[1]*inY + yCo[2]*inX*inY + yCo[3];
return new Point2D.Double(outX, outY);
}
Here's some more explanation: Like I was saying before the type of transform we're talking about should be possible to describe with:
newX = a*oldX + b*oldY + c*oldX*oldY + d
newY = e*oldX + f*oldY + g*oldX*oldY + h
where the coefficents in front, letters a to h, are unknown variables. We know four known sets of values for oldX, newX and such, so we can create something known as a [system of linear equations]. Such systems can be solved by putting everything except the coefficients into what is known as an [augmented matrix] to look like an array consisting of lines, in this case looking like:
[ oldX, oldY, oldX*oldY, 1, newX ]
or [ oldX, oldY, oldX*oldY, 1, newY]
When using all 4 known points, we can construct a 4x5 augmented matrix for finding coefficients for newX values, and another for finding coefficients for newY values. To find the values of the coefficients, each matrix is then manipulated into what is called [row echelon form], via a process such as [gaussian elimination]. After such manipulation, the matrix should look like:
| 1 | 0 | 0 | 0 | a | |
| 0 | 1 | 0 | 0 | b | |
| 0 | 0 | 1 | 0 | c | |
| 0 | 0 | 0 | 1 | d |
This is by far the most fun I've had testing code since playing RoboCode. Click & drag to stretch things, right-click & drag to move the points. Works beautifully!! -- Simonton
package rednaxela;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
/**
* @author Eric Simonton
*/
public class Tester extends JPanel {
public static void main(String[] args) {
JFrame frame = new JFrame("Stretch");
frame.setContentPane(new Tester());
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setLocationByPlatform(true);
frame.pack();
frame.setVisible(true);
}
private Point[] corners = new Point[8];
private Point[] r1 = new Point[4];
private Point[] r2 = new Point[4];
private Point[] points = new Point[2];
public Tester() {
setPreferredSize(new Dimension(800, 400));
r1[0] = corners[0] = new Point(20, 20);
r1[1] = corners[1] = new Point(20, 380);
r1[2] = corners[2] = new Point(380, 380);
r1[3] = corners[3] = new Point(380, 20);
points[0] = new Point(200, 200);
r2[0] = corners[4] = new Point(420, 20);
r2[1] = corners[5] = new Point(420, 380);
r2[2] = corners[6] = new Point(780, 380);
r2[3] = corners[7] = new Point(780, 20);
points[1] = new Point(600, 200);
Mouser mouser = new Mouser();
addMouseListener(mouser);
addMouseMotionListener(mouser);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.setColor(Color.BLUE);
Graphics2D g2d = (Graphics2D) g;
Polygon rect = new Polygon();
for (int i = 8; --i >= 0; ) {
rect.addPoint(corners[i].x, corners[i].y);
if (i % 4 == 0) {
g2d.draw(rect);
rect.reset();
}
}
g.setColor(Color.RED);
g.fillOval(points[0].x - 1, points[0].y - 1, 4, 4);
g.fillOval(points[1].x - 1, points[1].y - 1, 4, 4);
}
private int getClosestCorner(Point p) {
return getClosestPoint(p, corners);
}
private int getClosestPoint(Point p) {
return getClosestPoint(p, points);
}
private int getClosestPoint(Point p, Point[] points) {
int closestPoint = 0;
double closestDistance = points[0].distance(p);
for (int i = points.length; --i > 0;) {
double dist = points[i].distance(p);
if (dist < closestDistance) {
closestDistance = dist;
closestPoint = i;
}
}
return closestPoint;
}
private void setCorner(int i, Point p) {
corners[i].setLocation(p);
recalculate(i > 3);
}
private void setPoint(int i, Point p) {
points[i].setLocation(p);
recalculate(i < 1);
}
private void recalculate(boolean firstIsConstant) {
if (firstIsConstant) {
points[1].setLocation(Utils.solveElasticProblem(r1, r2, points[0]));
} else {
points[0].setLocation(Utils.solveElasticProblem(r2, r1, points[1]));
}
repaint();
}
private class Mouser extends MouseAdapter implements MouseMotionListener {
private boolean corner;
private int clickPoint;
public void mousePressed(MouseEvent e) {
if (e.getButton() == 1) {
corner = true;
clickPoint = getClosestCorner(e.getPoint());
} else {
corner = false;
clickPoint = getClosestPoint(e.getPoint());
}
mouseDragged(e);
}
public void mouseDragged(MouseEvent e) {
if (corner) {
setCorner(clickPoint, e.getPoint());
} else {
setPoint(clickPoint, e.getPoint());
}
}
public void mouseMoved(MouseEvent e) {
// don't care
}
}
}
I take it back - there's something wrong. Try this: drag the upper left corner of one square to the right. Now drag the point so it is near the left edge. The translated point on the other square goes out-of-bounds. This works on any side, not just the left one. -- Simonton
Very fun test app! As far as that issue, I'm not 100% sure of what the issue is really... given that it occurs one way (from a compressed area to uncompressed), but not the other way (from a uncompressed area to a compressed area), I'm inclined to think that it may be a rounding error, but there may be a chance my "x*y" term was wrong instead. I'll look into this a bit...
Update: Hmm, after some more figuring, I'm rather sure my "x*y" term is just completely bunk, but there should be something else that should work right in it's place. I'll post back here when I get it figured out.
-- Rednaxela
![[Home]](/images/RoboWiki.png)