複数の円が重ならずに入った正方形の中に、とある円が重ならずに入る場所があるかどうかの判定

Question

前提・実現したいこと

タイトル通り、「複数の円が重ならずに入った正方形の中に、とある円が重ならずに入る場所があるかどうか」を、高速に判定するためのアルゴリズムを考えています。問題を図にすると下のような感じですかね。。（雑ですが）

（各円の中心座標と半径は既知とします。円の個数は任意です。）

もちろん、全ての点を探索すればいいのですが、非常に時間がかかると思います。そこで、比較的早そうな（証明できていなくてもいいので）アルゴリズムを探しています。

願わくばUnity2DでC#を使って実装できるものがいいです。（別にほかの言語でもOKです。なんとかします。）

###求める回答
解決策がなくても、ヒントになりそうな考え方やアルゴリズム、似た問題などがあれば、ぜひ教えていただきたいです。また、早くなりそうな方法であれば、全探索の改良などでも構いません（この問題における探索する順番の優先度など）。どうかよろしくお願いします。

###追記（2020/04/07）
返信遅れていますが、非常に興味深い回答が多数寄せられています。
誠にありがとうございます。
先日、Bongoさんが実験してくださったように、2次元の探索はさほど負荷がかからないことが分かりました。
そのため、悩んでいた事自体は解決したのですが、まだ展開がありそうなのでもう少し回答を募りたいと思います。
回答してくださった方には再度お礼申し上げます。

Comments

[Zuishin]

入る場所があるかどうかを求めればいいんですね？
入る場所を求めるのではなく。

[ochinhuni]

はい！そうです。

Answer 1

面白そうな問題に取り組んでいますね。すみませんが私も力技案しか思いつかなかったんですけれども、二次元空間ならば総当たりでも何とかなるんじゃないかと思います（立方体の空間に球体を詰めていくような3D版となると、このやり方ではきつそうですが...）。

話を単純化するために正方形のサイズは1.0×1.0とし、適当な大きさのテクスチャ（さしあたり2048×2048としました）の各ピクセルについてその位置に円を置けるかを判定することにしました。
各地点に円を置けるかどうかの判定は並列に行っても問題ないでしょうから、グラフィックス機能を使えば十分高速に処理できるだろうと見込んでのことです。

ロジックの中核となるスクリプトは下記のようにし...

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using Random = UnityEngine.Random;

public class BoxAndBalls
{
	private const int Level = 12;
	private readonly List<Vector3> balls = new List<Vector3>();
	private readonly RenderTexture[] availabilityMaps;
	private readonly Texture2D availabilityMapReader;
	private readonly Texture2D ballTexture;
	private Color[] ballTexturePixels;
	private int ballTextureWidth = 1;
	private int ballTextureHeight = 1;

	private Material availablePositionFinder;
	private readonly int RadiusProperty = Shader.PropertyToID("_Radius");
	private readonly int BallCountProperty = Shader.PropertyToID("_BallCount");

	public BoxAndBalls()
	{
		this.availabilityMaps = Enumerable.Range(0, Level).Select(
			l =>
			{
				var resolution = 1 << l;
				return new RenderTexture(resolution, resolution, 0, RenderTextureFormat.R8);
			}).ToArray();
		this.availabilityMapReader = new Texture2D(2, 2, TextureFormat.R8, false);
		this.ballTexture = new Texture2D(
			this.ballTextureWidth,
			this.ballTextureHeight,
			TextureFormat.RGBAFloat,
			false) {filterMode = FilterMode.Point};
		this.ballTexturePixels = new Color[this.ballTextureWidth * this.ballTextureHeight];
	}

	public Texture AvailabilityMap => this.availabilityMaps[Level - 1];
	public Texture BallTexture => this.ballTexture;
	public int BallCount => this.balls.Count;

	public bool TryAddBall(float x, float y, float radius)
	{
		if (!this.VerifyNextPosition(x, y, radius))
		{
			Debug.Log($"({x}, {y})に半径{radius}のボールを置くことはできませんでした。");
			return false;
		}

		this.balls.Add(new Vector3(x, y, radius));
		this.UpdateBallTexture();
		Debug.Log($"({x}, {y})に半径{radius}のボールを置きました。");
		return true;
	}

