Priority queue not processed in expected order

This is a discussion on Priority queue not processed in expected order within the C++ Programming forums, part of the General Programming Boards category; Hello, I am trying to implement a priority queue in an OpenGL program and am getting unexpected results. I have ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    27

    Priority queue not processed in expected order

    Hello,

    I am trying to implement a priority queue in an OpenGL program and am getting unexpected results.

    I have an original image. The user colors different parts of this image one of three colors, with each color representing a different value of rigidity for that portion of the image. Then, when the user clicks and drags a point in the image, that image stretches depending on the rigidity of its parts. I want the connected, rigid parts of the image to move together, so I have implemented a priority queue to determine where each pixel of the image ends up after deformation, with the most rigid portions processed first.

    The problem is that currently, the priority processes most of the rigid points together, but not all of them. I have output the order the points are being processed to confirm this, and it is not an OpenGL issue. Because of this issue, those rigid portions of the image don't stay together when they move. Does anyone have any suggestions?

    I define my priority queue thusly:
    Code:
    std::priority_queue<DeformationCandidate> _deformationQueue;
    A simplified version of the relevant code segment is below. It begins after the image has been colored and the user starts the stretching of the image.

    Code:
            //Move the pixel nearest to the mouse click and drag
    
            //Add the first pixel's neighbors to the deformation queue
    
            //Process the neighbors queue
    	while (!_deformationQueue.empty())
    	{
    		//Grab the candidate pixel for deformation from the neighbors queue
    		DeformationCandidate candidatePoint = _deformationQueue.top();
    		_deformationQueue.pop();
    
    		
    		//If the point has not already been processed, do so using the deformation of its sponsor point
    		if (!deformed)
    		{
    			//Calculate how much the point moved
    
    			//If the point was moved, we add its neighbors to the queue
    			//xShift and yShift are the x and y displacements of the point
    			if ((fabs(xShift) > 0.0) && (fabs(yShift) > 0.0))
    			{
    				//Add that point's neighbors to the queue to be processed
    				_addNeighbors(candidatePoint.row, candidatePoint.column);
    			}
    		}
    
    		//Flag the point as deformed so we don't keep processing already deformed points
    		deformed = true;
    	}
    DeformationCandidate.h is:
    Code:
    #ifndef DEFORMATION_CANDIDATE
    #define DEFORMATION_CANDIDATE
    
    class DeformationCandidate
    {
    private:
    public:
    	DeformationCandidate();
    	~DeformationCandidate(){};
    
    	//The row and column number of the candidate point
    	int row, column;
    
    	//The row and column number for the sponsor point.
    	//The sponsor point is the point whose movent caused our candidate point to deform
    	int sponsorRow, sponsorColumn;
    
    	//The tissue dentisty of the candidate point
    	int rigidity;
    
    	int get_rigidity()
    	{
    		return rigidity;
    	}
    	
    	//Overloaded operators to appropriately order priority queue
    	bool operator==(const DeformationCandidate& rhs) const;
    
    	bool operator<(const DeformationCandidate& rhs) const;
    
    	bool operator>(const DeformationCandidate& rhs) const;
    };
    #endif
    and DeformationCandidate.cpp is:
    Code:
    # include "DeformationCandidate.h"
    
    DeformationCandidate::DeformationCandidate()
    {
    	//Initialize variable values
    	row = -1;
    	column = -1;
    	rigidity = -1;
    	sponsorRow = -1;
    	sponsorColumn = -1;
    
    }
    
    bool DeformationCandidate::operator==(const DeformationCandidate& rhs) const
    {
    	return (*this).rigidity == rhs.rigidity;
    }
    
    bool DeformationCandidate::operator<(const DeformationCandidate& rhs) const
    {
    	return (*this).rigidity < rhs.rigidity;
    }
    
    bool DeformationCandidate::operator>(const DeformationCandidate& rhs) const
    {
    	return (*this).rigidity > rhs.rigidity;
    }
    Thanks,
    JackR

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Do you realise that after the first time through that loop the "deformed" flag is permanently set and it becomes the same as:
    Code:
    while (!_deformationQueue.empty())
    {
    	//Grab the candidate pixel for deformation from the neighbors queue
    	DeformationCandidate candidatePoint = _deformationQueue.top();
    	_deformationQueue.pop();
    }
    I.e. it does something with the first item and then empties the entire thing.
    Or, there's got to be some piece of information missing from what you have posted.

    You don't need that destructor because it's empty, public and non-virtual.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    27
    iMalc,

    Thank you for your reply.

    Deformed is a property of each pixel in the original image. I tried to show the section of the code where I thought the problem may have been, and I apologize for the error.

    It should have been:

    Code:
            
    	//First, set the deformed variable for all points to false (not deformed)
    	for (int rowNum = 0; rowNum < image.rows; rowNum++)
    	{
    		for (int columnNum = 0; columnNum < image.columns; columnNum++)
    		{
                            image.deformed[rowNum][columnNum] = true;
    		}
    	}
    
            //Move the pixel nearest to the mouse click and drag
    
            //Add the first pixel's neighbors to the deformation queue
    
            //Process the neighbors queue
    	while (!_deformationQueue.empty())
    	{
    		//Grab the candidate pixel for deformation from the neighbors queue
    		DeformationCandidate candidatePoint = _deformationQueue.top();
    		_deformationQueue.pop();
    
    		
    		//If the point has not already been processed, do so using the deformation of its sponsor point
    		if (!image.deformed[candidatePoint.row][candidatePoint.column])
    		{
    			//Calculate how much the point moved
    
    			//If the point was moved, we add its neighbors to the queue
    			//xShift and yShift are the x and y displacements of the point
    			if ((fabs(xShift) > 0.0) && (fabs(yShift) > 0.0))
    			{
    				//Add that point's neighbors to the queue to be processed
    				_addNeighbors(candidatePoint.row, candidatePoint.column);
    			}
    		}
    
    		//Flag the point on the original image as deformed so we don't keep processing already deformed points
    		image.deformed[candidatePoint.row][candidatePoint.column] = true;
    	}
    I am still not sure what my issue is.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Priority queue
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2007, 12:30 AM
  2. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-14-2007, 11:48 PM
  3. Level order traversal w/o queue
    By curlious in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 06-16-2004, 07:54 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. queue help
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-29-2001, 08:38 AM

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