Siv3D Winter of Code 2013 の解答

昨年末に出題した Siv3D Winter of Code 2013 の解答です。

解答例

# include "Shapes.hpp"

namespace codeIQ
{
	std::vector<Vec2> CreateRect(double x, double y, double w, double h)
	{
		return{ { x, y }, { x + w, y }, { x + w, y + h }, { x, y + h } };
	}

	std::vector<Vec2> CreatePlus(double r, double width, const Vec2& center)
	{
		const double halfWidth = width / 2.0;
		const double x0 = center.x - r;
		const double x1 = center.x - halfWidth;
		const double x2 = center.x + halfWidth;
		const double x3 = center.x + r;
		const double y0 = center.y - r;
		const double y1 = center.y - halfWidth;
		const double y2 = center.y + halfWidth;
		const double y3 = center.y + r;

		return{
			{ x1, y0 }, { x2, y0 }, { x2, y1 },
			{ x3, y1 }, { x3, y2 },	{ x2, y2 },
			{ x2, y3 }, { x1, y3 },	{ x1, y2 },
			{ x0, y2 }, { x0, y1 },	{ x1, y1 }
		};
	}

	std::vector<Vec2> CreatePentagon(double r, double angle, const Vec2& center)
	{
		return CreateNgon(5, r, angle, center);
	}

	std::vector<Vec2> CreateHexagon(double r, double angle, const Vec2& center)
	{
		return CreateNgon(6, r, angle, center);
	}

	std::vector<Vec2> CreateNgon(int n, double r, double angle, const Vec2& center)
	{
		if (n < 3)
		{
			return{};
		}

		std::vector<Vec2> vertices;

		vertices.reserve(n);

		for (int i = 0; i < n; ++i)
		{
			vertices.push_back(center + Circular(r, angle + i*(TwoPi / n)));
		}

		return vertices;
	}

	std::vector<Vec2> CreateStar(double r, double angle, const Vec2& center)
	{
		return CreateNStar(5, r, r / ((3 + ::sqrt(5.0)) / 2), angle, center);
	}

	std::vector<Vec2> CreateNStar(int n, double rOuter, double rInner, double angle, const Vec2& center)
	{
		if (n < 2)
		{
			return{};
		}

		std::vector<Vec2> vertices;

		vertices.reserve(2 * n);

		for (int i = 0; i < n * 2; ++i)
		{
			vertices.push_back(center + Circular(i % 2 ? rInner : rOuter, angle + i*(Pi / n)));
		}

		return vertices;
	}
}

別解(より高速)

std::vector<Vec2> CreateNgon(int n, double r, double angle, const Vec2& center)
{
	if (n < 3)
	{
		return{};
	}

	std::vector<Vec2> vertices(n, center);

	for (int i = 0; i < n; ++i)
	{
		vertices[i] += Circular(r, angle + i*(TwoPi / n));
	}

	return vertices;
}

std::vector<Vec2> CreateStar(double r, double angle, const Vec2& center)
{
	const double innerScale = 0.38196601125010515; // 2/(3 + sqrt(5)) 

	return CreateNStar(5, r, r * innerScale, angle, center);
}

std::vector<Vec2> CreateNStar(int n, double rOuter, double rInner, double angle, const Vec2& center)
{
	if (n < 2)
	{
		return{};
	}

	std::vector<Vec2> vertices(n * 2, center);

	for (int i = 0; i < n * 2; ++i)
	{
		vertices[i] += Circular(i % 2 ? rInner : rOuter, angle + i*(Pi / n));
	}

	return vertices;
}

解説

CreatePlus

単純に実装すると見通しが悪くなるので、登場する値を整理しました。

CreatePentagon / CreateHexagon

DRY 原則で CreateNgon の特殊ケースとします。ソースコードが短くなるだけでなく、命令に使われるメモリを削減し、キャッシュ効率を改善する効果があります。

CreateNgon

空の vector に頂点を push_back() / emplace_back() で追加すると、メモリの再アロケートが生じて性能が低下します。はじめからサイズが N 個と決まっているので、vector::reserve(N) で必要なサイズのメモリをアロケーションしておきましょう。
別解では、N 個の center で vector を初期化しています。これによって計算時の一時オブジェクトを削減するだけでなく、push_back() によるサイズチェックも省略できるので、さらに効率を改善できます。
Circular の使い方については Circular 型 を参照してください。

CreateStar

CreateNStar の特殊ケースです。
rOuter と rInner の比率は 1 : \frac{2}{3+\sqrt{5}} です。
sqrt が実行時に計算されるのを防ぐために、別解のように数値リテラルを埋め込むと効率的です。もちろんコメントで式を示すのを忘れずに。

CreateNStar

CreateNgon と同様、必要なサイズのメモリをアロケーションしてから各要素を追加します。ループは展開して N 回にもできますが、ループごとの命令が大きくなるためか性能が低下しました。手元の環境で計測して選択しましょう。

CodeIQ では 1 週間ほどの募集でしたが、アクセルさん、rumiaqua さん、冬椿さん、ケアルガさん、ciel さん、hisoji_ さんが解答を投稿してくれました。以上の方にはフィードバックコメントをお送りします。
また春か夏ごろに新しい問題を出題予定です。ぜひ挑戦してみてください!