possible to check if two arc's intersect?

ottenm

Subject says it all. I'm drawing a number of arc's like this:

arc(x1, y1, w1, h1, start1, stop1, PIE);
arc(x2, y2, w2, h2, start2, stop2, PIE);

... and I'd like to find out before I draw them if the arcs intersect/overlap/share pixels (using these terms synonymously). It's not enough to check the two ellipses because the ellipses can overlap long before the arcs overlap.

Would prefer some nice elegant math, but I do have one duct-tape idea:
Draw both arcs to some kind of off screen buffer using semi-transparent fill colors, then scan the buffer for pixels colored to reflect an overlap. Big buffer, so probably check the ellipses first, then just check pixels within the ellipses somehow.

Very grateful for any suggestions!

koogs

do circle-circle collision first (distance between centres). if true then work out the (two) intersections. then check to see if these two intersections are on the drawn arcs.

http://mathworld.wolfram.com/Circle-CircleIntersection.html

and you'll probably need atan2() for the last bit

(um, might only work if w=h)

quark

You can get Processing code to find the intersection points here see page 3

ottenm

Super grateful for the suggestions! Thank you!

Struggling with two issues though.

The bigger issue: the intersection points only seem useful in some instances. For example, in the image below on the left neither point is on an arc, but the arcs overlap. And on the right, both points are on an arc, but the arcs don't overlap.

(can't get the image to display inline in the forum, I uploaded it here http://postimg.org/image/vfaqya7y9)

A smaller issue is with positive and negative radians. I'm taking the intersection points from the code at Quark's place and using atan2() to find their radians on (or not on) an arc. This is working 90% of the time. But a few situations stumble. For example, I have a 9:00-12:00 arc (drawn from 3.1 to 4.7 or PI to 1.25*PI). I have an intersection point right on the arc at about 11:30, but atan2() gives me radians of -1.6, and in code -1.6 does not fall between 3.1 and 4.7.

It's better than it used to be. I used to draw my arcs (pie chart slices) starting vertically at 4.71 and moving clockwise, always positive. So I used to draw this same 9:00-12:00 arc as 9.4 - 11.0 (radians). It drew fine, but using atan2() was only working in the first quadrant.

More concerned with the first issue. Sorry for the long post.

quark

atan2 return a value -PI to +Pi this needs to be converted to 0 to 2Pi. The following code will do that.

angle = (angle < 0) : angle + TWO_PI : angle;

quark

The other problem is shown in your first picture where the arc straddles the 0 degree position. This sketch has a function that determines whether an angle falls within an arc range defined in the clockwise direction.

You will need to check both arcs to ensure that the arcs intersect.

void setup() {
  println(isInRange(1.2, 0.7, 1.1), false);
  println(isInRange(1.2, 0.7, 1.9), true);
  println(isInRange(1.2, 1.9, 1.1), false); // Arc straddles zero point
  println(isInRange(1.8, 1.5, 0.4), true);  // Arc straddles zero point
  println(isInRange(0.1, 1.5, 0.4), true);  // Arc straddles zero point
}

/*
Determine whether an angle falls within an arc. Correction is made
 if the arc straddles the zero (east) position
 Parameters
 angle = angle to test
 arcStart the angle made by the anti-clockwaise end of the arc
 arcEnd   the angle made by the clockwaise end of the arc

 Note all angles must be in the range 0 to 2Pi
 */
boolean isInRange(float angle, float arcStart, float arcEnd) {
  if (arcStart <= arcEnd) {
    return angle >= arcStart && angle <= arcEnd;
  } else {
    return angle >= arcStart || angle <= arcEnd;
  }
}

koogs

For example, in the image below on the left neither point is on an arc, but the arcs overlap

no they don't. when you say arc do you mean sector?

http://www.nextlevelmaths.com/resources/other_resources/parts_of_a_circle/

ottenm

My bad Koogs! I've read close to 20 articles, references, and help posts related to drawing 'arc's with programming languages, and this is the first distinction I've seen between the one part of the stroke, and the rest of what gets drawn (albeit a math reference). Even 'arc's with noStroke() get called 'arc's.

So yes, trying to figure out if two sectors overlap, like when their 2 transparent fill colors would create a third shade.

Again, sorry for the disconnect.

ottenm

atan2 ... needs to be converted to 0 to 2Pi The other problem is ... where the arc straddles the 0 degree position

Awesome fixes Quark, thanks a million! I really struggle with trig and geometry issues. And maybe authority, too.