Skip to main content

Algorithm to sort edge list of simple polygon for 2D and 3D

Sometimes it is handy to sort an edge list. In this case I needed an algorithm to test for concavity of a simple 3D polygon with just one face. You can also apply the procedure on 2D because it just sorts an edge list that could contain either 2D or 3D vertices.

The polygons were made in Blender v.2.67, so the script had to be written in Python and executed via the Run Script button in the text editor. I didn't want to use fancy algorithms to sort edges because we're dealing with simple polygons, so I ended up writing my own. As a side note, the edge-angle checkbox in Blender, which can be used to see if a polygon is convex or concave didn't work for me, so I had no other choice but to first sort edges before I can apply angle calculations on consecutive vertices. Suggestions for improvements are welcome and hopefully it helps someone else who had to deal with the same (or similar) issues in Blender!

The basic idea is that you build up your sorted edge list e step by step, starting by adding a first element. Next, there is a main loop that is as long as all the elements m contained in the unsorted edge list mesh.edges. Each edge contains a start vertex [0] and an end vertex [1]. What I did was: at each step you search for a match between the last inserted [1] of e and a target [0] of m. Sometimes, edges are added in a reversed direction in mesh.edges, so if the first search didn't find anything, than perhaps looking in the opposite direction (when [1] of m is equal to [1] of e but it was not already added to e), would result in a match. When this happens, the direction of the edge has to be switched, and a duplicate of the data is created to be able to switch the direction and add this switched direction into e. The drawback is that now, in the main search, the algorithm has to check if switched edges have not been added into e as well. I've tested it with meshes with 100+ vertices, and I didn't see any performance issues, but like I said before suggestions for improvements are more than welcome :)


  1. Be sure to be in Edit Mode.
  2. Be sure to be in Edge Select Mode.
  3. Be sure to have all edges selected.

Here is the script:


Anonymous said…
Players mark off randomly drawn numbers on their playing cards in the hopes of overlaying a whole line. Players can win by creating horizontal, vertical, or diagonal lines or overlaying the entire card. Blackjack is one other popular selection among on line casino table video games, particularly for gamers in search of a less skill-based sport than poker. During a blackjack sport, punters play in opposition to a dealer to win betting rounds. Players goal to collect as high a quantity as possible in 온라인카지노 each spherical with out exceeding 21 factors. No-deposit bonuses like cashback promotions, weekly bonus spins, and membership rewards present online on line casino gamers with tons of opportunities to earn big money.

Popular posts from this blog

But Google what about mobile phones that do not support Javascript?

In the global device market, there are still between 0.2% and 5.4% of phones that do not support Javascript, at least in these set of countries according to this site. In case your mobile website falls within this set than what do you do when you want to optimize CSS delivery by deferring the loading of some CSS but still serving the complete CSS to non-Javascript websites?

A Short Online Letter to the Board of Alphabet Inc.

Dear Chairman Hennessy, I would like to openly share a question that kept coming back to me in the past couple of days, and that gave me courage to write a short open letter for the first time in my life. While catching up with daily news I came across a couple of articles in the past week alone, namely on the world’s remaining wilderness areas that are under threat . That the Earth’s oceans have retained 60 percent more heat each year than we’ve previously thought, that humanity has wiped out 60% of animal populations since 1970, that China has legalised rhino horn and tiger bone usage after 25 years, to calling for urgent action to develop technologies for negative emissions because our clean energy efforts won’t be enough. Here’s the question: is there actually a future for us, for your company, for humanity and our natural environment? What we do today will lay down the trajectory for our carrying capacity on Earth. Instead of investing in self-driving transportation and

A scalable geometrical model for muscle and tendon units: An algorithmic solution on how to fit a template muscle on a high resolution muscle mesh

The reason for this blog post is to share a bit on a particular hard problem that I've encountered during my Master's thesis with a broader audience. I will try my best to write it in plain English, but as the problem is complex expect this to be a lengthy post with domain specific terminology.