check if two segments on the same circle overlap / intersect

Question

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

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

How can I find out if these two circle segments overlap? (i.E. if they intersect or touch in 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 

This looks like a deceptively simple problem but I cannot wrap my head around it. I currently have a basic idea for a solution which involves splitting each segment into two if it crosses 0°, but I am not sure if that covers all cases, and I was wondering if there is an elegant formula.

Homey

possible duplicate of Intersection between two Arcs? (arc = distance between pair of angles) – Aquarist

Given you don't specify radius of circle or center are we to assume that the arcs are on the same circle? – Lucubrate

@HighPerformanceMark I do not think that other question is a duplicate. The answer for that question involves sorting arrays and managing a list of neighboring segments. – Homey

@Lucubrate Yes, the segments are on the same circle; I had that in the text, but the title might have been unclear, I modified the question title to reflect this fact – Homey

@HighPerformanceMark I just saw you modified the link; that other question looks indeed related, thought they only appear to have angles between 0° and 360°. The answer seems similar to my basic idea of splitting segments, I'd be interested to find out if that is indeed a working solution for my problem, and if there are any better ones? – Homey

Answer 1

As @admaoldak mentioned, normalize the degrees first:

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

Now to check if b1 is within (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 is:

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)

Offing

Thanks! This is what I used; altough if speed were an issue, I think that it would be sufficient to only check for intersect(b1_norm,a1_norm,a2_norm)||intersect(a1_norm,b1_norm,b2_norm) to cover all cases – Homey

what about A=[ -45°, 45°]; B=[ 180°, 359°] ==> overlap – Haemoid

Note, modulos often aren't implemented correctly for negative numbers (I don't know about python but it is the case in most C lineage languages) – Closure

Answer 2

For an interval [i.X , i.Y] , let's 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 = i.X + 360
2. i_slide.Y = i.Y + 360

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

normalize(A) interval-overlaps with normalize(B)

or

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

interval-overlaps is defined in the same way as "intersection" in adamoldak's post.

and both operations normalize() and slide() are easy to be implemented.

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

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

and [315,405] interval-overlaps with [370,380]

Tailorbird

Switch A & B and your example breaks. You need to check norm(A) vs norm(B), slide(norm(A)) vs norm(B) & norm(A) vs slide(norm(B) – Cadmann

Answer 3

I have a similar problem with a game engine with rectangles overlapping in a looping map. I've thought about it a lot and have looked at some of you guys' answers. If you're looking for performance, this is the best you can get (until someone proves me wrong :P):

#assume the angles are already normalised
def overlap(a1, a2, b1, b2):
  if a2 - a1 + b2 - b1 > 360: #must overlap
    return True
  return (b1 > a2) ^ (b2 > a1) ^ (a2 < a1) ^ (b2 < b1)

Elegant. Elegant and kinda ugly.

Perambulator

Answer 4

How about normalizing each degree value to 0-360:

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

Then you just check for intersection:

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

Gilud

A=[-45°,45°]; B=[10°,20°] ==> A=[315°,45°]; B=[10°,20°], then a1_norm is > b2_norm despite overlap – Homey