This morning I got to work on a fairly simple feature of a much larger tool that I am currently developing. The feature I’m working on involves graphically editing polygons. Why, you ask am I doing this? Well, that I can’t say, but nonetheless I can share a particularly interesting problem (to me at least) that I got to take a swing at solving. The problem is this:
When a user is editing a node in the polygon by dragging it around on the screen, how do you handle the case when they drop it on an existing node?
Consider this polygon I sketched out in a prototype of the tool.
What should happen if the user drags this node over on top of that node:
Well, I think the most logical thing to do is that you merge the two nodes together. Implementing that is pretty easy. The slightly harder question is what to do with the remaining structure of the polygon? For my use case, polygons have to be manifold in that no vertex is connected to more than two edges. (The polygons can be open and thus have two end vertices connected to only one edge.) So, what part do you delete? Well, my solution is that you delete the “smaller” part, where “smaller” is defined as the part that has the fewest nodes. So, for example, this is what my polygon looks like after the “drop”
Now, I use a std::list<> simply because I know I’m going to be inserting and deleting nodes at random places. Linked lists are great for that, and for rendering, I have to walk the whole list anyway, so there’s no performance hit there. Graphically, my data structure looks
something like this:
The rub comes when you start to realize that there are tons of different ways a user might try to merge nodes together in either an open or closed polygon. I’ve illustrated a few below along with what nodes would need to be merged in the corresponding data structure. In the data structure pictures, the red node is the target (the node on which the user will be dropping) and the green node is the one they are manipulating (the source node).
Here is one example:
Here is another example:
In all these examples, we have different “cases” that we need to handle. For instance, in the first example the portion of the data structure we want to keep is the stuff between the source and target nodes. So, the stuff on the “ends” of the list needs to be deleted. In the middle case, we just need to merge the source and target together. Finally, in the last case, the nodes between the source and target need to be deleted, whereas the stuff at the “ends” of the list need to be kept.
This simple type of problem causes shivers in many programmers, and I’ll admit, I was nervous at first that this problem was going to lead to a solution that handled each individual case respectively. Nothing in all of programming is more hideous than that. So, there has to be a simple way to figure out what part of the list to keep, and what part of the list to throw away.
Now, I’m sure this problem has been solved numerous times before, but I wanted to take a shot at it without googling. (I still haven’t googled, yet… so if this is similar to any other approach, they get the credit and I just reinvented the wheel…) I remember a long time ago listening to a C++ programmer espouse the wonders of the standard library’s algorithm section. I vaguely remember him droning on about how wonderful the std::rotate algorithm is. At the time, I didn’t see what all the fuss was about. Now, I’m right there with him. std::rotate is pretty awesome!
std::rotate is a simple algorithm. Essentially what it does is it takes the first element in a list, pops it off the list and moves it to the rear of the list. Everything else in the list shifts up one spot. This is called a left rotate, because you can imagine the items in the list rotating to the left until they get to the front of the line, at which point they fall off and are put back on the end of the list. (Using reverse iterators you can effectively perform a right rotate as well.) So, how can we take advantage of this to simplify figuring out what needs to be deleted from our list of nodes?
Well, the answer is remarkably simple. Once we locate the source and target nodes in the list, regardless of their relative position with respect to one another or to the ends of the list, we simply left rotate the list until the target becomes the head of the list. That is, if we start with this:
In the example just given, after the rotate, we would delete the head of the list. However, let’s take a look at our first example. Here is the original list:
// Search lambda function for looking for any other node in the list that is
// coindicent to this node, except this node.
auto searchAdjacentFun = [this, pNode](const NodeListTool::AdjustNodePtrT &pOtherNode)->bool
{
if (pNode->tag() == pOtherNode->tag()) return false;
return (QVector2D(pNode->pos() - pOtherNode->pos()).length() < m_snapTolerance); }; auto targetLoc = std::find_if(m_nodes.begin(), m_nodes.end(), searchAdjacentFun); // If we don't find an adjacent node within the tolerance, then we can't merge if (targetLoc == m_nodes.end()) { return false; } // Tidy things up so that the source has exactly the same position as the target pNode->setPos((*targetLoc)->pos());
// Begin the merge by left rotating the target so that it is at the
// beginning of the list
std::rotate(m_nodes.begin(), targetLoc, m_nodes.end());
// Find this node in the list
auto searchThis = [this, pNode](const NodeListTool::AdjustNodePtrT &pOtherNode)->bool
{
return (pNode->tag() == pOtherNode->tag());
};
auto sourceLoc = std::find_if(m_nodes.begin(), m_nodes.end(), searchThis);
// Now, figure out which nodes we are going to delete.
auto distToBeg = std::distance(m_nodes.begin(), sourceLoc);
auto distToEnd = std::distance(sourceLoc, m_nodes.end());
if (distToBeg < distToEnd) { // If our source is closer to the beginning (which is the target) // than it is to the end of the list, then we need to delete // the nodes at the front of the list m_nodes.erase(m_nodes.begin(), sourceLoc); } else { // Otherwise, delete the nodes at the end of the list m_nodes.erase(sourceLoc, m_nodes.end()); } // Now, see if we still have more than 2 vertices if (m_nodes.size() > 2) {
m_bClosed = true;
}
else {
m_bClosed = false;
}
return true;