Boolean function for intersection between circular segment and circle

[Starnub]

Hey guys, I've been trying to figure out how to find out if a segment and another circle intersect given the following:
Circle X, Y
Circle radius

Sector X, Y
Sector radius
Sector angle 1
Sector angle 2

From a bit of Googling I found this but my stupid dumb brain can't figure out which language this is written in.
https://math.stackexchange.com/question ... tersection

Any help would be greatly appreciated!

EDIT: I just realised I said segment instead of sector, sorry!

[darkfrei]

Can you draw the situation?
Why not just intersection of two circles?

[pgimeno]

Do they intersect if the sector is contained within the circle, or did you mean a circumference rather than a circle?

[Starnub]

Can you draw the situation?
Why not just intersection of two circles?

This is for a simple game I'm making, basically I need to figure out if the red circle lies within the circle sector here.

[Starnub]

Do they intersect if the sector is contained within the circle, or did you mean a circumference rather than a circle?

There wouldn't be a situation where the sector lies within the circle, here's an image of what I'm working with.

[BrotSagtMist]

Might be easier to see it as triangle instead.
Given a point, a range and an angle you can calculate another point.
With two points you can calculate the function of a line.
Having two lines you need to resolve booth using your balls x position.
In other words: if we resolve the lower line using the balls x and the result is greater than the balls y and the result of the upper line is lower we are inside. And for the front we just use a distance check.

[Starnub]

Might be easier to see it as triangle instead.
Given a point, a range and an angle you can calculate another point.
With two points you can calculate the function of a line.
Having two lines you need to resolve booth using your balls x position.
In other words: if we resolve the lower line using the balls x and the result is greater than the balls y and the result of the upper line is lower we are inside. And for the front we just use a distance check.

How would I find the end point of the sector lines? Sorry I haven't done math in years and I've never been good at it.

[BrotSagtMist]

What end point? Lines are infinitive.

[Starnub]

What end point? Lines are infinitive.

OH right I forgot about the distance check, this is great. Thank you very much!

[pgimeno]

Ok, the diagram helped. It's tricky because there are some corner cases (literally) that need to be handled. Here's a function:

Code: Select all

local sin, cos, sqrt = math.sin, math.cos, math.sqrt

local function withinSector(tx, ty, tr, sx, sy, ar, a1, a2)
  -- First filter is the easiest and fastest - a square of radius vr+tr
  if   tx <= sx-(ar+tr)
    or tx >= sx+(ar+tr)
    or ty <= sy-(ar+tr)
    or ty >= sy+(ar+tr)
  then
    return false
  end
  -- Second filter is by distance - a circle of radius vr+tr
  local stx = tx-sx
  local sty = ty-sy
  local dist = sqrt(stx*stx + sty*sty)
  if dist >= ar + tr then
    return false
  end
  -- Now for the gist of it.
  local vertex1x, vertex1y, vertex2x, vertex2y
  local normal1x, normal1y, normal2x, normal2y
  local vsx, vsy
  local dot1, dot2
  vertex1x, vertex1y = cos(a1), sin(a1)
  normal1x, normal1y = -vertex1y, vertex1x
  -- To account for the target radius, we displace the sentry by the normal
  -- times the radius of the target, giving a "virtual sentry" position
  vsx, vsy = sx - normal1x * tr, sy - normal1y * tr
  -- Calculate the dot product of the vector VV->Target and the normal
  dot1 = (tx - vsx) * normal1x + (ty - vsy) * normal1y
  -- Repeat with the other line; the normal is the opposite
  vertex2x, vertex2y = cos(a2), sin(a2)
  normal2x, normal2y = vertex2y, -vertex2x
  vsx, vsy = sx - normal2x * tr, sy - normal2y * tr
  dot2 = (tx - vsx) * normal2x + (ty - vsy) * normal2y
  -- We can now reject many cases
  -- This would benefit from having the funnel angle instead of calculating it
  local span = a2 - a1
  if span < 0 then span = span + 6.283185307179586 end
  if span >= 3.141592653589793 then
    -- the area covers >= 180 degrees; we can discard if both dot products
    -- are negative
    if dot1 < 0 and dot2 < 0 then return false end
  else
    -- the area covers < 180 degrees; we can discard if either dot product is
    -- negative
    if dot1 < 0 or dot2 < 0 then return false end

    -- In this case, the corner at the sentry's position needs to be checked.
    -- If the target and both segments' endpoints are at opposite sides of
    -- the normal, the previously calculated result is invalid and needs to be
    -- evaluated based on distance to the corner (the sentry's position).
    dot1 = vertex1x * (tx - sx) + vertex1y * (ty - sy)
    dot2 = vertex2x * (tx - sx) + vertex2y * (ty - sy)
    if dot1 < 0 and dot2 < 0 then
      -- The result depends entirely on the distance to the sentry
      return dist < tr
    end
  end
  -- Now for the corners at the ends of the segments. First, if the distance
  -- is less than the arc's radius, the result is already accurate and we have
  -- a collision.
  if dist < ar then
    return true
  end
  
  -- Now, check which side of the segments the centre of the target is with
  -- respect to the normal. If either is on the arc's side, the result is
  -- already correct; return true.
  dot1 = (tx - sx) * normal1x + (ty - sy) * normal1y
  dot2 = (tx - sx) * normal2x + (ty - sy) * normal2y
  if dot1 >= 0 and dot2 >= 0 or span >= 3.141592653589793 and (dot1 >= 0 or dot2 >= 0) then return true end
  -- The collision is now solely determined by the distance to either corner
  dist = sqrt((vertex1x * ar + sx - tx)^2 + (vertex1y * ar + sy - ty)^2)
  if dist < tr then return true end
  dist = sqrt((vertex2x * ar + sx - tx)^2 + (vertex2y * ar + sy - ty)^2)
  return dist < tr  
end

Example attached. Control with the mouse: no button = move the sentry; hold LMB to adjust view direction using mouse horizontal movement; hold RMB to adjust how wide the view is using mouse horizontal movement.