Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!execu!sequoia!rpp386!garnett
From: garnett@rpp386.cactus.org (John Garnett)
Newsgroups: comp.graphics
Subject: Re: help with quick color map search
Message-ID: <17173@rpp386.cactus.org>
Date: 21 Oct 89 06:14:24 GMT
References: <67563@tut.cis.ohio-state.edu>
Reply-To: garnett@rpp386.UUCP (John Garnett)
Organization: USENET Users' Anonymous
Lines: 22

In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu 
(Robert Rosenblum) writes:
>I'm writing an application which involves taking a given rgb value and
>finding the color in the color map which is closest.  My routine
>performs a linear search through the color map, comparing the
>"distance" between my rgb value and each color map entry, and the
>index of the closest color is returned.  However, this technique is
>very slow.
>
>Is there is a more efficient way to find the closest color in a color
>map?  Any help would be greatly appreciated.

You may wish to investigate "An Algorithm for Finding Best Matches
in Logarithmic Expected Time" by Jerome M. Friedman, Jon Louis
Bentley, and Raphael Ari Finkel in the September 1977 issue of
the _ACM Transactions on Mathematical Software_, p. 209.

-- 
+------------------------------------+-----------------------------------+
| John Garnett                       |      Base 1.9                     |
| garnett@rpp386.cactus.org          |                                   |
| {bigtex|texbell}!rpp386!garnett    |      "It's almost binary"         |