An NLogN 2D Polygon Splitting Algorithm

I needed to come up with a solution to help designers authoring 2D polys over flat surfaces directly in Unreal Engine 4. I was also asked for a quick way to split up an authored polygon into multiple ones.

In a nutshell, designers wanted to define a 2D polygon, like the one in figure 1 but also have the ability to define internal segments:

Figure 1 – An example of a (split) polygon

I solved the authoring part by extending the UE4 spline component. However, I needed to keep the splitting part simple for both me to implement and for designers to use. I didn’t have much time and I had to find a quick solution that gave the best bang for the buck. I came up with two options:

  • Use one or more splines to partition the polygon.
  • Add another type of vertex to the spline component and use it as an “internal vertex”.
Figure 2 – Option one using splines on the left, option two using internal vertices on the right

The first option seemed appealing as it gave designers more authoring freedom. However, they also had to add more work creating (and authoring) more than one spline and on my end I had to write quite some boilerplate code to support that.

The second option seemed a hack but adding a second type of vertex to the spline component (actually to its metadata) seemed easy to do. And for designers it was definitely the easier option as well.

Maths is fun (really!!!)

After deciding to go with option #2 the only “bit” left was to write a 2D polygon splitting algorithm that given a convex or concave polygon and a list non intersecting segments spitted out a list of sub polygons indices.

Let’s take a look at a concrete example figure 3 and let’s (for fun) define the problem mathematically: $I$ represents the indices of our polygon and $S$ the pairs of indices that split the polygon.

Figure 3 – A poly to split

$ I = \{ k : k \in \mathbb{N} \} $
$ S =\{ {a\brack b} \in I \} $

so we have in figure 3:

$ I = \{ 0, 1, 2, 3, 4, 5, 6, 7 \} $
$ S = \{ (1,7), (1,6), (1,3), (1,4), (6,4) \} $

The expected outcome would be something similar to this:

$ T = \{ (1,7,0), (6,7,1), (6,1,4), (1,2,3), (1,3,4), (4,5,6) \} $

I have to admit that the first algorithm I came up with was just plain inefficient. It only needed to run in the Unreal Engine editor and surely designers weren’t going to create polys with hundred of thousands of vertices, so it turned out to be fine in the end.

I couldn’t live with it

Despite the algorithm wasn’t the fastest (although it worked), I kept thinking about at how inefficient my implementation was. Just to give you a hint, the time complexity was something like $ \theta (n^3)$, let alone space complexity which I’d like to omit if you don’t mind. Let’s pretend the following solution was the first I came up with.

After spending some time thinking through it, I came up with a better solution that runs in $ \theta (N log(N))$ time. It’s not super fast…but surely better than cubic time complexity!

Another one bites the maths

First of all we need to order our segment list S by the min absolute index difference. That is:

$ Min( Abs( a_i – b_i) ) $

Our set $S$ then becomes:

$ S = \{ (1, 3), (6, 4), (1,4), (1, 6), (1,7) \} $

Sorting an array isn’t too expensive (depending on the sorting algorithm of course). As an alternative a priority queue could be used instead, so elements are sorted upon insertion. Taking elements off a priority queue is not constant but it’s relatively cheap: $ \theta(\log n )$.

Now for each index pair in the sorted list $S$, let’s add the indices in between from $I$. Formally:

$ \forall {a\brack b} \in I \rightarrow P = \{ a_i, b_i – 1, …. , b_i – k, b_i : a_i < k < b_i : k \in I \} $

$ I = I – \{ b_i – 1, …., b_i – k \} $

If for any reason $ a_i, b_i $ are not in $I$ then we have intersecting internal segments. Our final list $T$ is going to be the union of P and what’s left in I.

$ T = P \cup I $

First segment in $S$ is $(1, 3) $ . We need to take all the indices still in $I$ between 1 and 3. In this case it’s going to be index 2 only and our first is $ (1, 2, 3) $ .

$ P_1 = \{ 1, 2, 3 \} $

Now we need to remove index 2 from $I$.
$ I = \{ 0, 1, \cancel{2}, 3, 4, 5, 6, 7 \} $

The second segment is $(6, 4)$, the index in between is 5. Let’s apply the same logic:

$ P_2 = \{ 6, 5, 4 \} $

Now remove 5 from $I$:
$ I = \{ 0, 1, \cancel{2}, 3, \cancel{5}, 6, 7 \} $

The third segment is $(1,4)$. Now, the indices in between are 2 and 3, but 2 is no longer in $I$ so we can use index 3 only. Which makes our third poly:

$ P_3 = \{ 1, 3, 4 \} $

And let’s remove 3 from $I$:

$ I = \{ 0, 1, \cancel{2}, \cancel{3}, \cancel{5}, 6, 7 \} $

And finally segment $(1, 7)$. Indices in between are 2, 3, 4, 5, 6, but only 6 is left within this range in $I$. Thus:

$ P_4 = \{ 1, 6, 7 \} $

