查找一个圆是否完全包含在多个三角形中？

Question

在游戏中，区域由永不重叠的三角形定义，角色由圆圈定义。我怎么知道整个角色的碰撞圈是否包含在这些三角形内？示例图片：

这里，红色部分是三角形的外部，所以圆不包含在其中。有算法可以检测到吗？

我只提出了“不完美”的解决方案，比如在圆的边界采样点，然后测试每个点是否在三角形内。

Answer 1

所以基本上，三角形形成一个具有多边形边界的域，您想要检查域内是否包含由中心点和半径定义的圆盘。所以如果你从三角形开始，你必须找到一种方法来提取域的多边形边界并将其表示为形状为 n 行和两列的二维数组（矩阵），以便每一行都是顶点的两个坐标多边形边界线的点和这些点是有序的，以便它们在逆时针位置沿边界连续排列，即当您沿着从索引点 i 到下一个点 i+1 的方向行走时该域名位于您的左侧。例如，这里是像您这样的域的多边形边界的表示：

a = 4/math.sqrt(3)
Pgon = np.array([[0,0],
                 [a,0],
                 [2*a,-1],
                 [2*a+4,0],
                 [2*a+4,4],
                 [2*a,4],
                 [2*a,2], 
                 [a,1], 
                 [a,4],
                 [0,0]])

观察第一个点和最后一个点是一样的。

遇到这种情况，或许可以试试下面的算法：

import numpy as np
import math

def angle_and_dist(p1, p2, o):
  p12 = p2 - p1
  op1 = p1 - o
  op2 = p2 - o
  norm_p12 = math.sqrt(p12[0]**2 + p12[1]**2)
  norm_op1 = math.sqrt(op1[0]**2 + op1[1]**2)
  norm_op2 = math.sqrt(op2[0]**2 + op2[1]**2)
  p12_perp = np.array([ - p12[1], p12[0] ])
  h = - op1.dot(p12_perp)
  theta12 = op1.dot(op2) / (norm_op1*norm_op2)
  theta12 = math.acos( theta12 )
  if h < 0:
    theta12 = - theta12
  if op1.dot(p12) > 0:
    return theta12, norm_op1
  elif op2.dot(p12) < 0:
    return theta12, norm_op2
  else:
    return theta12, h/norm_p12

def is_in_polygon(p, disk):
  o, r = disk
  n_p = len(p)-1
  index_o = 0
  h_min = 400
  for i in range(n_p):
    theta, h = angle_and_dist(p[i,:], p[i+1,:], o)
    index_o = index_o + theta
    if 0 <= h and h < h_min:
      h_min = h
  if theta <= math.pi/100:
    return 'center of disc is not inside polygon'
  elif theta > math.pi/100:
    if h_min > r:
      return 'disc is inside polygon'
    else:
      return 'center of disc is inside polygon but disc is not'

a = 4/math.sqrt(3)

Pgon = np.array([[0,0],
                 [a,0],
                 [2*a,-1],
                 [2*a+4,0],
                 [2*a+4,4],
                 [2*a,4],
                 [2*a,2], 
                 [a,1], 
                 [a,4],
                 [0,0]])

# A test example:
#disc = (np.array([3*a/4, 2]), a/4-0.001)
disc = (np.array([3*a/4, 2]), math.sqrt(3)*a/8 - 0.0001)

print(is_in_polygon(Pgon, disc))

查找一个圆是否完全包含在多个三角形中？

Finding if a circle is fully contained within multiple triangles?

math

collision-detection