	public bool TryGetRandomAvailablePosition(float radius, out float x, out float y)
	{
		if (this.availablePositionFinder == null)
		{
			this.availablePositionFinder = new Material(Shader.Find("Hidden/AvailablePositionFinder"));
		}

		// Levelに応じた解像度（12なら2048×2048）のテクスチャ上の全ピクセルについて
		// 半径がradiusのボールを置けるかチェックし、結果を描画する
		this.availablePositionFinder.SetFloat(this.RadiusProperty, radius);
		this.availablePositionFinder.SetInt(this.BallCountProperty, this.balls.Count);
		Graphics.Blit(this.ballTexture, this.availabilityMaps[Level - 1], this.availablePositionFinder, 0);

		// 解像度を1/2、1/4、1/8...と半々に小さくしたテクスチャを用意しておき、
		// 描画された結果を縦横1/2サイズのテクスチャに順次転写していく
		// 2×2ピクセルずつ見ていき、4ピクセルのうちボールを置ける場所が1箇所以上あれば
		// 次のテクスチャレベルの当該ピクセルは1となる
		// 最終的に1×1ピクセルまで転写されたとき、そのテクスチャの色が1ならば
		// どこかにまだボールを置ける場所が残っていることを意味する
		for (var i = Level - 2; i >= 0; i--)
		{
			Graphics.Blit(this.availabilityMaps[i + 1], this.availabilityMaps[i], this.availablePositionFinder, 1);
		}

		// 結果を確認する
		var currentActive = RenderTexture.active;
		RenderTexture.active = this.availabilityMaps[0];
		this.availabilityMapReader.ReadPixels(new Rect(0, 0, 1, 1), 0, 0);
		RenderTexture.active = currentActive;
		if (this.availabilityMapReader.GetPixel(0, 0).r <= 0.0f)
		{
			Debug.Log($"もう半径{radius}のボールを置ける場所はなさそうです。");
			x = 0.0f;
			y = 0.0f;
			return false;
		}

		// もし置ける場所を取得したいのであれば、this.availabilityMaps[Level - 1]の全ピクセルを取得し
		// 色が1の座標を抜き出して配列にでもして返せばいいだろうが、頻繁にやるには高コストと思われる
		// どこかランダムに1箇所選ぶだけでいいなら、結果テクスチャを先ほどの転写順とは逆順に
		// 調べていくことで、必要なピクセルのチェック数を節約できそう
		// 今回は一人のプレイヤーがひたすらボールを詰めていくというデザインにしたが、たとえば
		// コンピュータを相手に交互にボールを置いていくようなゲームデザインなら、敵の手番で
		// ボールを置く場所を決定する際に、こういった機能が有用かもしれない
		var offset = new Vector2Int();
		var availablePixelPositions = new List<Vector2Int>();
		var flipY = SystemInfo.graphicsUVStartsAtTop;
		for (var i = 1; i < Level; i++)
		{
			RenderTexture.active = this.availabilityMaps[i];
			this.availabilityMapReader.ReadPixels(
				new Rect(offset.x, flipY ? (1 << i) - 2 - offset.y : offset.y, 2, 2),
				0,
				0);
			availablePixelPositions.Clear();
			for (var u = 0; u < 2; u++)
			{
				for (var v = 0; v < 2; v++)
				{
					var pixel = this.availabilityMapReader.GetPixel(u, v);
					if (pixel.r > 0.0f)
					{
						availablePixelPositions.Add(new Vector2Int(u, v));
					}
				}
			}

			offset = (offset + availablePixelPositions[Random.Range(0, availablePixelPositions.Count)]) * 2;
		}
		RenderTexture.active = currentActive;
		var map = this.availabilityMaps[Level - 1];
		x = ((offset.x * 0.5f) + 0.5f) / map.width;
		y = ((offset.y * 0.5f) + 0.5f) / map.height;
		Debug.Log($"まだ({x}, {y})に半径{radius}のボールを置けそうです。");
		return true;
	}

