Page 1 of 1

[SOLVED] Check if two arcs occupy the same space

Posted: Thu Jun 13, 2013 11:24 pm
by nordbjerg
Hey LÖVErs! :neko:

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:
Image

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

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
micha wrote:...

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

Re: Check if two arcs occupy the same space

Posted: Fri Jun 14, 2013 5:48 am
by 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.

Re: Check if two arcs occupy the same space

Posted: Fri Jun 14, 2013 12:53 pm
by nordbjerg
micha wrote: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 :awesome:

Re: Check if two arcs occupy the same space

Posted: Fri Jun 14, 2013 1:16 pm
by 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)

Re: Check if two arcs occupy the same space

Posted: Fri Jun 14, 2013 1:24 pm
by 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

Re: Check if two arcs occupy the same space

Posted: Fri Jun 14, 2013 6:09 pm
by nordbjerg
micha wrote:...

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