三角形と円の判定処理を知りたいです

前提

三角形と円の判定
①三角形内に円が収まっているか
②三角形の辺と接しているか

実現したいこと

円と三角形が接しているor内にあるか判定をしたい

補足情報

C#またはPythonで再現をしたいです
参考となるサイト、できれば簡易で構いませんのでコード等お教えいただけると幸いです。

行動規範の内容に同意します

回答4件

http://marupeke296.com/COL_2D_No5_PolygonToCircle.html

投稿2022/10/28 12:23

KEMONO.PANTSU

総合スコア481

円と三角形が接しているor内にあるか判定をしたい

判定法やその実装に興味はなく成果物（ゲーム等）の完成を優先する

既存のライブラリを探してみましょう。
c# 2d collision detection library - Google 検索
 python 2d collision detection library - Google 検索

例えばBox2Dは各言語に移植されており、比較的情報も多いです（やりたいことに対してオーバースペックではあるが^^;
Box2D - Wikipedia

判定法やその実装に興味がある・ライブラリを使うほどでもなく簡易的なものでいい

C#またはPythonで再現をしたいです
参考となるサイト、できれば簡易で構いませんのでコード等お教えいただけると幸いです。

C#とPythonはだいぶ文法が違いますしGUIとなると例を出すのもなかなか難しいのですが、Processingでの例を紹介します。

ProcessingはほぼJava（C#とかなり似ている）なのですが、Pythonモードもあります。
Processing - Wikipedia
Welcome to Processing! / Processing.org

こちらはProcessing（Javaモード）での、多角形と円の当たり判定です。
POLYGON/CIRCLE | Collision Detection

上記をベースに質問画像に似せました。

Java
1final float r = 15;
2PVector[] vertices = {
3  new PVector(200, 100),
4  new PVector(360, 250),
5  new PVector(200, 250),
6};
7
8
9void setup() {
10  size(600, 400);
11  noFill();
12  strokeWeight(4);
13}
14
15void draw() {
16  background(255);
17
18  stroke(0);
19  beginShape();
20  for (PVector v : vertices) {
21    vertex(v.x, v.y);
22  }
23  endShape(CLOSE);
24
25  float cx = mouseX;
26  float cy = mouseY;
27  boolean hit = polyCircle(vertices, cx, cy, r);
28  if (hit) {
29    stroke(255, 0, 0);
30  } else {
31    float a = r * sin(QUARTER_PI);
32    line(cx - a, cy - a, cx + a, cy + a);
33    line(cx + a, cy - a, cx - a, cy + a);
34    stroke(255, 255, 0);
35  }
36  ellipse(cx, cy, r * 2, r * 2);
37}
38
39
40boolean polyCircle(PVector[] vertices, float cx, float cy, float r) {
41  int next = 0;
42  for (int current = 0; current < vertices.length; current++) {
43    next = current + 1;
44    if (next == vertices.length) next = 0;
45
46    PVector vc = vertices[current];
47    PVector vn = vertices[next];
48
49    boolean collision = lineCircle(vc.x, vc.y, vn.x, vn.y, cx, cy, r);
50    if (collision) return true;
51  }
52
53  boolean centerInside = polygonPoint(vertices, cx, cy);
54  if (centerInside) return true;
55
56  return false;
57}
58
59boolean lineCircle(float x1, float y1, float x2, float y2, float cx, float cy, float r) {
60  boolean inside1 = pointCircle(x1, y1, cx, cy, r);
61  boolean inside2 = pointCircle(x2, y2, cx, cy, r);
62  if (inside1 || inside2) return true;
63
64  float distX = x1 - x2;
65  float distY = y1 - y2;
66  float len = sqrt((distX * distX) + (distY * distY));
67
68  float dot = (((cx - x1) * (x2 - x1)) + ((cy - y1) * (y2 - y1))) / pow(len, 2);
69
70  float closestX = x1 + (dot * (x2 - x1));
71  float closestY = y1 + (dot * (y2 - y1));
72
73  boolean onSegment = linePoint(x1, y1, x2, y2, closestX, closestY);
74  if (!onSegment) return false;
75
76  distX = closestX - cx;
77  distY = closestY - cy;
78  float distance = sqrt((distX * distX) + (distY * distY));
79
80  return distance <= r;
81}
82
83boolean linePoint(float x1, float y1, float x2, float y2, float px, float py) {
84  float d1 = dist(px, py, x1, y1);
85  float d2 = dist(px, py, x2, y2);
86  float lineLen = dist(x1, y1, x2, y2);
87  float buffer = 0.1;
88
89  return d1 + d2 >= lineLen - buffer && d1 + d2 <= lineLen + buffer;
90}
91
92boolean pointCircle(float px, float py, float cx, float cy, float r) {
93  float distX = px - cx;
94  float distY = py - cy;
95  float distance = sqrt((distX * distX) + (distY * distY));
96
97  return distance <= r;
98}
99
100boolean polygonPoint(PVector[] vertices, float px, float py) {
101  boolean collision = false;
102
103  int next = 0;
104  for (int current = 0; current < vertices.length; current++) {
105    next = current + 1;
106    if (next == vertices.length) next = 0;
107
108    PVector vc = vertices[current];
109    PVector vn = vertices[next];
110
111    if (((vc.y > py && vn.y < py) || (vc.y < py && vn.y > py))
112      && (px < (vn.x - vc.x) * (py - vc.y) / (vn.y - vc.y) + vc.x)) {
113      collision = !collision;
114    }
115  }
116
117  return collision;
118}