	private void UpdateBallTexture()
	{
		var ballCount = this.balls.Count;
		var capacity = this.ballTextureWidth * this.ballTextureHeight;
		if (capacity < ballCount)
		{
			while (capacity < ballCount)
			{
				if (this.ballTextureWidth > this.ballTextureHeight)
				{
					this.ballTextureHeight <<= 1;
				}
				else
				{
					this.ballTextureWidth <<= 1;
				}

				capacity <<= 1;
			}

			this.ballTexture.Resize(this.ballTextureWidth, this.ballTextureHeight);
			Array.Resize(ref this.ballTexturePixels, capacity);
		}

		for (var i = 0; i < ballCount; i++)
		{
			var ball = this.balls[i];
			this.ballTexturePixels[i] = new Color(ball.x, ball.y, ball.z);
		}

		this.ballTexture.SetPixels(this.ballTexturePixels);
		this.ballTexture.Apply(false);
	}

	private bool VerifyNextPosition(float x, float y, float radius)
	{
		if ((x < radius) || (x > (1.0f - radius)) || (y < radius) || (y > (1.0f - radius)))
		{
			Debug.Log("壁に近すぎます。");
			return false;
		}

		foreach (var ball in this.balls)
		{
			var relativeX = ball.x - x;
			var relativeY = ball.y - y;
			var distance = Mathf.Sqrt((relativeX * relativeX) + (relativeY * relativeY));
			if (distance < (radius + ball.z))
			{
				Debug.Log("他のボールに近すぎます。");
				return false;
			}
		}

		return true;
	}
}

判定部分は下記のようなシェーダーコードとしました。

Shader "Hidden/AvailablePositionFinder"
{
	Properties
	{
		_MainTex ("Texture", 2D) = "white" {}
		_Radius ("Radius", Float) = 0.0
		_BallCount ("Ball Count", Int) = 0
	}
	SubShader
	{
		CGINCLUDE
		#include "UnityCG.cginc"

		struct appdata
		{
			float4 vertex : POSITION;
			float2 uv : TEXCOORD0;
		};

		struct v2f
		{
			float2 uv : TEXCOORD0;
			float4 vertex : SV_POSITION;
		};

		v2f vert(appdata v)
		{
			v2f o;
			o.vertex = UnityObjectToClipPos(v.vertex);
			o.uv = v.uv;
			return o;
		}

		sampler2D _MainTex;
		ENDCG

		Pass
		{
			Cull Off
			ZWrite Off
			ZTest Always

			CGPROGRAM
			#pragma vertex vert
			#pragma fragment frag

			float4 _MainTex_TexelSize;
			float _Radius;
			uint _BallCount;

			fixed4 frag(v2f i) : SV_Target
			{
				if (any(max(max(_Radius - i.uv, i.uv - (1.0 - _Radius)), 0.0)))
				{
					// 壁に近すぎる
					return 0.0;
				}

				uint ballTexWidth = (uint)_MainTex_TexelSize.z;

				[loop]
				for (uint index = 0; index < _BallCount; index++)
				{
					float2 uv = (float2(index % ballTexWidth, index / ballTexWidth) + 0.5) * _MainTex_TexelSize.xy;
					float3 ball = tex2Dlod(_MainTex, float4(uv, 0.0, 0.0)).xyz;
					
					if (distance(i.uv, ball.xy) < _Radius + ball.z)
					{
						// 他のボールに近すぎる
						return 0.0;
					}
				}

				return 1.0;
			}
			ENDCG
		}

		Pass
		{
			Cull Off
			ZWrite Off
			ZTest Always
			
			CGPROGRAM
			#pragma vertex vert
			#pragma fragment frag

			fixed4 frag(v2f i) : SV_Target
			{
				return sign(tex2D(_MainTex, i.uv));
			}
			ENDCG
		}
	}
}

この他、ゲームっぽい体裁にするためのBoxAndBallsを使う側のスクリプトがあるのですが、本筋とは関係が薄いだろうということと字数節約のために省略しました。

