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 の比率は です。
sqrt が実行時に計算されるのを防ぐために、別解のように数値リテラルを埋め込むと効率的です。もちろんコメントで式を示すのを忘れずに。
CreateNStar
CreateNgon と同様、必要なサイズのメモリをアロケーションしてから各要素を追加します。ループは展開して N 回にもできますが、ループごとの命令が大きくなるためか性能が低下しました。手元の環境で計測して選択しましょう。
CodeIQ では 1 週間ほどの募集でしたが、アクセルさん、rumiaqua さん、冬椿さん、ケアルガさん、ciel さん、hisoji_ さんが解答を投稿してくれました。以上の方にはフィードバックコメントをお送りします。
また春か夏ごろに新しい問題を出題予定です。ぜひ挑戦してみてください!