That's PhiLho (two Hs)
I haven't played much with the morph programs, when they were a fad, but I remember that in lot of cases, you chose manually which point from the start is paired to which point at the end.
You can do that by taking care that each couple of point is at the same position.
It is more reliable than heuristics, and allows some interesting effects too.

FPoint is a class i created to essential hold 2 PVectors (current point and goto point)

am looking at that and there's a lot of code i don't understand.

you say you have two arrays. where are they?

and i don't get the linked list aspect. surely each point only has one nearest neighbour. why the need for a list of them?

i think your problem may be that a point in set B may be the nearest for more than one member of set A

1. A1  A2
2. B1                                  B2
   

and that you then delete B2, somehow

i'd just use three arrays

public static int COUNT = 20;
PVector now[] = new PVector[COUNT];       // current position
PVector next[] = new PVector[COUNT];      // new position
int nearest[] = int[COUNT];      // index of nearest neighbour

initialise now and next to random arrays of PVectors

finding nearest neighbour is just

1. for (int i = 0 ; i < COUNT ; i++) {
2.   float dist = 10000000000; // set to large number initially. no need to store.
   
3.   for (j = 0 ; j < COUNT ; j++) {
4.     thisDist = distance from now[i] to next[j];
5.     if (thisDist < dist {
6.       dist = thisDist;
7.       nearest[i] = j;      // next[j] is the nearest to now[i]
8.   }
9. }

then lerp from now[i] to next[nearest[i]]

when you've done set now[] to next[] and initialise next[] to a new random PVector array and start again.

When you replace line 277 with this...

1.       ellipse(pt2.x, pt2.y, i*10, i*10);

... the problem is nicely illustrated.

I agree with kooogy. One way to solve the problem of multiple nearest neighbours is to make a list of the available indices and remove them as they are picked as a nearest neighbour. That way you always end up with matching pairs. Otherwise all points eventually end up clustered into the same spot. Look at your code with the above replacement of line 277 and this clustering process becomes quite apparent.

Remember that once you force a paired outcome, the challenge then becomes finding the optimal solution. Since there are more than one possible paired outcomes. Moving through the points in a different orders will probably result in different outcomes. These different outcomes could be compared by their totalLength. The optimal solution is the one with the lowest totalLength. Don't know how optimal you want your solution to be.

If you really have a lot of points (and/or 3 dimensions) perhaps you can look into using a k-d tree. Also see the PointOctree example in Toxiclibs. You could use it to lower the number of N * N possibilities when searching for the nearest neighbour.

Here is a very basic implementation of the algorithm discussed above using Toxiclibs (although it should be fairly easy to use PVector instead). I'm pretty sure there are mathematically better ways to find an optimal solution. This one performs all right. You need at least 1 try to get a list of matched pairs. Give it a 100 tries and it will find a solution which is better. Give it a 1000 tries and it may find an even more optimal solution etc. Although given it's randomly inefficient brute-force method, you may very well be searching without getting a more optimal solution...

As said above, when you have significantly more points and/or dimensions you will probably need more advanced methods.

A good way to further optimize this code would be to run the findConnections() from B to C during the interpolation from A to B. That way you'll have your new best matched pairs by the time the points reach their destination.

Code Example

1. import toxi.geom.*;
2.  
3. int numPoints = 50;                // the number of points
4. int spacing = 50;                  // spacing from the sides with regard to the ellipse's locations
5. int radius = 10;                   // radius of the ellipses
6. int maxTries = 100;                // number of tries (could be anything from 1 to infinity)
7. float interpolationSpeed = 0.01;   // movement speed going from point A to point B
8.  
9. Vec2D[] A = new Vec2D[numPoints];
10. Vec2D[] B = new Vec2D[numPoints];
11. int[] bestMatches = new int[numPoints];
12. int lowestTotalLength, totalTries;
13. boolean searching = true;
14. float interpolation;
15.  
16. void setup() {
17.   size(800, 800, P2D);
18.   frameRate(10000);
19.   lowestTotalLength = numPoints * width;
20.   A = randomPoints();
21.   B = randomPoints();
22.   fill(0, 0, 255);
23.   noStroke();
24.   smooth();
25. }
26.  
27. void draw() {
28.   background(255);
29.   if (searching) {
30.     findConnections();
31.     for (int i=0; i<numPoints; i++) {
32.       ellipse(A[i].x, A[i].y, radius, radius);
33.     }
34.     if (totalTries > maxTries) {
35.       frameRate(60);
36.       searching = false;
37.     }
38.   } else {
39.     for (int i=0; i<numPoints; i++) {
40.       Vec2D v = A[i].interpolateTo(B[bestMatches[i]], interpolation);
41.       ellipse(v.x, v.y, radius, radius);
42.     }
43.     interpolation += interpolationSpeed;
44.     if (interpolation > 1) {
45.       interpolation = 0;
46.       lowestTotalLength = numPoints * width;
47.       totalTries = 0;
48.       A = B;
49.       B = randomPoints();
50.       frameRate(10000);
51.       searching = true;
52.     }
53.   }
54. }
55.  
56. Vec2D[] randomPoints() {
57.   Vec2D[] randomPoints = new Vec2D[numPoints];
58.   for (int i=0; i<numPoints; i++) {
59.     randomPoints[i] = new Vec2D(random(spacing, width-spacing), random(spacing, height-spacing));
60.   }
61.   return randomPoints;
62. }
63.  
64. void findConnections() {
65.   int[] matches = new int[numPoints];
66.   ArrayList <Integer> order = new ArrayList <Integer> ();
67.   ArrayList <Integer> possibilities = new ArrayList <Integer> ();
68.   for (int i=0; i<numPoints; i++) {
69.     possibilities.add(i);
70.     order.add(i);
71.   }
72.   Collections.shuffle(order); // this creates a different solution every try
73.   for (int i=0; i<numPoints; i++) {
74.     int closestPossibility = findClosestPoint(A[order.get(i)], possibilities);
75.     matches[i] = possibilities.get(closestPossibility);
76.     possibilities.remove(closestPossibility); // this forces matched pairs
77.   }
78.   int totalLength = 0;
79.   for (int i=0; i<numPoints; i++) {
80.     totalLength += A[i].distanceTo(B[matches[i]]);
81.   }
82.   if (totalLength < lowestTotalLength) {
83.     lowestTotalLength = totalLength;
84.     bestMatches = matches;
85.   }
86.   totalTries++;
87. }
88.  
89. int findClosestPoint(Vec2D v, ArrayList <Integer> possibilities) {
90.   float closestDistance = 654321;
91.   int closestPoint = -1;
92.   for (int i=0; i<possibilities.size(); i++) {
93.     Vec2D target = B[possibilities.get(i)];
94.     float distance = v.distanceTo(target);
95.     if (distance < closestDistance) {
96.       closestDistance = distance;
97.       closestPoint = i;
98.     }
99.   }
100.   return closestPoint;
101. }

Ken, please look again.

The findNearest() function and the near int[] array in your sketch are not being used. By that I mean, you call them, but you don't do anything with the results. It's currently the sorter that makes both the transition and the line between two consecutive points look good, which is perhaps good enough. However in that case you could just delete all those other things and achieve exactly the same effect as before. What your sketch does now is lerp from a set of (sorted) random points to another set of (sorted) random points, like so...

1. import processing.opengl.*;
2.  
3. ArrayList npoints = new ArrayList();
4. ArrayList next = new ArrayList();
5. float lerpAmt = 0.0f;
6.  
7. void setup() {
8.   size(600,600, OPENGL);
9.   smooth();
10.   int initCount = 60;
11.   for(int i=0; i<initCount; i++) {
12.     PVector p = new PVector(random(width),random(height), random(width));
13.     npoints.add( p );
14.  
15.     PVector n = new PVector(random(width),random(height), random(width));
16.     next.add( n );
17.   }
18.  
19.   initialize();
20. }
21.  
22. void draw() {
23.   background(0);
24.   frame.setTitle( str(frameRate) );
25.   lights();
26.  
27.   translate(width/2,height/2, -width);
28.   rotateX( radians(frameCount*0.5) );
29.   rotateY( radians(frameCount*0.5) );
30.   rotateZ( radians(frameCount*0.5) );
31.   translate(-width/2,-height/2, 0);
32.  
33.   for(int i=0; i<npoints.size(); i++) {
34.     PVector fro = (PVector) npoints.get(i);
35.     PVector to = (PVector) next.get(i);
36.  
37.     //from point
38.     noStroke();
39.     fill(255,0,255);
40.     PVector lerped = plerp(fro, to, lerpAmt);
41.     pushMatrix();
42.     translate(lerped.x,lerped.y, lerped.z);
43.     ellipse(0,0, 9,9);
44.     popMatrix();
45.  
46.     //from point
47.     stroke(0,255,255);
48.     noFill();
49.     pushMatrix();
50.     translate(to.x,to.y, to.z);
51.     ellipse(0,0, 9,9);
52.     popMatrix();
53.  
54.     npoints.set(i, lerped);
55.   }
56.  
57.   noFill();
58.   noStroke();
59.   beginShape(LINES);
    
60.   for(int i=0; i<npoints.size(); i++) {
61.     PVector pt = (PVector) npoints.get(i);
62.     float g = norm(i, 0,npoints.size())*255;
63.     stroke(0,g,255);
64.     vertex(pt.x, pt.y, pt.z);
65.   }
66.   endShape();
67.  
68.   if(lerpAmt >= 1.0) {
69.     update();
70.     lerpAmt = 0.0f;
71.   } else {
72.     lerpAmt += 0.01f;
73.   }
74. }
75.  
76. void initialize() {
77.   Collections.sort(npoints, new XSorter());
78.   Collections.sort(next, new XSorter());
79. }
80.  
81. void update() {
82.   next = new ArrayList();
83.   for(int i=0; i<npoints.size(); i++) {
84.     PVector n = new PVector(random(width),random(height), random(width));
85.     next.add( n );
86.   }
87.  
88.   initialize();
89. }
90.  
91. PVector plerp(PVector pt1, PVector pt2, float amt) {
92.   float x = lerp(pt1.x, pt2.x, amt);
93.   float y = lerp(pt1.y, pt2.y, amt);
94.   float z = lerp(pt1.z, pt2.z, amt);
95.   return new PVector(x,y,z);
96. }
97.  
98. public class XSorter implements Comparator<PVector> {
99.   public int compare(PVector p1, PVector p2) {
100.     if(p1.x < p2.x) return -1;
101.     else if(p1.x > p2.x) return 1;
102.     else return 0;
103.   }
104. }