partial update area merger

update.cc

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
using std::cout;
using std::endl;

// make sure a <= b, or swap a and b to make it sure.
template <class T>
void reorder(T& a, T& b)
{
	if (b < a) std::swap(a, b);
}

template <class T>
T floor_shr(T src, T by)
{
	return src >> by;
}

template <class T>
T ceil_shr(T src, T by)
{
	T mask = (1 << by) - 1;
	return floor_shr(src, by) + !!(src & mask);
}

template <class T, class Resolution>
T floor_downsample(T x, Resolution reso)
{
	return floor_shr(x, reso) << reso;
}

template <class T, class Resolution>
T ceil_downsample(T x, Resolution reso)
{
	return ceil_shr(x, reso) << reso;
}

namespace region
{
	using coordinate = int;
	struct xyxy
	{
		coordinate x1;
		coordinate y1;
		coordinate x2;
		coordinate y2;
		xyxy() = default;
		xyxy(coordinate x1, coordinate y1, coordinate x2, coordinate y2)
			: x1{x1}, y1{y1}, x2{x2}, y2{y2}
		{
			reorder();
		}

		void reorder()
		{
			::reorder(x1, x2);
			::reorder(y1, y2);
		}

		void clip_by(xyxy clipper)
		{
			::reorder(clipper.x1, x1);
			::reorder(clipper.y1, y1);
			::reorder(x2, clipper.x2);
			::reorder(y2, clipper.y2);
		}

		xyxy clip(xyxy clippee)
		{
			clippee.clip_by(*this);
			return clippee;
		}

		bool intersect(xyxy other)
		{
			bool x_intersected = !(other.x2 < x1 || other.x1 > x2);
			bool y_intersected = !(other.y2 < y1 || other.y1 > y2);
			return (x_intersected && y_intersected);
		}
	};

	template <class Resolution>
	xyxy downsample(xyxy r, Resolution reso)
	{
		return {
			floor_downsample(r.x1, reso),
			floor_downsample(r.y1, reso),
			 ceil_downsample(r.x2, reso),
			 ceil_downsample(r.y2, reso),
		};
	}

	struct dimension
	{
		coordinate w;
		coordinate h;
		dimension() = default;
		dimension(coordinate w, coordinate h) : w{w}, h{h} {}
	};

	struct position
	{
		coordinate x;
		coordinate y;
		position() = default;
		position(coordinate x, coordinate y) : x{x}, y{y} {}
	};


	struct merger
	{
		using resolution_type = int;
		using coordinate = region::coordinate;
		using region_list = std::list<region::xyxy>;
		using iterator = region_list::iterator;


		merger(resolution_type r=5) : reso{r} {}

		void resolution(resolution_type r) { reso = r; }
		void dimension(coordinate w, coordinate h) { this->w = w; this->h = h; }

		void clear() { regions.clear(); }
		void add(region::xyxy r) { regions.push_back(r); }
		iterator begin() { return regions.begin(); }
		iterator   end() { return regions.  end(); }

		void merge()
		{
			downsample();
			clip();
			while (merge_intersected()) {}
		}

	private:
		region_list regions;
		resolution_type reso;
		coordinate w;
		coordinate h;

		void clip()
		{
			region::xyxy clipper{ 0, 0, w-1, h-1 };
			for (auto& r: regions)
				r.clip_by(clipper);
		}

		void downsample()
		{
			for (auto& r: regions)
				r = region::downsample(r, reso);
		}

		bool merge_intersected()
		{
			bool merged = false;

			auto end = regions.end();
			for (auto i=regions.begin(); i!=end; ++i) {
				auto j = std::next(i);
				while (j != end) {
					if (i->intersect(*j)) {
						reorder(i->x1, j->x1);
						reorder(i->y1, j->y1);
						reorder(j->x2, i->x2);
						reorder(j->y2, i->y2);
						auto nj = std::next(j);
						regions.erase(j);
						j = nj;
						merged = true;
					}
					else ++j;
				}
			}

			return merged;
		}
	};
};


int main()
{
	region::merger m;
	m.dimension(640, 480);
	m.add({-1, -10, 50, 60});
	m.add({1, 10, 62, 90});
	m.add({400, 400, 500, 600});
	m.add({100, 200, 399, 370});
	m.merge();
	for (auto& r: m)
		cout << r.x1 << ", " << r.y1 << " -> "
			 << r.x2 << ", " << r.y2 << endl;
}