[SOLVED] Check if two arcs occupy the same space

[nordbjerg]

Hey LÖVErs!

I need a way to check if two arcs occupy the same space in a given circle, but I am unsure of how to go about it. The idea is that I can create nodes off of other nodes in my game, with each node having a specific arc / cirlce segment size. Of course, these segments must not occupy the same space in the given node.

Example of desired outcome:


What I have so far, which works in some cases :

Code: Select all

function pie:addSegment(start, size, r, g, b)
	local fits = true
	for _, segment in pairs(self.segments) do
		if (start + size > segment.start
			and start + size < segment.start + segment.size) then
			fits = false
			break
		end
	end

	if not fits then
		print("That segment can not fits!1!!")
	else
		table.insert(self.segments, { start = start, size = size, r = r, g = g, b = b })
	end
end

TL;DR / Solution

...

If this still does not work (rounding errors, maybe) then you can introduce an angular tolerance, which is a maximum overlap that is allowed:

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta <= (width1+width2)/2 - tolerance  then return true -- collision end
  return false
end

[micha]

You are dealing with angles here, but it works the same way as with intervals (lines). Let's say you have two intervals (a,b) and (c,d). How do you check if they overlap? It is easier to check if the do not overlap: There are only two cases possible: Either it is b < c or it is a > d. So, if you have for each arc the starting angle and the "width"-angle you can check like this:

Code: Select all

function arccollision (start1, width1, start2, width2)
  if start1+width1 < start2 or start2+width2 < start 1 then return false end-- no collision
  return true -- otherwise collision
end

The problem here, however, is that you have the full circle, which is closed. That means that 359° and 0° are close, even though the difference of the numbers is large. So I suggest you do not store the starting angle and the width of each arc, but the mid-angle and the width. Now the collision check is like this:

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta < (width1+width2)/2 then return true -- collision end
  return false
end

The variable delta calculates the "angular difference" between the two mid-angles. The stuff with the %(2*math.pi) and so on transforms this angle such that it is always between 0 and pi/2 (between 0° and 180°). Then the next line checks if this difference is smaller than the half of the sum of the two widths. In this case a collision happens.

[nordbjerg]

You are dealing with angles here, but it works the same way as with intervals (lines). Let's say you have two intervals (a,b) and (c,d). How do you check if they overlap? It is easier to check if the do not overlap: There are only two cases possible: Either it is b < c or it is a > d. So, if you have for each arc the starting angle and the "width"-angle you can check like this:

Code: Select all

function arccollision (start1, width1, start2, width2)
  if start1+width1 < start2 or start2+width2 < start 1 then return false end-- no collision
  return true -- otherwise collision
end

The problem here, however, is that you have the full circle, which is closed. That means that 359° and 0° are close, even though the difference of the numbers is large. So I suggest you do not store the starting angle and the width of each arc, but the mid-angle and the width. Now the collision check is like this:

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta < (width1+width2)/2 then return true -- collision end
  return false
end

The variable delta calculates the "angular difference" between the two mid-angles. The stuff with the %(2*math.pi) and so on transforms this angle such that it is always between 0 and pi/2 (between 0° and 180°). Then the next line checks if this difference is smaller than the half of the sum of the two widths. In this case a collision happens.

This actually made sense to me. Thank you for your very detailed and clear answer, sir

[nordbjerg]

I added your code and it worked great in any other case than this:

Code: Select all

p:addSegment(math.pi * 2.5, math.pi / 2, 255, 0, 0)
p:addSegment(math.pi * 2, math.pi / 2, 0, 0, 255)
p:addSegment(math.pi, math.pi, 0, 255, 0)

If I do math.pi / 2.05 it works, otherwise it will not fit. The syntax is pie:addSegment(start, size, r, g, b)

In my code I calculate the midangle like so:

Code: Select all

local midangle = start + (size / 2)

[micha]

This is probably because the edges of the two arcs are exactly equal. Try to fix this using the "<=" instead of "<":

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta <= (width1+width2)/2 then return true -- collision end
  return false
end

If this still does not work (rounding errors, maybe) then you can introduce an angular tolerance, which is a maximum overlap that is allowed:

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta <= (width1+width2)/2 - tolerance  then return true -- collision end
  return false
end

[nordbjerg]

...

If this still does not work (rounding errors, maybe) then you can introduce an angular tolerance, which is a maximum overlap that is allowed:

Code: Select all

function arccollision (mid1, width1, mid2, width2)
  delta = math.abs( (mid1-mid2+math.pi)%(2*math.pi)-math.pi)
  if delta <= (width1+width2)/2 - tolerance  then return true -- collision end
  return false
end

The tolerance did the trick, thank you =)