RamerDouglasPeuker not great for closed paths

[brianwinterpixel]

I'm trying out the function RamerDouglasPeuker, but it seems to not work well with closed paths.

When the points that need to be removed lie at the beginning or end of the path, the algorithm fails to identify them.

Example:

I attempted to resolve this by explicitly looping the path, like so:

template<typename T>
inline Paths<T> closedRamerDouglasPeucker(const Paths<T> &paths, double epsilon) {
	Paths<T> result;
	result.reserve(paths.size());
	for (const Path<T>& path : paths) {
		Path<T> looped_path = path; // copy
		looped_path.push_back(path.front()); // make the path loop back
		result.push_back(RamerDouglasPeucker<T>(looped_path, epsilon));
	}
	return result;
}

Unfortunately, while this appears to successfully clean up some polygons, it destroys important vertices in others.

It looks like RDP is intended for open paths, but the documentation recommends running this after offset operations.

[brianwinterpixel]

I've found a solution that works for me, but it's certainly not ideal in terms of memory allocation.

template<typename T>
inline Paths<T> closedRamerDouglasPeucker(const Paths<T> &paths, double epsilon) {
	Paths<T> result;
	result.reserve(paths.size());
	for (const Path<T>& path : paths) {
		if (path.size() <= 4) {
			result.push_back(path);
			continue;
		}
		// Perform the algorithm on the path twice, once rotated by half
		Path<T> new_path = RamerDouglasPeucker<T>(path, epsilon);
		if (new_path.size() <= 4) {
			result.push_back(new_path);
			continue;
		}
		Path<T> rotated;
		rotated.reserve(new_path.size());
		auto middle = new_path.begin() + new_path.size() / 2;
		std::copy(middle, new_path.end(), std::back_inserter(rotated));
		std::copy(new_path.begin(), middle, std::back_inserter(rotated));
		new_path = RamerDouglasPeucker<T>(rotated, epsilon);
		
		result.push_back(new_path);
	}
	return result;
}

[brianwinterpixel]

Resolved by 1aae9b4