Need suggestions for an algorithm

This is a discussion on Need suggestions for an algorithm within the Tech Board forums, part of the Community Boards category; I have a 1000 entry color table represented graphically by a long bar, 1000 pixels wide. Each table entry is ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    321

    Need suggestions for an algorithm

    I have a 1000 entry color table represented graphically by a long bar, 1000 pixels wide.
    Each table entry is a vertical line 1 pixel wide and 20 pixels high.

    Only a relatively small number of colors (minimun 2, maximum 56) are entered by the user.
    These are what I call "nodes" and can be placed anywhere within the table. The rest of the
    table entries, between the nodes, are calculated by the program. Just beneath the color bar
    are small markers which show the actual node positions.

    For editing purposes, the nodes are displayed as colored rectangles in a field just below the
    color table.

    It kind of looks like this, although with graphic elements, not text (and also not to scale):

    Code:
    ||||||||||||||||||||||||||||||||||||||||||||||||||||||||    color table
    ^     ^      ^               ^^                        ^    node position markers
    
    [ ]   [ ]   [ ]   [ ]   [ ]   [ ]                           nodes
    What I would like to do is arrange the nodes in their field so that each corresponds as closely
    as possible to it's actual table entry just above it. When the node positions are far enough apart,
    this can be done exactly. But because the node rectangles are many pixels wide, some of these
    rectangles will need to be displaced from the actual position above in the table when the positions
    are too close.

    The end result should look something like this:

    Code:
    ||||||||||||||||||||||||||||||||||||||||||||||||||||||||    color table
    ^     ^      ^               ^^                        ^    node position markers
    
    [ ]  [ ]    [ ]           [ ]  [ ]                   [ ]    nodes
    In the above two illustrations, it was quite easy to do manually. I could also do it easily for some
    other arrangement, manually. The main problem though, is that there are a huge number of possible
    patterns. I can't think of a way to handle any possible arrangement. Is there something related to this
    that could provide a useful algorithm?

    I can scan through the nodes and collect all types of data, but I'm not sure what to with it next. It seems
    that there is some judgement that needs to be made, and that's where I'm stuck.
    How do I translate what I easily did above just by looking at it, into a general procedure?

  2. #2
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    You may be able to represent your nodes as a graph, where the distance between nodes (vertices) is the edge weight. Ideally I assume you would like to center your node directly under it's corresponding marker. With a graph you can examine the distance to adjacent nodes and determine if you need to add an offset to that ideal positioning (directly underneath the marker) or divide the available space amongst closely positioned nodes.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    Quote Originally Posted by Subsonics View Post
    You may be able to represent your nodes as a graph, where the distance between nodes (vertices) is the edge weight. Ideally I assume you would like to center your node directly under it's corresponding marker. With a graph you can examine the distance to adjacent nodes and determine if you need to add an offset to that ideal positioning (directly underneath the marker) or divide the available space amongst closely positioned nodes.
    Working with the space or distance between the nodes does seem like a better approach.
    Is there anything in weighted graph theory that could be useful here? I have a basic idea of what a graph is,
    but not familiar with the graph operations.
    Also, would your suggestion be similar to my last idea below?

    What I have thought of so far:

    I believe this cannot simply be done by scaling. I thought of expanding the table positions by a factor of 18
    (18 is my node rectangle pitch) to move the table entries at least 18 pixels apart. But now if I try to reduce
    the space between them proportionately, certain spaces may reach their minimum limit of 18 and throw off
    the ending size of the scaled down field.
    The idea here was to add in the required space between nodes and keep everything proportional by expanding
    it. Then reduce all the spaces proportionately. But some spaces scale and some don't. Possibly this might work
    if several passes are made, redefining the parameters each time a space limit is encountered.

    I also thought of simply placing them in position one by one, and adjusting them as necessary. But when room
    needs to be made for the new node, a decision needs to be made concerning which ones to move. Not sure
    how to determine this at that point in the procedure. Possibly the number of different cases that need to be handled
    is not really that large. I have to think about this one some more.

    My only other idea is some type of mutiple pass procedure that looks at errors from best position and repeats the
    adjustments until the overall errors are minimum. This could be a possibility if I can figure out a way to weight the
    errors to get groups to be centered, if possible.

  4. #4
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by megafiddle View Post
    Working with the space or distance between the nodes does seem like a better approach.
    Is there anything in weighted graph theory that could be useful here? I have a basic idea of what a graph is,
    but not familiar with the graph operations.
    A "weight" can mean anything you want it to in order to fit a graph onto your problem, in this case distance in pixels would be the edge weight. It's not necessarily graph operations that could be useful (as far as I know, there may be graph algorithms that readily solves your problem), but the representation of your nodes as a "graph". I put that in quotes since it's basically a list, but you could easily create a data structure that holds a reference to a node and it's it's distance to adjacent nodes in pixels. After that step, knowing the minimum distance required you could easily update it by moving your node representations in your graph until the minimum space property is fulfilled. You could try to render after the new positioning and experiment with different ways of allocating/dividing space for competing nodes.

    Quote Originally Posted by megafiddle View Post
    Also, would your suggestion be similar to my last idea below?
    Not sure I follow you completely but the last paragraph seems to be most similar afaik.
    Last edited by Subsonics; 03-18-2013 at 11:41 AM.

  5. #5
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    Quote Originally Posted by Subsonics View Post
    A "weight" can mean anything you want it to in order to fit a graph onto your problem, in this case distance in pixels would be the edge weight. It's not necessarily graph operations that could be useful (as far as I know, there may be graph algorithms that readily solves your problem), but the representation of your nodes as a "graph". I put that in quotes since it's basically a list, but you could easily create a data structure that holds a reference to a node and it's it's distance to adjacent nodes in pixels. After that step, knowing the minimum distance required you could easily update it by moving your node representations in your graph until the minimum space property is fulfilled. You could try to render after the new positioning and experiment with different ways of allocating/dividing space for competing nodes.



    Not sure I follow you completely but the last paragraph seems to be most similar afaik.
    Ok, thanks. I'm going to try that. And rendering to observe the progress is a good idea.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,159
    Implement a repulsive force between the markers which drops to zero beyond a certain distance, and an attractive force between each marker and its corresponding entry in the color table. Minimize the total potential energy. Play with the parameters (basically, the strength of the two kinds of forces) until you get a pleasing result.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    Quote Originally Posted by brewbuck View Post
    Implement a repulsive force between the markers which drops to zero beyond a certain distance, and an attractive force between each marker and its corresponding entry in the color table. Minimize the total potential energy. Play with the parameters (basically, the strength of the two kinds of forces) until you get a pleasing result.
    That's an interesting idea also. Could be pretty neat if the nodes were modeled as cellular automata. They could adjust themselves.
    (I have also been working on another program, John Conway's "Life". It gave me that idea).

    Anyway, still working on it.

  8. #8
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    I came up with something that seems to work.

    The ideas from subsonics and brewbuck are more interesting approaches, but I could not find a way to impliment them.
    The main problem was anticipating and handling the various patterns that could occur. Things became much simpler
    when I handled the lower and upper ends of the node field independantly from the inner region.
    Groups at the lower and upper ends cannot be centered as groups in the inner region can be. At best you can only
    left justify or right justify the groups. The node field ends at the lower and upper limits of the color table.
    (A group is any sequence of nodes which are too close to each other to align with their actual positions; they would
    have to overlap. So they need to be separated, or expanded)

    After the ends are aligned, the inner groups (if any) are all handled in a consistant way. The groups will be centered
    and if a group impinges on an adjacent node or group, it will merge with it and form a new larger group on the next
    pass of the algorithm.

    It looks like this:

    Code:
    void setnodefields(void)
    {   int n,  n1, n2, gsize, center, g1, g2, x;
    
        for( n = 0; n < nnodes; n++ )                                       // set initial field positions to actual table positions
            nodef[n] = nodep[n];
    
        g1 = 1;
        while( g1 )                                                 // repeat until all groups expanded and aligned
        {   n = 1;
            n1 = 1;
            while( nodef[n]-nodef[n-1] <= NODEPITCH && n < nnodes-1 )       // align any group at left end
            {   nodef[n] = nodef[n-1]+NODEPITCH;
                n1 = ++n;
            }
    
            n = nnodes-2;                                               // align any group at right end
            n2 = nnodes-2;
            while( nodef[n+1]-nodef[n] <= NODEPITCH && n > 0 )
            {   nodef[n] = nodef[n+1]-NODEPITCH;
                n2 = --n;
            }
    
            n = n1;
            g1 = 0;
            while( ! g1 && n < n2 )                                     // locate internal group
            {   if( nodef[n+1]-nodef[n] < NODEPITCH )
                {   g1 = n;
                    while( nodef[n+1]-nodef[n] < NODEPITCH && n < n2 )
                        g2 = ++n;
    
                    gsize = g2+1-g1;                                    // expand and center group
                    center = ( nodep[g2]+nodep[g1] )/2;
                    nodef[g1] = center-( gsize*NODEPITCH-NODEGAP )/2;
                    for( n = g1+1; n <= g2; n++ )
                        nodef[n] = nodef[n-1]+NODEPITCH;
                }
    
                n++;
            }
        }
    
        for(n = 0; n < nnodes; n++)                                // set node rectangles
        {   x = n*NODEPITCH;
            nsubfield[n].top = 0;
            asubfield[n].top = NODEHEIGHT/2;
            asubfield[n].bottom = NODEHEIGHT;
    
    
            if(link[n] == LINK1)
                asubfield[n].left = nsubfield[n].left = x+2;
            else if(link[n] == LINK2)
                asubfield[n].left = nsubfield[n].left = x-2;
            else
                asubfield[n].left = nsubfield[n].left =  nodef[n];
    
            asubfield[n].right = nsubfield[n].right = nsubfield[n].left+NODEWIDTH;
    
            if(altnode[n])
                nsubfield[n].bottom = nfield.top+NODEHEIGHT/2;
            else
                nsubfield[n].bottom = nfield.top+NODEHEIGHT;
        }
    }
    Last edited by megafiddle; 04-08-2013 at 08:55 PM.

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,159
    Nice work.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    Thanks!

    It does have your repulsive force to the extent that it causes a minimum separation between nodes.
    The attractive force is limited though to the very end nodes in a group, not so much the individual
    nodes within a group. More of a simple "centering". It does work out nicely though for isolated
    symmetrical groups.

    Also it incorporates Subsonic's ideas to an extent,, analyzing the spacing.

    Anyway, it seems to work without problems.
    Last edited by megafiddle; 04-11-2013 at 09:08 PM.

  11. #11
    Registered User
    Join Date
    Mar 2011
    Posts
    321
    Ok, doesn't quite work without problems.

    While moving the nodes around to test it further, certain patterns can cause it to oscillate between two different alignments.
    Fix was simple though - changed this:

    while( nodef[n+1]-nodef[n] < NODEPITCH && n < n2 )

    to this:

    while( nodef[n+1]-nodef[n] <= NODEPITCH && n < n2 )

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need suggestions
    By princez90 in forum C Programming
    Replies: 6
    Last Post: 05-15-2008, 10:13 PM
  2. Suggestions
    By Taikon in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 10:28 AM
  3. Hash algorithm suggestions
    By itsme86 in forum C Programming
    Replies: 4
    Last Post: 08-06-2004, 12:05 PM
  4. Any suggestions
    By bluehead in forum C++ Programming
    Replies: 10
    Last Post: 01-14-2002, 05:35 PM
  5. Thanks for the suggestions..
    By cozman in forum Windows Programming
    Replies: 4
    Last Post: 12-05-2001, 09:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21