$ I = \{ 0, 1, \cancel{2}, \cancel{3}, \cancel{5}, \cancel{6}, 7 \} $

So we only actually have $ (0, 1, 7) $ left in $I$ .

Now the last bit, we need to merge $P=\{ P_1, P_2, P_3, P_4 \} $ with what’s left in $I = \{ (0,1,7) \} $:

$ P = \{ (1,2,3), (4,5,6), (1,3,4), (1,6,7) \} $

$ T = \{ (1,2,3), (4,5,6), (1,3,4), (1,6,7) \} \cup \{ (0,1,7) \} $

$ T = \{ (1,2,3), (4,5,6), (1,3,4), (1,6,7), (0,1,7) \} $

Show me the code!

Ok ok…if you’ve had enough of this math nonsense so have I. Let’s put together a simple C++ script that does the job. Let’s first define the struct Segment, which contains the pair of indices to split the polygon and the comparison operator greater than and less than.

struct Segment
{
	int32_t indexFrom;
	int32_t indexTo;

	bool operator>(const Segment& other) const
	{
		return fabs(indexFrom - indexTo) > fabs(other.indexFrom - other.indexTo);
	}

	bool operator<(const Segment& other) const
	{
		return fabs(indexFrom - indexTo) < fabs(other.indexFrom - other.indexTo);
	}
};

Now the struct Poly that contains a list of indices

struct Poly
{
	std::vector<int32_t> indices;
	Poly()
	{
                // let's initialise the indices
		indices.reserve(6);
	}
};

and now the main function that does the work. I decided to use an inverted priority queue, that is a heap where the root is the smallest element.

bool find_polys(std::set<uint32_t>& indices, std::priority_queue<Segment, std::vector<Segment>, std::greater<Segment>>& segments, std::vector<Poly>& polys)
{
        // we know there are going to be S + 1 polys
	polys.reserve(segments.size() + 1);

	while(!segments.empty())
	{
		const Segment& segment = segments.top();
		polys.push_back(Poly());
		auto& polyIndices = polys.back().indices;
		int32_t indexFrom = fmin(segment.indexFrom, segment.indexTo);
		int32_t indexTo = fmax(segment.indexFrom, segment.indexTo);

		polyIndices.push_back(indexFrom);

		// if segment indices from and to have already been removed then we have intersecting segments!
		auto from = indices.find(indexFrom);
		if (from == indices.end() || indices.find(indexTo) == indices.end())
		{
			return false;
		}
		from++;
                // let's add indices in between from and to from I
		while (from != indices.end() && *from < indexTo)
		{
			polyIndices.push_back(*from);
			from = indices.erase(from);
		}
		polyIndices.push_back(indexTo);
		segments.pop();
	}
        // anything left in indices should be copied over to last poly in the list
	polys.push_back(Poly());
        // this should be the equivalent of a memcpy
	std::copy(indices.begin(), indices.end(), std::back_inserter(polys.back().indices));

	return true;
}

Asymptotic Complexity

It seemed to me the time complexity is $ \theta (N log(N))$ where the linear part is iterating over the segments and the logarithmic bit is for both adding the indices in between (and popping out the segment of the queue). I didn’t trust myself though so I installed google benchmark and wrote some code to stress test find_poly. I was not very familiar with it before, but it’s a well established library from google to benchmark code snippets and it also calculates asymptotic complexity! Exactly what I needed 🙂

For the benchmark I tested the function with with an increasing number of indices from 10 to 100,000. For the test I generated automatically the segments between the indices so that the polygon would be fan triangulated.

This is the benchmark code:

static void BM_find_poly(benchmark::State& state) 
{
	int numVertices = state.range(0);
	int numSegments = 0;
	for (auto _ : state)
	{
		std::vector <Poly> polys;
		state.PauseTiming();
                // let's build the input
		std::set<uint32_t> indices;
		std::priority_queue<Segment, std::vector<Segment>, std::greater<Segment>> segments;
		generateSegments(numVertices, segments, indices);
		numSegments = segments.size();
		state.ResumeTiming();
		find_polys(indices, segments, polys);
	}
        // set the number of elements
	state.SetComplexityN(numSegments + numVertices);
}

BENCHMARK(BM_find_poly)->Unit(benchmark::kMicrosecond)->RangeMultiplier(10)->Range(10, 1E5)->Complexity();

BENCHMARK_MAIN();
Figure 5 – Yes I called my PC Thanos…

And boom, I was right! yay! My implementation is indeed $ \theta (N log(N))$! I didn’t trust google benchmark (but I should have) so I plotted a graph in Excel using the output data:

Time complexity is in fact NLog(N)!

Conclusions

While it’s not an algorithm I’d personally employ at runtime in a game, it isn’t too slow to be used in an editor ( 32ms to process 100,000 vertices and 99,997 segments) considering I tested it on an old CPU from 2013.