動作させたところ、下図のような結果になりました。画面左上に表示されているのが次に置くべきボールのサイズ、箱の中に現れる青い×印はランダムに選択されたボールを置けるであろう場所です。
左下と右下のRawImageはデバッグ目的のもので、左下はボールを置けると判断された領域、右下はシェーダー側へ既存ボールの位置・サイズを送り込むためにデータをテクスチャの形にしたものです。

今回は正方形内の個々の点についてそれぞれ他の円や壁との距離を調べる方法にしましたが、majiponiさんのおっしゃるように、既存の円や壁が発生させる配置禁止領域を重ね描きしていって禁止領域マップを作るというのもよさそうですね。

Comments

[ochinhuni]

とてもとても丁寧な回答をありがとうございます。
実際に実装して試していただくなんて、何だか申し訳ないです。。
見たところサクサク動いていますね！仰られているように杞憂だったのかもしれません。
また、コードを共有していただきありがとうございます。細かなテクニックがたくさん詰まっていて、Unity初心者の私にとって、とても勉強になりました！

参考にさせていただきます！ありがとうございます。

Answer 2

すべての点に対する探索でなく求められそうな気はします。

最適なポジションに置いた、追加できる最大の大きさの円と、それらに接する3つの既存の円(正方形の辺も円と扱う)を考えます。
既存の円の中心のうち2点を考えます。
追加円中心とその2点との距離の差は、対応する円の半径の差です。
2点からの距離の差が等しい点の集合は、双曲線です。
別の組み合わせで考えれば、複数の双曲線ができ、その交点に求める点はあります。
双曲線の交点は、ググったところどうやら解析的に求められるようです。
参考: https://yo-kun.hatenadiary.org/entry/20081130/p1
場所がわかればあとは既存の円の中心との距離とその半径の差が求める円の最大の半径です。

3つの円の組の求め方ですが、たぶん「円間の距離の短い順に線で結び、できた3角形分割」でいけるのではないかなという気がします。

ただ、これで計算できたとして、円が多くなると高々画面解像度程度の全探索(既存円半径+追加円半径で全既存円を塗って塗り残しを見る)とどちらが速いかは微妙なところなようにも思います。

Comments

[ochinhuni]

回答ありがとうございます！
これは、私には到底思いつかない方法ですね。。
三角形分割をし、各三角形の頂点３つの内、任意の二点からできる各双曲線の交点で、外接する円の半径が分かるということですか。。
双曲線を作るために必要な二焦点からの距離の差は半径の差なので既知というのが面白いですね。

早いかどうかは別として、とても面白かったです！
参考にさせていただきたます！

Answer 3

各点で調べる、に近いですが…

入るか調べたい円の半径をR、各円の半径をr(n)、正方形の一辺をW、とします。まず、正方形内のすべての点に、0、とマークします。次に、各円に対し、中心からR+r(n)の半径の円を考え、その内部の点に、1、とマークします。最後に、座標が(R,R)-(W-R,W-R)の点の中に、0、とマークされている点がないか調べます。

Comments

[ochinhuni]

回答していただきありがとうございます！
置けない場所のマップを作るんですね！
思いつきそうで思いつかなかったです。。
非常に良い案だと思いました。

参考にさせていただきます！

Answer 4

既に存在する全ての図形に対して、正方形(円に外接、辺の長さ＝円の直径)があるとする。
既に存在する全ての図形に対して、正方形(円に内接、対角線＝円の直径)があるとする。

ここで想定する全ての正方形は、辺がx軸 or y軸に平行である。

---

1. 全ての円を、円に外接する正方形であるとして判定

→1に該当ない場合
2-1, 全ての円は円に内接する正方形であるとして、次ステップで計算を行う座標をスクリーニング

2-2, 追加する円が既存の円と重複せずに存在できるか判定
(円と円の中心間距離d > 円1の半径r1 + 円2の半径r2)

---

もうちょっとスマートな解法ありそうですが...
個人的にも気になるので、考えついた方ぜひ解答ください！

