Programming a Simple Polygon Editor

Categories:

polygon-editor-icon-1Part of my job at PADT is writing custom software for our various clients.  We focus primarily on developing technical software for the engineering community, with a particular emphasis on tools that integrate with the ANSYS suite of simulation tools.  Frankly, writing software is my favorite thing to do at PADT, simply because software development is all about problem solving.

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.

polygon-editor-f01

What should happen if the user drags this node over on top of that node:polygon-editor-f02

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”

polygon-editor-f03Conceptually, this sounds pretty simple, but how do you do it programmatically?  To give some background, note that the nodes in my polygon class are stored in a simple, ordered C++ std::list<>.

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:polygon-editor-f04Pretty simple.  For a closed polygon, my class maintains a flag and simply draws an edge from the last node to the first node.

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:

polygon-editor-f05polygon-editor-f06

Here is another example:

polygon-editor-f07
polygon-editor-f09b

Finally, here is one more:polygon-editor-f08polygon-editor-f09

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:polygon-editor-f10We left rotate until we have this:polygon-editor-f11That’s great, but what does that buy us?  Well, now that one of the participating nodes is at the head of the list, our problem is much simpler because all of the nodes that we need to delete are now at either end of the list.  The only question left to answer is which end of the list do we trim off?  The answer to that question is trivial.  We simply trim off the shorter end of the list with respect to the source node (the green node in the diagram). The “lengths” of the two lists are defined as follows.  For the head section, it’s the number of nodes up to, but not including the source. (This section obviously includes the target node)  For the tail, it’s the number of nodes from the source to the end, including the source.  (This section includes the source node).  Since we define the two sections this way we are guaranteed to delete either the source or the target, but not both.  Its fine to delete either one of them, because at this point we’ve deemed the geometrically coincident, but we must not accidentally delete both!!

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:

polygon-editor-f12Here is the rotated list:polygon-editor-f13So, in this case, the “end” of the list (including the source) is the shortest.  If it is a tie, then it doesn’t matter, just pick one.  Interestingly enough, if the two nodes are adjacent in the original list, then the rotated list will look like either this:polygon-editor-f14 Or this, if the source is “before” the target in the original list:polygon-editor-f15In either case, the algorithm works unchanged, and we only delete one node.  It’s beautiful! (At least in my opinion…)  Modern C++ makes this type of code really clean and easy to write.  Here is the entire thing, including the search to located geometrically adjacent nodes as well as the merge. The standard library algorithms really help out!

// 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;
Categories

Get Your Ansys Products & Support from the Engineers who Contribute to this Blog.

Technical Expertise to Enable your Addictive Manufacturing Success.

PADT Pulse Newsletter Screen Grab from March 2023

PADT’s Pulse Newsletter

Keep up to date on what is going on at PADT by subscribing to our newsletter.


By submitting this form, you are consenting to receive marketing emails from: . You can revoke your consent to receive emails at any time by using the SafeUnsubscribe® link, found at the bottom of every email. Emails are serviced by Constant Contact

Share this post:

Upcoming Events

05/31/2023

Driving Automotive Innovation with Additive - Webinar

05/24/2023

Hill Air Force Base Tech Expo

05/24/2023

Structural Updates in Ansys 2023 R1 (3) – Structural Optimization & Ex

05/23/2023

CROSSTALK 2023: Emerging Opportunities for Advanced Manufacturing Smal

05/10/2023

Signal & Power Integrity Updates in Ansys 2023 R1 - Webinar

04/26/2023

Additive Manufacturing Updates in Ansys 2023 R1 - Webinar

04/20/2023

38th Space Symposium Arizona Space Industry

More Info

04/19/2023

38th Space Symposium
Arizona Space Industry

04/19/2023

Additive Aids for Manufacturing - Webinar

04/18/2023

38th Space Symposium
Arizona Space Industry

04/17/2023

38th Space Symposium

04/13/2023

Venture Madness 2023

04/12/2023

Fluid Meshing & GPU-Solver Updates in Ansys 2023 R1 - Webinar

03/29/2023

8th Thermal and Fluids Engineering Conference

03/29/2023

Structural Updates in Ansys 2023 R1 - Composites, Fracture & MAPDL

03/28/2023

8th Thermal and Fluids Engineering Conference

03/27/2023

8th Thermal and Fluids Engineering Conference

03/26/2023

8TH Thermal and Fluids Engineering Conference

03/24/2023

Arizona BioPreneur Conference | Spring 2023

03/22/2023

2023 Arizona MedTech Conference

03/22/2023

Optimize Jigs & Fixtures with Additive - Webinar

03/15/2023

3D Design Updates in Ansys 2023 R1 - Webinar

03/08/2023

Competitive Advantages of 1D/3D Coupled Simulation - Webinar

03/01/2023

High Frequency Updates in Ansys 2023 R1 - Webinar

02/22/2023

Additive Advantages in Aerospace - Webinar

02/15/2023

Structural Updates in Ansys 2023 R1 (1) - Webinar

02/09/2023

IME 2023: MD&M | WestPack | ATX | D&M | Plastek

02/08/2023

IME 2023 MD&M | WestPack | ATX | D&M | Plastek

02/07/2023

IME 2023 MD&M | WestPack | ATX | D&M | Plastek

