Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!hplabs!hpfcso!hpfcdq!poe
From: poe@hpfcdq.HP.COM (Daryl Poe)
Newsgroups: comp.graphics
Subject: Re: Re: help with quick color map search + FIX for ppmquant
Message-ID: <390041@hpfcdq.HP.COM>
Date: 25 Oct 89 17:21:43 GMT
References: <67563@tut.cis.ohio-state.edu>
Organization: Hewlett-Packard - Fort Collins, CO
Lines: 22

> Is there is a more efficient way to find the closest color in a color
> map?  Any help would be greatly appreciated.

Take a look at "An Algorithm for Finding Nearest Neighbors" by Friedman,
Baskett, and Shushtek, IEEE Transactions on Computers, October, 1975, p.
1000.

The algorithm they suggest is to sort the points along one of the
dimensions.  Given a target point, search outward from that target along
your sorted dimension (say, blue) until the distance along that
dimension is greater than the distance (in all three dimensions) to the
nearest color found so far.  Obviously, any colors further away from your
target in that dimension are also going to be further away when all
three dimensions are considered, so you can end your search at that
point.

The overhead of this algorithm is fairly small and it works well with
small data sets (like the 16-4096 entries in a typical colormap).


Daryl Poe
Hewlett-Packard, Graphics Technology Division