<p>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).</p>

<p>Things I have tried:</p>

<ol>
<li><p>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."</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

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

CC BY-SA 3.0
2013-01-15T05:23:49.973Z
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ε
CC BY-SA 3.0
2013-01-15T20:18:13.723Z
Try Delaunay triangulation
Vanessa
CC BY-SA 3.0
2013-01-17T02:55:05.107Z
Dude I love you. That's what I was looking for. Write it as an answer and I'll accept it. :)
Jason
CC BY-SA 4.0
2022-06-16T11:00:13.760Z
This is a long-dead post, but how does one actually implement this transformation? I love Delaunay triangles… but is there a good pointer to best practices in this type of mapping?
JayCrossler
<graph-algorithms>
Map points from one plane into another
Jason
# Map points from one plane into another

(Asked by: username_0 on 2013-01-15)

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?

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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"?  
> **username_2**: Try Delaunay triangulation  
> **username_0**: Dude I love you. That's what I was looking for. Write it as an answer and I'll accept it. :)  
> **username_3**: This is a long-dead post, but how does one actually implement this transformation? I love Delaunay triangles… but is there a good pointer to best practices in this type of mapping?  

---

## 0 answers

