mindisc_tester.cpp

# include <Siv3D.hpp> // Siv3D v0.6.15


// Circle{ p0, p1 } で、p0 と p1 を結ぶ線分を直径とする円を作成できます。
// triangle.getCircumscribedCircle() で三角形の外接円を作成できます。




struct DrawPoint {
	Vec2 p;
	Color c;
	double sz;
};
struct DrawCircle {
	Circle p;
	Color c;
};

struct DrawList {
	Array<DrawPoint> points;
	Array<DrawCircle> circles;
};

// 途中経過を記録しておくと、後で描画できる
// 複数入れたら、左右矢印キーで切り替え
Array<DrawList> drawState;

int64 CALC_COST = 0;




// 3 点を含む最小の円を返す
Circle SmallestEnclosingCircle(const Vec2& p0, const Vec2& p1, const Vec2& p2)
{
	// TODO
}

// 与えらえた点をすべて含む最小の円を返す
Circle SmallestEnclosingCircle(const Array<Vec2>& points)
{
	// TODO
}




// 円が点をすべて包含していることを確認する。
bool VerifyEnclosingCircle(const Array<Vec2>& points, Circle c)
{
	Circle c_enlarge = c;

	// わずかに円を拡大
	c_enlarge.r *= (1.0 + 1.0e-14);

	bool ok = true;

	for (size_t i : step(points.size())) {
		if (!c_enlarge.contains(points[i])) {
			Console << U"points[" << i << U"] not included!";
			ok = false;
		}
	}

	Console << (ok ? U"[ OK ]" : U"[ NG ]");
	return ok;
}



Array<Vec2> GenerateCase(int64 id) {
	Array<Vec2> inputPoints;

	for (size_t i = 0; i < 20; i++) {
		//double x = Random(-10.0, 10.0);
		//double y = Random(-10.0, 10.0);
		//inputPoints.push_back(Vec2(x, y));

		double th = Random(0.0, Math::Pi * 2.0);
		auto p = Vec2(Cos(th), Sin(th)) * Random(0.0, Math::Pi * 20.0);

		// p.moveBy(Vec2(Random() * 0.001, Random() * 0.001));

		inputPoints.push_back(p);
	}

	return inputPoints;

}


void Main()
{
	// 背景の色を設定する | Set the background color
	Scene::SetBackground(ColorF{ 0.0, 0.0, 0.0 });

	Array<Vec2> inputPoints;

	Circle minidisc;

	for (int64 i = 0; i < 100; i++) {

		CALC_COST = 0;

		inputPoints = GenerateCase(i);

		minidisc = SmallestEnclosingCircle(inputPoints);
		bool ok = VerifyEnclosingCircle(inputPoints, minidisc);

		Console << U"CALC_COST = " << CALC_COST;
		if (!ok || CALC_COST >= 1000000000) break;
	}


	Vec2 sceneCenter = Scene::CenterF();
	Vec2 sceneSize = Scene::Size();

	RectF boundingRect;
	double scale = 1.0;
	Vec2 cent;
	{
		Vec2 mn = inputPoints[0];
		Vec2 mx = inputPoints[0];
		for (auto p : inputPoints) {
			if (mn.x > p.x) mn.x = p.x;
			if (mn.y > p.y) mn.y = p.y;
			if (mx.x < p.x) mx.x = p.x;
			if (mx.y < p.y) mx.y = p.y;
		}
		cent = (mn + mx) / 2.0;
		Vec2 sz = mx - mn;
		if (sz.x <= 1.0e-50) sz.x = 1.0;
		if (sz.y <= 1.0e-50) sz.y = 1.0;
		scale = Min(sceneSize.x / sz.x, sceneSize.y / sz.y) * 0.8;
		boundingRect = RectF(cent - sceneSize * scale / 2.0, sceneSize * scale);
	}

	{
		DrawList d;
		for (auto p : inputPoints) {
			d.points.push_back(DrawPoint{ p, Palette::White, 5.0 });
		}
		d.circles.push_back(DrawCircle{ minidisc, Palette::Orange });
		drawState.push_back(d);
	}

	size_t drawPtr = 0;

	while (System::Update())
	{
		if (!drawState.empty()) {
			if (KeyLeft.down() && drawPtr != 0) drawPtr--;
			if (KeyRight.down() && drawPtr + 1 < drawState.size()) drawPtr++;
		}

		for (auto& c : drawState[drawPtr].circles) {
			Circle circle_to_draw = c.p;
			circle_to_draw.center.moveBy(-cent);
			circle_to_draw.center *= scale;
			circle_to_draw.r *= scale;
			circle_to_draw.center.moveBy(sceneCenter);
			circle_to_draw.drawFrame(1.0, c.c);
		}

		for (auto& c : drawState[drawPtr].points) {
			Vec2 point_to_draw = c.p;
			point_to_draw.moveBy(-cent);
			point_to_draw *= scale;
			point_to_draw.moveBy(sceneCenter);
			point_to_draw.asCircle(c.sz).draw(c.c);
		}
	}
}