Pythonモードにベタ移植。

Python
1r = 15
2vertices = [
3  PVector(200, 100),
4  PVector(360, 250),
5  PVector(200, 250),
6]
7
8
9def setup():
10  size(600, 400)
11  noFill()
12  strokeWeight(4)
13
14def draw():
15  background(255)
16
17  stroke(0)
18  beginShape()
19  for v in vertices:
20    vertex(v.x, v.y)
21  endShape(CLOSE)
22
23  cx = mouseX
24  cy = mouseY
25  hit = polyCircle(vertices, cx, cy, r)
26  if hit:
27    stroke(255, 0, 0)
28  else:
29    a = r * sin(QUARTER_PI)
30    line(cx - a, cy - a, cx + a, cy + a)
31    line(cx + a, cy - a, cx - a, cy + a)
32    stroke(255, 255, 0)
33
34  ellipse(cx, cy, r * 2, r * 2)
35
36
37def polyCircle(vertices, cx, cy, r):
38  next = 0
39  for current, vc in enumerate(vertices):
40    next = current + 1
41    if next == len(vertices): next = 0
42
43    vn = vertices[next]
44
45    collision = lineCircle(vc.x, vc.y, vn.x, vn.y, cx, cy, r)
46    if collision: return True
47
48  centerInside = polygonPoint(vertices, cx, cy)
49  if centerInside: return True
50
51  return False
52
53def lineCircle(x1, y1, x2, y2, cx, cy, r):
54  inside1 = pointCircle(x1, y1, cx, cy, r)
55  inside2 = pointCircle(x2, y2, cx, cy, r)
56  if inside1 or inside2: return True
57
58  distX = x1 - x2
59  distY = y1 - y2
60  len = sqrt((distX * distX) + (distY * distY))
61
62  dot = (((cx - x1) * (x2 - x1)) + ((cy - y1) * (y2 - y1))) / pow(len, 2)
63
64  closestX = x1 + (dot * (x2 - x1))
65  closestY = y1 + (dot * (y2 - y1))
66
67  onSegment = linePoint(x1, y1, x2, y2, closestX, closestY)
68  if not onSegment: return False
69
70  distX = closestX - cx
71  distY = closestY - cy
72  distance = sqrt((distX * distX) + (distY * distY))
73
74  return distance <= r
75
76def linePoint(x1, y1, x2, y2, px, py):
77  d1 = dist(px, py, x1, y1)
78  d2 = dist(px, py, x2, y2)
79  lineLen = dist(x1, y1, x2, y2)
80  buffer = 0.1
81
82  return d1 + d2 >= lineLen - buffer and d1 + d2 <= lineLen + buffer
83
84def pointCircle(px, py, cx, cy, r):
85  distX = px - cx
86  distY = py - cy
87  distance = sqrt((distX * distX) + (distY * distY))
88
89  return distance <= r
90
91def polygonPoint(vertices, px, py):
92  collision = False
93
94  next = 0
95  for current, vc in enumerate(vertices):
96    next = current + 1
97    if next == len(vertices): next = 0
98
99    vn = vertices[next]
100
101    if ((vc.y > py and vn.y < py) or (vc.y < py and vn.y > py)) \
102      and (px < (vn.x - vc.x) * (py - vc.y) / (vn.y - vc.y) + vc.x):
103      collision = not collision
104
105  return collision

私は数学的なことは全く分かりません（ので、解説は最初から読んでみてください^^;
Collision Detection

投稿2022/10/29 22:21

TN8001

総合スコア9385

「三角形を全方向に円の半径分だけ膨らませた図形」に「円の中心座標」が含まれるか？
という判定を考えてください．
判定しやすいように前者の図形側を適当にいくつかの部分に切り分けて考えるなどすればよいでしょう．

投稿2022/10/29 01:22

fana

総合スコア11703

fana

2022/10/31 01:23