01/27/2023

Arizona Photonics Days, 2023

01/26/2023

Arizona Photonics Days, 2023

01/26/2023

TIPE 3D Printing | 2023

01/26/2023

Venture Cafe Phoenix Talent Night - Job Fari

01/26/2023

VFS 2023 Autonomous/Electric VTOL Symposium

01/25/2023

Arizona Photonics Days, 2023

01/25/2023

Building A.M.- Utah: Kickoff!

01/25/2023

TIPE 3D Printing | 2023

01/25/2023

VFS 2023 Autonomous/Electric VTOL Symposium

01/24/2023

VFS 2023 Autonomous/Electric VTOL Symposium

01/24/2023

TIPE 3D Printing | 2023

01/18/2023

2023 AZ Tech Council Golf Tournament

12/21/2022

Simulation Best Practices for 5G Technology - Webinar

12/14/2022

Digital Twins Updates in Ansys 2022 R2 - Webinar

12/08/2022

Tech the Halls - AZ Tech Council Holiday Mixer

12/07/2022

Electric Vehicle and Other Infrastructure Update Panel

11/30/2022

SPEOS Updates in Ansys 2022 R2 - Webinar

11/23/2022

Simulation Best Practices for Electronics Reliability - Webinar

11/16/2022

Discovery Updates in Ansys 2022 R2

11/10/2022

VentureCafe Phoenix Panel: Venture Capital in AZ

11/08/2022

2022 GOVERNOR’S CELEBRATION OF INNOVATION AWARDS + TECH SHOWCASE

11/03/2022

VentureCafe Phoenix Panel: Angel Investment in AZ

11/02/2022

High & Low Frequency Electromagnetics Updates in Ansys 2022 R2

10/26/2022

Simulation Best Practices For Chip-Package-System Design & Development

10/20/2022

Nerdtoberfest 2022

10/19/2022

2022 Southern Arizona Tech + Business Expo

10/19/2022

LS-DYNA Updates in Ansys 2022 R2 - Webinar

10/17/2022

Experience Stratasys Truck Tour - Clearfield Utah

10/14/2022

ASU School of Manufacturing Systems and Networks - Formal Opening Cele

10/14/2022

Experience Stratasys Truck Tour - Midvale Utah

10/12/2022

Experience Stratasys Truck Tour - Littleton Colorado

10/06/2022

Fluids Updates in Ansys 2022 R2 - Webinar

10/05/2022

Experience Stratasys Truck Tour - Colorado Springs

09/29/2022

White Hat Life Science Investor Conference - 2022

09/28/2022

2022 AZBio Awards

09/28/2022

Simulation Best Practices for Rotating Machinery Design & Development

09/21/2022

ExperienceIT NM 2022

09/21/2022

Additive Updates in Ansys 2022 R2 - Webinar

09/14/2022

Rocky Mountain Life Sciences Investor & Partnering Conference

09/08/2022

Ansys Optics Simulation User Group Meeting - Virtual

09/08/2022

Ansys Optics Simulation User Group Meeting

09/07/2022

SI & PI Updates in Ansys 2022 R2 - Webinar

08/31/2022

Simulation Best Practices for Developing Medical Devices - Webinar

08/24/2022

Mechanical Updates in Ansys 2022 R2 - Webinar

08/10/2022

Tucson after5 Tech Mixer: Ruda-Cardinal

08/05/2022

Flagstaff Tech Tour, 2022

08/02/2022

2022 CEO Leadership Retreat

08/01/2022

2022 CEO Leadership Retreat

07/27/2022

Thermal Integrity Updates in Ansys 2022 R1 - Webinar

07/20/2022

Simulation Best Practices for the Pharmaceutical Industry - Webinar

07/14/2022

NCMS Technology Showcase: Corpus Christi Army Depot

07/13/2022

NCMS Technology Showcase: Corpus Christi Army Depot

07/13/2022

Additive & Structural Optimization Updates in Ansys 2022 R1 - Webinar

07/07/2022

Arizona AADM Conference, 2022

06/29/2022

LS-DYNA Updates & Advancements in Ansys 2022 R1 - Webinar

06/23/2022

Simulation Best Practices for Wind Turbine Design - Webinar

06/15/2022

MAPDL Updates & Advancements in Ansys 2022 R1 - Webinar

06/01/2022

Mechanical Updates in Ansys 2022 R1 - pt. 2 Webinar

05/26/2022

Modelling liquid cryogenic rocket engines in Flownex - Webinar

05/25/2022

SMR & Advanced Reactor 2022

05/25/2022

05/24/2022

SMR & Advanced Reactor 2022

05/19/2022

RAPID + tct 2022

05/19/2022

Venture Cafe Roundtable: AI & Healthcare

05/18/2022

Tucson after5 Tech Mixer: World View

05/18/2022

RAPID + tct 2022

More Info

05/18/2022

Signal & Power Integrity Updates in Ansys 2022 R1 - Webinar

05/18/2022

Simulation World 2022

05/17/2022

RAPID + tct 2022

05/11/2022

Experience Stratasys Manufacturing Virtual Event

Search in PADT site

Contact Us

Most of our customers receive their support over the phone or via email. Customers who are close by can also set up a face-to-face appointment with one of our engineers.

For most locations, simply contact us: