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!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.