> いくつかの部分に切り分け例えば， 1. 大元の三角形 2. 三角形の各辺を外側に膨らませた部分（長方形）×３個 3. 三角形の頂点を膨らませた部分（円）×３個とかに分けて判定すればよい． 1. に困るなら「三角形　内外判定」とかでググればおｋ． 2. は単なる長方形vs点でしかない． 3. は点間の距離の判定でしかない．

行動規範の内容に同意します

ベストアンサー

所与の三角形をなす三点をA, B, C とします。
所与の円の中心をPとし、半径を r とします。
AとBを通る直線をL1, BとCを通る直線をL2, CとAを通る直線をL3 とします。(各辺を両端ともに延長して無限に長く伸ばして各直線L1, L2, L3にする、ということです。）
P からL1に下ろした垂線の足をH1とします。同様に PからL2に下ろした垂線の足をH2, PからL3に下ろした垂線の足をH3 とします。
PとH1の距離を d1 , PとH2の距離を d2, PとH3の距離を d3 とします。
このとき所与の円が三角形ABCの（いずれかの辺に接する場合も含めて、）内部にある必要条件は以下です。

　　　r ≦ min { d1, d2, d3 } 　--------- [1]

　　　すなわち「r が d1, d2, d3 のどれよりも大きくない」こと

　　です。

ただし上記の[1]は、円が三角形の内部にあるための必要条件であるけれども十分条件ではありません。
では [1] が満たされるとき、平面に描いた絵では何が言えるかというと、先のように辺AB, 辺BC, 辺CAを結んで延長した直線L1, L2, L3 を引くと、これらの直線を境界線として平面全体が三角形ABCの内部とその周りの6個の計7個の部分に分割されますが、[1] が満たされるとき半径 r の円はこれら7つの領域のうちのどれかひとつの中に（境界線に接することも許容し、）収まることになります。つまり2つ以上の領域にまたがることがないです。
そこで、条件[1] にもうひとつ何か2つめの条件を加えることで7つに分割された領域のうちのひとつである三角形ABCの中に円が収まっている必要十分条件にすればよいのですが、そのもうひとつの条件としては

　　　円の中心Pが三角形ABCの内側にある。ただし外周は含まない。 --------- [2]

　が満たされればよいです。

すなわち、与えられた円と三角形が[1]と[2]の両方を満たすならば、円は三角形の（いずれかの辺に接する場合も含め）内部に含まれます。

追記

上記の[1]かつ[2] を満たす円、つまり三角形ABCの内部に含まれる円の半径 r が最大値をとるとき円はどの辺とも接します。すなわち r = d1 = d2 = d3 となります。このときの円を三角形ABCの内接円(incircle) 、中心を三角形ABCの内心(incenter) と呼びます。内心は三角形ABCの3つの角それぞれの二等分線が交わる一点として求められます。

追記2

上記で回答したのは、所与の円が所与の三角形の（いずれかの辺に接する場合も含めて、）内部にある必要十分条件です。したがって、質問の「実現したいこと」の図にある、3つの円のうち上から二つ目の（三角形の一辺と2点で交わるような）円は三角形の内部に収まっていないものと判断されます。

投稿2022/10/28 12:38

編集2022/10/29 15:13

退会済みユーザー

総合スコア0

退会済みユーザー

2022/10/29 07:42

BAに選んで頂いた後で誠に申し訳ないのですが上記の回答は間違っていました。再検討して正しい条件を導出できましたら回答に追記させていただきます。

Ben_Muller

2022/10/29 10:57

お手数おかけします

退会済みユーザー

2022/10/29 15:25

回答を修正しました。修正の要点は下記です。修正前に回答した条件・r ≦ min { d1, d2, d3 } は円が三角形の内部に含まれるための必要条件ではありますがこれだけでは十分条件ではありませんでした。そこでこの条件に加えてもうひとつ・円の中心Pが三角形ABCの内側にあるを加えました。この両方が満たされるとき円は三角形の内部に含まれますし、逆に三角形の内部に含まれる円について、これら2つの条件が満たされます。どちらの条件も、xy座標上の計算に帰着させていくにはこの先まだかなりの作業が必要ですが、「xy座標平面での2点間の距離を求める」だったり「相異なる2点を通る直線の式」だったり「二直線が垂直に交わる条件」などの幾何学の基本をプログラムで書いていけば、回答に書いた [1]かつ[2] を書けるものと思います。

退会済みユーザー

2022/10/29 15:44

この回答は独力で（何も調べないで）導いたものですが、もっとよい公式なり導出の方法がありそうですね。興味深い質問をありがとうございました。

fana

2022/10/31 01:32

> r ≦ min { d1, d2, d3 } 正三角形の外接円（…は対象外だといういうなら「それをほんのちょっとだけ縮めた円」）とか考えるとそうはならない気がしますが…？重心から各辺に下した垂線の長さは重心から頂点までの距離よりも短いですよね．

行動規範の内容に同意します

あなたの回答