Search code examples
mathcollision-detection

Finding if a circle is fully contained within multiple triangles?

In a game, an area is defined by triangles that never overlap, and characters are defined by circles. How can I know whether the full character's collision circle is contained within these triangles? Example image:

visual example

Here, the red parts are outside triangles, so the circle isn't contained within them. Is there an algorithm that can detect this?

I've only came up with "non-perfect" solutions, like sampling points at the border of the circle, then testing if each is inside a triangle.

Solution

  • So basically, the triangles form a domain with polygonal boundary and you want to check if a disk, defined by a center point and a radius is contained inside the domain. So if you start with the triangles, you have to find a way to extract the polygonal boundary of your domain and represent it as a 2D array (matrix) of shape n rows and two columns so that every row is the two coordinates of a vertex point of the polygonal boundary line and the points are ordered so that they are consecutive order along the boundary in a counterclockwise position, i.e. when you walk in a direction from point of index i to the next point i+1 the domain stays on your left. For example, here is the representation of a polygonal boundary of a domain like yours:

    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]])

    Observe that the first and the last points are the same.

    In such a scenario, maybe you can try the following algorithm:

    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))