Sorting question

Cogman

Lifer
Sep 19, 2000
10,283
134
106
Hey everyone again, I'm in need of some help. Im trying to replicate some functions from another language to c++. One of the functions FindColorsSpiralTolerance is supposed to do a spiral search for colors that are close to a given color within a given tolerance range and return the points that test positive, starting from a given point. There is another function FindColorsTolerance that returns an array of Points to the matching colors. Currently my methodology is like this.

Get the points using FindColorsTolerance,
create an array that is the same length as the one returned from FindColorsTolerance.
Fill the new array with distances from the center point.
heap sort the new array simultaneously switching values in the original point array.

Technically it isn't a spiral search, more of a circular one, but that is close enough for me.

So far these are the options I have been considering.

1. do a different searching method, quicksort maybe.
2. implement a real spiral search rather then this pseudo one.
3. somehow store off the final changes and then re-order the point array based on them.

Overall, I have a working function, it is just slower then I would like, and the sorting is where I am dieing (Profiler tells me this).
 

Markbnj

Elite Member <br>Moderator Emeritus
Moderator
Sep 16, 2005
15,682
14
81
www.markbetz.net
One way I did this in the past (I wrote an article for DDJ on the technique in 1993) is to presort the existing colors into a BSP tree. Since colors can be interpreted as sparse points in a 3D volume where r=x, g=y, b=z (for example), and palettes are usually pretty static, the problem lends itself nicely to a tree-based search. If you're not familiar with BSP trees they rotate the index of comparison at each level of the tree, and create a spatial partitioning.

So basically to find matches within a certain tolerance from a particular color you begin by comparing red at level 0, and if the target color is less than the top node's red component you go left, otherwise you go right. At the next level you compare green and do the same, and so on for blue, and then back to red. At each level you calculate the euclidean distance between the two points and keep the smallest. Or if you prefer build a list of all nodes within a certain distance of the target.
 

Cogman

Lifer
Sep 19, 2000
10,283
134
106
Originally posted by: Markbnj
One way I did this in the past (I wrote an article for DDJ on the technique in 1993) is to presort the existing colors into a BSP tree. Since colors can be interpreted as sparse points in a 3D volume where r=x, g=y, b=z (for example), and palettes are usually pretty static, the problem lends itself nicely to a tree-based search. If you're not familiar with BSP trees they rotate the index of comparison at each level of the tree, and create a spatial partitioning.

So basically to find matches within a certain tolerance from a particular color you begin by comparing red at level 0, and if the target color is less than the top node's red component you go left, otherwise you go right. At the next level you compare green and do the same, and so on for blue, and then back to red. At each level you calculate the euclidean distance between the two points and keep the smallest. Or if you prefer build a list of all nodes within a certain distance of the target.

Hum, guess I wasn't clear enough. The searching is being done on a bitmap, not a color plane. right now, the test if a give points color is close enough is just a simple RGB check (if color1.r - color2.r < Tolerance, theres a match, ect).

Imagine taking a current screenshot an then starting from a point looking for all the white on the screen (white being determined by the tolerance you input). And then reporting back every point on the screen that is white. That is basically what I am trying to do (in a reasonable amount of time)

Though, using a euclidean distance to check the tolerance seems like a good idea to me (actually, I wanted to use HSL but it broke compatability with the other languages function)
 

Markbnj

Elite Member <br>Moderator Emeritus
Moderator
Sep 16, 2005
15,682
14
81
www.markbetz.net
Ah, ok, I think a similar technique would still work, though you would need more data in the tree nodes.

Suppose you had one node in the BSP tree for every unique color in the bitmap, and that the node contained a list of the pixels that are set to that color... getting your result would be a simple tree traversal, adding the list of pixels for each match to a results list.

If there is any way you can pre-sort the colors into an ordered structure such as a BSP tree you should see an order of magnitude decrease in execution time. Of course, I don't know what algorithm the "FindColorsTolerance" function is using now.