Vitaly Budovski wrote:
Vitaliy Margolen wrote:
Vitaly Budovski wrote:
Make use of the Triangle Inequality Nearest Neighbour algorithm to find the nearest colour more efficiently than a simple linear search. The improvements are most noticeable with a palette of 256 colours. Testing shows approximately 3-4x performance increase for 256 colours.
Overall idea looks good, however the big problem with it is use of float point numbers. Fortunately you can get rid of them and use integers instead. Because you never use the distance in the calculations, but only to compare against other distances, you can skip "sqrt" and just compare squares, as the original code does. That will give you even more speed improvements.
Thanks for the tip. Unfortunately in this instance it will not work as I do in fact query more than a < b. See the nearest function in patch 2.
And what is so special about subtracting one from the other?
Few more nitpicks about this and other patches in the series:
+static int compare_distance(const void *left, const void *right) +{
- const struct tinn *l = left;
- const struct tinn *r = right;
Please don't use void pointers. Use typed pointers, especially that you cast them to a hard-coded type.
The qsort function I use internally takes that particular function pointer.
And the problem is what? Any pointer is compatible with void* (not other way around).
Vitaliy Margolen.