OutlineDetector

OutlineDetector.h

#pragma once

Array<Array<Vec2>> GetOutlines(const Image& image, function<bool(Color)> judge)
{
	const Point directions[8] = { { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } };
	const Rect rect(image.size());
	const int width = image.width();
	const int height = image.height();
	Grid<bool> map(width, height, false);
	Array<Point> startPositions;

	// mapに転写
	{
		Point p = Point::Zero();
		for (;;)
		{
			if (!map[p] && judge(image[p]))
			{
				Array<Point> points;

				// 始点
				startPositions.emplace_back(p);
				map[p] = true;
				points.emplace_back(p);

				for (int i = 0; i < points.size(); ++i)
				{
					for (int dir = 0; dir < 8; ++dir)
					{
						const Point point = points[i].movedBy(directions[dir]);

						if (rect.contains(point) && !map[point] && judge(image[point])) { map[point] = true; points.emplace_back(point); }
					}
				}
			}

			// 読み取り位置変更
			if (++p.x == width)
			{
				p.x = 0;

				if (++p.y == height) break;
			}
		}
	}

	// 結果を格納
	Array<Array<Vec2>> outlines;
	if (startPositions.empty()) return outlines;

	int		botDirection = 0;
	Point	botPosition = startPositions.back();
	startPositions.pop_back();

	Array<Point> outline;
	outline.emplace_back(botPosition);

	for (;;)
	{
		for (int i = -2; i <= 4; ++i)
		{
			// 始点に戻った場合
			if (outline.size() >= 2 && (botDirection + i) % 8 == 0 && botPosition == outline.front())
			{
				// 最初と最後を被らせないために末尾を削除する
				outline.pop_back();

				// 転写
				auto& result = outlines.emplace_back();
				for (const auto& o : outline)
					result.emplace_back(o.x, o.y);

				if (startPositions.empty()) return outlines;

				botPosition = startPositions.back();
				startPositions.pop_back();

				outline.clear();
				outline.emplace_back(botPosition);

				break;
			}

			// 移動
			const Point forwardPosition = botPosition + directions[(botDirection + i + 8) % 8];
			if (rect.contains(forwardPosition) && map[forwardPosition.y][forwardPosition.x])
			{
				botPosition = forwardPosition;
				botDirection = ((botDirection + i) % 8 + 8) % 8;
				outline.emplace_back(botPosition);

				break;
			}

			// 一ブロックの場合は無視する
			if (i == 4)
			{
				if (startPositions.empty()) return outlines;

				botPosition = startPositions.back();
				startPositions.pop_back();

				outline.clear();
				outline.emplace_back(botPosition);
			}
		}
	}
}