[SOLVED] Check if two arcs occupy the same space

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
nordbjerg
Prole
Posts: 12
Joined: Thu Jun 13, 2013 9:17 pm

[SOLVED] Check if two arcs occupy the same space

Post 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
Last edited by nordbjerg on Fri Jun 14, 2013 6:09 pm, edited 1 time in total.
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: Check if two arcs occupy the same space

Post 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.
nordbjerg
Prole
Posts: 12
Joined: Thu Jun 13, 2013 9:17 pm

Re: Check if two arcs occupy the same space

Post 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:
nordbjerg
Prole
Posts: 12
Joined: Thu Jun 13, 2013 9:17 pm

Re: Check if two arcs occupy the same space

Post 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)
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: Check if two arcs occupy the same space

Post 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
nordbjerg
Prole
Posts: 12
Joined: Thu Jun 13, 2013 9:17 pm

Re: Check if two arcs occupy the same space

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

Who is online

Users browsing this forum: Bing [Bot] and 7 guests