I hope you have enjoyed the article, and you liked my 2D polygon splitting approach. If you manage to come up with a more efficient solution get in touch and let me know!

My four mistakes with Vim

I have always been curious about using Vim. The legend says you can write/edit text at the speed of thought. As a coder I have always been intrigued by that, and hoped to unlock the “code at the speed of thought” trophy by mastering it.

A few years ago I tried and installed Vim using a Visual Studio plugin called VsVim, which emulates most of Vim commands. I wasn’t very familiar with any of it or Vim’s modal nature so I naively thought I could easily pick it up just by using it.

The experience was awful.

I couldn’t get anything right, I was completely confused by Vim’s modal nature. Instead of writing code at the speed of thought I wasn’t actually writing anything that made sense whatsoever. I then tried to kill Vim with fire.*

*Vim was still fine after…I wasn’t..

Mistake #1 – I completely underestimated Vim

Curiosity was still there when a few months ago I decided to look at Vim again. It was difficult to grasp if Vim was still worth learning in 2020 with a lot of IDEs and plugin out there. However the idea of “writing code at the speed of thought” was still in my mind. Unfortunately, no matter how many articles I read or videos I watched about Vim I couldn’t really tell whether Vim was worth my while or not. I then figured there was no other option but to learn Vim myself if I wanted an answer to that question.

I also asked a few friends from different coding backgrounds (DevOps, C++ games developers, Javascript, C# and Python) what their opinion of Vim was. To summarise the feedbacks I got, except from devops, is that Vim is a sort of hacky text editor for nostalgic old-fashioned Unix users who like to use terminals so that they can call themselves hackers. If you think my friends are horrible you’re probably right and I should keep my dev questions for Stackoverflow or Reddit from now on.

Anyway…amused and a little concerned, I kept on reading articles and watching videos on Vim regardless.

Without some background, it can be very daunting to navigate around Vim. Luckily there are a plethora of articles, videos and books on the topic. Practical Vim is a very good book, I used it (and still reading it) to learn about Vim and I recommend it as it contains a lot of examples and it’s easy enough to read. A fun way to learn Vim if you are into action-adventure type of games is to play an online game based on Vim’s keyboard shortcuts called Vim Adventures. It’s the “Zelda meets text editing” game, I’ve been playing it, it’s fun and polished (but it’s not free).

At first I was actually very slow at doing anything but got better after a couple of weeks. Editing and navigating code was a lot quicker than I imagined. Any change I needed to make had become much simpler. The more I practiced and learned about Vim the faster I become at getting my way around. Vim’s ability to navigate and modify text is unrivalled.

I realised I needed to reach for the mouse less often and noticed to spend a lot more time with my hands on the keyboard. My wrist has been thanking me ever since.

Mistake #2 – Vim doesn’t let you code at the speed of thought

To my regret, after two months of using Vim, I realised I wasn’t any faster at actually writing code. I was definitely faster at editing, refactoring but in the end it was actually very dumb of me thinking I could improve as a coder just by learning Vim commands.

I’ve actually come to the conclusion that if one is able to code at the speed of thought with Vim it probably can do so without it. However if you’re that kind of dev you‘re probably a dev unicorn, please do get in touch I want to capture and study you.

My initial motivations were wrong but I’ve learned something new and I don’t regret it 🙂 Learning Vim is like learning a programming language in itself and it’s extremely rewarding.

It was incredible to acknowledge that very little I remembered about the position of the keys on the keyboard. Despite being able to type without looking I was still not able to reach for a single key directly. For example, using simple Vim commands like h j k l (left, down, up and right) to move around in normal mode forced me to look at the keyboard at least once to position my fingers.

Mistake #3 – I thought I was a touch typist but I clearly wasn’t

Even if it sounds dumb, I always ignored why the letter f and j had small bumps. If you, like me, don’t know why, their purpose is to help you feel them with your index fingers so that you can position your other three fingers on the so called “Home Row” without looking. From there you can then reach for the other keys.

Home Row in a Qwerty layout

Using Vim made myself a better typist (not necessarily a faster one) and has brought to the surface my flaws with the keyboard. I’ve developed a better relationship with it, and I now believe a keyboard is for a developer what a lightsaber is for a Jedi.

Finally, I’ve been able to answer the question: ”Is Vim still a relevant tool to learn in 2020?” The answer is: unless you’re a dev unicorn, a fast touch typist, someone who can edit, write and code at the speed of thought already then yeah learning Vim is valuable and something to consider.

Vim is a time sink though. You’ll spend countless hours. Vim is very much like the English language: “easy” to learn but hard to master. I would recommend to use a plugin inside of your preferred IDE rather than using the original text editor. Don’t get me wrong, Vim has thousands plugins that can make it up to an equivalent modern IDE. However I find it’s better to use an IDE with Vim extensions but I guess it’s very much a matter of personal preference.

Mistake #4 – Why didn’t I learn Vim earlier?

I hope you enjoyed the article and let me know what you think in the comments!