check if two segments on the same circle overlap / intersect

user_145999 0
Viewed 2331

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.

2d angle language-agnostic geometry algorithm
4 Answers

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.

user_134660830
Related