For fun, I ended up rewriting this, because I realized you could cut the number of comparisons in half (and double the speed).
To get a correct result, each point needs to be compared against every other point. Taking 3 points as an example, A, B and C:
- 1st pass: compare A against B and C. (Note that there is no reason to compare A vs A – but the original code snippet does do this.)
- 2nd pass: compare B against A and C – but “B against A” was already done in the first pass. So you only need to do B vs C.
- 3rd pass: compare C against A and B – but both of these were already done. So this entire inner loop can be skipped.
So it can be done with only 3 comparisons, where the original code would perform 9.
It can’t quite be inferred from the code example exactly what is the data structure, so I made up a different one. For this type of problem, I often use Event. Here, it lets me store a 2D point along with the comparison results, using descriptive names, making the code easier to read (I hope).
(
f = { |a|
(a.size - 1).do { |i| // n-1 times
var thisPt = a[i];
(i+1 .. a.size-1).do { |j| // only points that haven't been checked
var dist = thisPt[\point].dist(a[j][\point]);
if(a[j][\point].x < thisPt[\point].x) {
if(thisPt[\leftDist].isNil or: {
dist < thisPt[\leftDist]
}) {
thisPt[\leftIndex] = j;
thisPt[\leftDist] = dist;
a[j][\rightIndex] = i;
a[j][\rightDist] = dist;
};
};
if(a[j][\point].x > thisPt[\point].x) {
if(thisPt[\rightDist].isNil or: {
dist < thisPt[\rightDist]
}) {
thisPt[\rightIndex] = j;
thisPt[\rightDist] = dist;
a[j][\leftIndex] = i;
a[j][\leftDist] = dist;
};
};
};
};
a
};
)
Test it:
(
~array = Array.fill(5, {
(point: Point(1.0.rand2.round(0.001), 1.0.rand2.round(0.001)))
});
)
f.(~array);
~array.do(_.postln); ""
// e.g.
( 'point': Point( 0.62, 0.789 ), 'leftDist': 0.92818640369271, 'rightDist': 1.0064000198728, 'rightIndex': 3,
'leftIndex': 4 )
( 'point': Point( -0.006, -0.447 ), 'leftDist': 0.82633770336346, 'rightDist': 0.89250266106046, 'rightIndex': 3,
'leftIndex': 4 )
( 'point': Point( -0.795, 0.064 ), 'rightDist': 0.66189122973492, 'rightIndex': 4 )
( 'point': Point( 0.849, -0.191 ), 'leftDist': 0.89250266106046, 'leftIndex': 1 )
( 'point': Point( -0.201, 0.356 ), 'leftDist': 0.66189122973492, 'rightDist': 0.82633770336346, 'rightIndex': 1,
'leftIndex': 2 )
// and plot it, to check
(
var blk = Color.black, pt = Color(0.5, 1, 0.5);
w = Window("test", Rect(800, 200, 300, 300)).front;
w.layout = VLayout(
u = UserView()
);
u.drawFunc_({ |view|
var b = view.bounds.extent;
var xscale = b.x * 0.5, yscale = b.y * 0.5;
var scale = Point(xscale, yscale.neg);
var offset = Point(xscale, yscale);
Pen.color_(blk)
.moveTo(Point(xscale, 0)).lineTo(Point(xscale, b.y))
.moveTo(Point(0, yscale)).lineTo(Point(b.x, yscale))
.stroke;
~array.do { |pt, i|
pt = pt.point * scale + offset;
Pen.color_(pt);
Pen.fillOval(Rect.aboutPoint(pt, 4, 4)).stroke;
Pen.stringAtPoint(i.asString, pt + Point(0, -20), Font.default, blk);
};
})
.refresh;
)
For my example run, the plot looks like this:
Taking point 4 as an example, the nearest point to the left is in fact 2 ('leftIndex': 2) and the nearest to the right is 1. (Point 2 doesn’t have a leftIndex because there is no point to its left; same for point 3’s missing rightIndex.)
The 0 here is probably okay because this would be the result when comparing a point against itself. (I got rid of the zero check by not comparing points against themselves.)
hjh
