时间戳

首页 > 解决方案 > 查找一个圆是否完全包含在多个三角形中？

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

问题描述

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

视觉示例

在这里，红色部分是外部三角形，因此圆圈不包含在其中。有没有一种算法可以检测到这一点？

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

标签： mathcollision-detection

解决方案

所以基本上，三角形形成一个具有多边形边界的域，您想检查由中心点和半径定义的磁盘是否包含在域内。因此，如果您从三角形开始，您必须找到一种方法来提取域的多边形边界并将其表示为形状为 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))

推荐阅读