Intersection between two arcs? (arc = distance between pairs of angles)

Question

I am trying to find a way to calculate the intersection between two arcs. I need to use this to determine how much of the arc is visually in the right half of the circle, and how much is on the left. I’m at least about creating an arc of the right half and intersect this with the actual arc. But I need a lot of time to solve this, so I thought about asking here - someone should have done this before.

Edit: I wish the previous illustration was provided when my head was too heavy after the corners of the crunch. I will try to explain again:

In this link you can see that I cut the arc in the middle to two halves, the right side of the arc contains 135 degrees, and the left side - 90.

This arc starts at -180 and ends at 45. (or starts at 180 and ends at 405 when normalized).

I managed to create this code to calculate the number of arc degrees contained on the right side, and on the left side:

f1 = (angle2>270.0f?270.0f:angle2) - (angle1<90.0f?90.0f:angle1); if (f1 < 0.0f) f1 = 0.0f; f2 = (angle2>640.0f?640.0f:angle2) - (angle1<450.0f?450.0f:angle1); if (f2 < 0.0f) f2 = 0.0f; f3 = (angle2>90.0f?90.0f:angle2) - angle1; if (f3<0.0f) f3=0.0f; f4 = (angle2>450.0f?450.0f:angle2) - (angle1<270.0f?270.0f:angle1); if (f4<0.0f) f4=0.0f; 

It works fine after normalizing the angles to be non-negative, but, of course, starting at 360 degrees. Then f1 + f2 gives me the sum of the left half, and f3 + f4 gives me the sum of the right half. It also does not take into account the case when the arc is defined as more than 360, which may be a “mistake”.

BUT, this seems like a "workaround", not a correct mathematical solution. I am looking for a more elegant solution, which should be based on the "intersection" between two arcs (because mathematics has no "sides", and not visually ";

Thanks!!

Answer 1

I think this works, but I have not tested it completely. You have 2 arcs, and each arc has a start angle and a stop angle. I will work in degrees, measured clockwise from the north, as you did, but it is just as easy to work in radians, measured counterclockwise from the east, as mathematicians do.

First, "normalize" your arcs, i.e. reduce all the angles in them to lie in [0,360) , so print the multiple values ​​of 360deg and do all the angles + ve. Make sure that the stop angle of each arc lies clockwise from the start angle.

Then select the starting angle of one of your arcs, no matter what. Sort all the angles that you have (4 of them) in numerical order. If any of the corners is numerically smaller than the starting angle you selected, add 360deg to them.

Repeat sorting the angles in increasing numerical order. Your selected starting angle will be the first item in the new list. From the starting corner that you have already selected, what is the next corner on the list?

1) If this is the stop angle of the same arc, then either there is no overlap, or this arc is entirely contained within another arc. Take a note and find the next corner. If the next angle is the angle of the start of another arc, there is no overlap, and you can stop; if this is the stop angle of the other arc, then the overlap contains the entire first arc. Stop

2) If this is the starting angle of another arc, then the overlap starts from this angle. Write down this corner. The next corner you hit should be the stop angle, and the overlap ends. Stop.

3) If this is the stop angle of another arc, then the overlap contains the angle between the initial angle of the first arc and this angle. Stop.

It's not particularly elegant and relies on ifs more than usual, but it should work and be relatively easy to translate into your favorite programming language.

And look, no trigonometry at all!

EDIT

This is a more “mathematical” approach, since you seem to feel the need.

For theta angle in (-pi,pi] hyperbolic sinusoidal function (often called sinh ) maps the angle to a segment on the real line in the interval (approximately) (-11.5,11.5] . In contrast to arcsin and arccos inverse function is also unique in the same interval: Follow these steps:

1) If the arc includes 0, break it into 2 arcs, (start,0) and (0,stop) . Now you have 2, 3 or 4 intervals on a real line.

2) Calculate the intersection of these intervals and convert back from the linear dimension to the angular dimension. Now you have the intersection of two arcs.

Answer 2

This test can be resumed using a single line test. Even if a good answer has already been sent, let me introduce mine.

Suppose that the first arc is A:(a0,a1) , and the second is B:(b0,b1) . I assume that the angle values ​​are unique, that is, in the range [0°,360°[ , [0,2*pi[ or ]-pi,pi] (the range itself is not important, we will see why). I will take the range ]-pi,pi] as the range of all angles.

---

To explain the approach in detail, I first developed a test for intersecting intervals in R. Thus, here we have a1>=a0 and b1>=b0 . Following the same notation for real intervals, I calculate the following value:

 S = (b0-a1)*(b1-a0) 

If S>0 , two segments do not overlap, otherwise their intersection is not empty. It is really easy to see why this formula works. If S>0 , we have two cases:

• b0>a1 means that b1>a0 , so there is no intersection: a0=<a1<b0=<b1 .

• b1<a0 means that b0<b1 , so there is no intersection: b0=<b1<a0=<a1 .

So, we have one mathematical expression that works well in R.

---

Now I rotate it in a circular area ]-pi,pi] . The hypotheses a0<a1 and b0<b1 no longer true: for example, the arc can go from pi/2 to -pi/2 , this is the left semicircle. Therefore, I calculate the following value:

 S = (b0-a1)*(b1-a0)*H(a1-a0)*H(b1-b0) 

where H is a step function defined by H(x)=-1 if x<0 else H(x)=1

Again, if S>0 , there is no intersection between arcs A and B. There are 16 cases to study, and I will not do this here ... but they are easy to do on the sheet :).

Note : S value is not important, just condition signs. The beauty of this formula is that it does not depend on the range that you have adopted. Alternatively, you can rewrite it as a logical test:

 T := (b0>a1)^(b1>a0)^(a1>=a0)^(b1>=b0) 

where ^ is a logical XOR

---

EDIT

Alas, there is an obvious case of failure in this formula ... Therefore, I will fix it here. I understand that htere is a case where the intersection of two arcs can be two arcs, for example, when -pi<a0<b1<b0<a1<pi .

The solution to fix this is to introduce a second test: if the sum of the angles is above 2*pi , then the arcs intersect exactly.

Thus, the formula is equal to:

 T := (a1+b1-a0-b0+2*pi*((b1<b0)+(a1<a0))<2*pi) | ((b0>a1)^(b1>a0)^(a1>=a0)^(b1>=b0)) 

Well, it’s less elegant than the previous one, but now it’s correct.