Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a point on a plane A, I want to be able to map to a corresponding point on plane B. I have a set of N corresponding pairs of reference points between the two planes, however, the overall mapping is not a simple affine transform (no homographies for me).

Things I have tried:

  1. For a given point, find the three closest reference points in plane A, compute barrycentric coordinates of that triangle, and then apply that transform to the corresponding reference points in plane B. How it failed: sometimes the three closest points were nearly collinear, so errors were huge. Also, there was no consistency in the mapping when crossing borders. It was very "jittery."

  2. Compute all possible triangles given the N reference points (N^3). Order them by size. For the given point, find the smallest triangle that it's in. This fixes the linearly of the points problem, but was still extremely jittery and slow.

  3. Start with a triangulated plane A. Iterate through the reference points, adding each one to the reference plane. Every time you add a point it exists in at least one triangle. Break that triangle into three triangles using the new reference point as a vertex. You end up with plane A triangulated so you can map from plane A to plane B with ease. Issues: You can prove that every triangle will have a point that is on the edge of the planes. This results in huge errors if your reference points are far from the edge of the planes.

I feel like this should be a fairly standard problem. Are there standard algorithms/libraries for this?

share|cite|improve this question
What objective function are you trying to optimize? What are your constraints? (Do you want a homeomorphism, an immersion, a submersion, or something else? Does the map have to be piecewise linear?) Why do you care if the map is "jittery"? And what is an "edge" of a plane? (Planes are infinite.) What, in this context, is an "error"? – Jeffε Jan 15 '13 at 5:23
Try Delaunay triangulation – Squark Jan 15 '13 at 20:18
Dude I love you. That's what I was looking for. Write it as an answer and I'll accept it. :) – Jason Jan 17 '13 at 2:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.