Check if two segments intersect / intersect on the same circle

Question

Given two circular segments of the same circle: A = [a1, a2] and B = [b1, b2], with:

• a1, a2, b1, b2 to the degree between -inf and + inf
• a1 <= a2; b1 <= b2
• a2-a1 <= 360; b2-b1 <= 360

How can I find out if these two segments of a circle overlap? (that is, if they intersect or touch at least one point)

Examples:

A=[ -45°, 45°]; B=[ 10°, 20°] ==> overlap A=[ -45°, 45°]; B=[ 90°, 180°] ==> no overlap A=[ -45°, 45°]; B=[ 180°, 360°] ==> overlap A=[ -405°, -315°]; B=[ 180°, 360°] ==> overlap A=[-3600°, -3601°]; B=[ 3601°, 3602°] ==> overlap (touching counts as overlap) A=[ 3600°, 3601°]; B=[-3601°,-3602°] ==> overlap (touching counts as overlap) A=[ -1°, 1°]; B=[ 3602°, 3603°] ==> no overlap 

It looks like a deceptively simple problem, but I can't wrap myself around it. I currently have a basic idea for a solution that involves splitting each segment into two if it intersects 0 °, but I'm not sure if this applies to all cases, and I was wondering if there is an elegant formula.

Answer 1

As @admaoldak mentioned, normalize degrees first:

 a1_norm = a1 % 360 a2_norm = a2 % 360 b1_norm = b1 % 360 b2_norm = b2 % 360 

Now, to check if b1 is inside (a1, a2),

 def intersect(b, as, ae Intersect = False If as > ae: if b >= as or b <= ae: return True Else: if b>=as and b<=ae: return True return False 

Final answer:

 intersect(b1_norm,a1_norm,a2_norm)||intersect(b2_norm,a1_norm,a2_norm)|| intersect(a1_norm,b1_norm,b2_norm)||intersect(a2_norm,b1_norm,b2_norm) 

Answer 2

For the interval [iX, iY] we define the normalization i_norm = normalize (i) so that:

 1. 0 <= i_norm.X < 360 2. i_norm.X <=i_norm.Y 

then we define another operation i_slide = slide (i) so that:

 1. i_slide.X = iX + 360 2. i_slide.Y = iY + 360 

we can prove that, for your input A and B , A overlaps with B if and only if:

normalize (A) overlap interval with normalize (B)

or

normalize (A) overlaps the interval with the slide (normalize (B))

interval overlaps are defined in the same way as "intersection" in post admoldak.

and both normalize () and slide () are easy to implement.

take your example: A=[-45°,45°]; B=[10°,20°] A=[-45°,45°]; B=[10°,20°] , we have

 normalize(A) = [315,405] normalize(B) = [10,20] slide( normalize(B) ) = [370,380] 

and [315,405] intervals overlap with [370,380]

Answer 3

How about normalizing the value of each degree to 0-360:

 a1_norm = a1 % 360 a2_norm = a2 % 360 b1_norm = b1 % 360 b2_norm = b2 % 360 

Then you just check the intersection:

 (a1_norm <= b2_norm) and (a2_norm<= b1_norm)