Comments

[ochinhuni]

素早い回答ありがとうございます！
なるほど！まずは、ざっくり判定するんですね。pygameの完全衝突判定(ピクセル単位の衝突判定)がまさに同じようなことをしていると聞いたことがあります。(Unityやその他もそうなのでしょうか？？)

回答していただきありがとうございます。参考にさせていただきます！！

Answer 5

新たに配置したい円の半径をrとするとき，
既存の全ての円の半径をrだけ広げた世界において…

for( 円１ in 既存の円群 )
{
  for( 円２ in 既存の円群，ただし円1ではない )
  {
    for( 交点 in 円1と円2の交点群 )
    {
      if( この交点を含む円が存在しない ){ return 設置できる }
    }
  }

  if( 円1が全ての円と交点をもたない ){ return 設置できる }
}
return 設置できない

（上記は話を簡単にするため「円」だけで書いたが，外周も既存の円と同様にrだけ内側に狭めて適切に扱えばいい）

…みたいな話にならないでしょうか．

---

↓
ダメだ．ならないな．

円の弧を２交点の範囲で切り取っていって残るか（円周全体が他の円群によって包括されるかどうか）という判定じゃないとダメだ．

すなわち，円弧上の位置を１次元の媒介変数t=0～1で表すとしたら，円弧上の位置t=0～1の範囲すべてが他者によって含まれるかどうかをチェックするという作業になる．
（交点計算によって，他者に含まれるtの範囲を集めていけばいいと思う．
計算時間については，データ規模次第では交点計算対象を何らかの枝狩りで減らす工夫が必要かもしれない．）

処理の意味合いを図形的な観点で言えば……　他で回答されているような「新しい円の中心を置けないエリア」のマスクを作ったとしたら，最終的にエリアの境界が１箇所でも残って見えていたら「置ける」という話．
（「置けない」場合には，空間の全域がマスクされるされるから境界が見えない）

Answer 6

[アナログな解]

入るかどうか調べる円（円X）の半径をRとします。

元々ある各円の中心から、その円の半径＋Rの円を書きます。（円Xの中心が、その円の中に在ると、その円と円ｘは重なります）
外枠の正方形に接する幅Rの枠を書きます。（円Xの中心が、その枠の中に在ると、正方形と円Xは重なります）

正方形の中に、上で説明した円にも四角い枠にも入っていない部分(円でも枠でも塗りつぶされていない部分）が存在すれば、その部分に中心をもつ円Xは重ならずに置くことができます。

Comments

[fana]

majiponi氏の回答と同内容に見えます．

Answer 7

• 正方形内の任意の二つの円の間の空隙の最小値は、それぞれの中心点を結ぶ線分の長さ－（それぞれの円の半径を足したもの）に等しい
• ある円が他の円に重ならないための条件は、上記を正方形内のすべての円に対して計算した結果、すべての空隙が 0 以上であることを満たしているかどうかで判定可能（接するのがありかなしかで変わります）
• ただし、ある円が正方形内に収まるかどうかの判定も必要（これは中心点の座標と半径から判定可能）

ではいけないかなあ……
※もう少し絞るなら、新しい円の周辺の円のみで判定することも可能なような気がしますが……

って、問題は「そのような点があるか？」か……しらみつぶしでやるにしても面倒ですね。

すべての円から、それぞれの円の中心を頂点とする三角形で領域を分割してやると、それぞれの領域で入る最大の空隙はとりあえず分かります。これで大まかに入りそうな場所と確実に入らない場所を振り分けて、入りそうな場所に対してしらみつぶし、ですかねえ？

Answer 8

既存円群の中心座標と外周矩形の４頂点でドロネー図を作り，
三角形毎に１点の探索開始点を（例えば適当に三角形の重心にでも）定め，
勾配法的に調べる：

ある位置(x,y)に関して，
距離を考えねばならないもの（既存円の中心，外周の４辺）のうち，(x,y)に最も距離が近いものと，(x,y)との間の距離をD(x,y)とし，D(x,y)が大きくなる方向に勾配を登っていけば良い．