ボロノイ図

#概要

こちらはC++ ([DXライブラリ](http://dxlib.o.oo7.jp/))を使って、ボロノイ図を作成する記事です。
以前、記事を書いた["～水彩ボロノイ図を線画～"](https://qiita.com/Gaccho/items/8083c18f38f36c9af7f1)とは違うアルゴリズムを使用しています。

DXライブラリは[こちら](http://dxlib.o.oo7.jp/dxdload.html)からダウンロードできます。
何か不備がありましたら指摘していただければ幸いです。

#コード
1/12秒おきにボロノイ図が自動分割生成されるプログラムです。
このコードでは、最大で100個まで分割します。

```cpp:Main.cpp
#define NOMINMAX
#include "DxLib.h"
#include <vector>
#include <chrono>

//横画面サイズ
#define MAP_X 512

//縦画面サイズ
#define MAP_Y 512

//原点の最大個数
#define VORONOI_COUNT_MAX 1

struct Point {
	int x, y;
};

static int DistanceSqrd(const Point& point, int x, int y) {
	int xd = x - point.x;
	int yd = y - point.y;
	return (xd * xd) + (yd * yd);
}

class Voronoi {
public:
	//ボロノイ図を作る
	void Make(int count) {
		CreatePointColor(count);
		CreateSites();
		SetSitesPoints();
	}

private:
	std::vector<Point> points_;
	std::vector<unsigned int> colors_;

	//原点の場所と色を決定する
	void CreatePointColor(int count) {
		const int w = MAP_X - 20, h = MAP_Y - 20;
		unsigned int c;
		for (int i = 0; i < count; i++) {
			points_.push_back({ GetRand(w) + 10, GetRand(h) + 10 });
			c = GetColor(GetRand(100) + 150, GetRand(100) + 150, GetRand(100) + 150);
			colors_.push_back(c);
		}
	}

	//図形を線画
	void CreateSites() {
		int w = MAP_X, h = MAP_Y, d, ind, dist;
		for (int hh = 0; hh < h; hh++) {
			for (int ww = 0; ww < w; ww++) {
				ind = -1;
				dist = std::numeric_limits<int>::max();
				for (int it = 0; it < points_.size(); it++) {
					const Point& p = points_[it];
					d = DistanceSqrd(p, ww, hh);
					if (d < dist) {
						dist = d;
						ind = it;
					}
				}
				if (ind > -1) DrawPixel(ww, hh, colors_[ind]);
			}
		}
	}

	//原点を線画
	void SetSitesPoints() {
		for (const auto& point : points_) {
			int x = point.x, y = point.y;
			for (int i = -1; i < 2; i++)
				for (int j = -1; j < 2; j++)
					DrawPixel(x + i, y + j, GetColor(0, 0, 0));
		}
	}
};

int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int) {

	//log出力停止・ウィンドウモード変更・初期化・裏画面設定
	SetOutApplicationLogValidFlag(FALSE), ChangeWindowMode(TRUE), DxLib_Init(), SetDrawScreen(DX_SCREEN_BACK);

	//画面サイズの決定
	SetGraphMode(MAP_X, MAP_Y, 32);

	//タイトル文字
	SetMainWindowText("Voronoi");

	//ボロノイ図を線画
	Voronoi diagram;
	
	//時間
	int time = 0;

	int voronoiCount = 0;

	//ボロノイ図を生成
	diagram.Make(1 + GetRand(VORONOI_COUNT_MAX - 1));

	while (ScreenFlip() == 0 && ProcessMessage() == 0) {
		//1/12秒おきにボロノイ図を生成
		if (time == 5 && voronoiCount < 100) {
			diagram.Make(1 + GetRand(VORONOI_COUNT_MAX - 1));
			time = 0;
			voronoiCount++;
		}

		//ESCキーで終了
		if (CheckHitKey(KEY_INPUT_ESCAPE)) break;

		//時間を増やす
		time++;
	}

	//DXライブラリの終了処理
	DxLib_End();
	return 0;
}
```

#結果
###実行してみたらこんな感じ
![1513276802515.jpg](https://qiita-image-store.s3.amazonaws.com/0/213065/dd6282fa-7d83-d69e-07f4-51a994bbb5e3.jpeg)

アニメーションしてみたらこんな感じ

![circleanimationmuvie](https://i.imgur.com/RapqAw9.gif)

##ソースコードのライセンス

These codes are licensed under CC0.
[![CC0](https://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg "CC0")](http://creativecommons.org/publicdomain/zero/1.0/deed.ja)

ソースコードは自由に使用してください。

#参考
[ＤＸライブラリ　関数リファレンスページ](http://dxlib.o.oo7.jp/dxfunc.html)
[新・C言語 ～ゲームプログラミングの館](http://dixq.net/g/)
[ボロノイ図](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3)
[ボロノイ図を作る](https://qiita.com/yellow_73/items/abfca17297124785fe28)
[ボロノイ図とその３つの性質](https://mathtrain.jp/voronoi)
[ボロノイ分割とは？](http://www.pasco.co.jp/recommend/word/word048/)
[GPUでボロノイ図を描画する](http://postd.cc/voronoi-diagrams/)
[ボロノイ図の描画アルゴリズムについて](http://p-mathedu.org/docs/15th/15-01-maegawa.pdf)
[Voronoi diagram](https://rosettacode.org/wiki/Voronoi_diagram)
[vector](https://cpprefjp.github.io/reference/vector.html)