2

Possible Duplicate:
Circle line collision detection

I'm trying to do collision testing between a finite line segment, and an arc segment. I have a collision test which does line segment vs. line segment, so I was going to approximate these arc segments with line segments and run my existing test.

The data I have defining the arc segment(s) are three points. Two of which are endpoints that lie on the circumference of a circle, and the third point is the center of that circle.

So far this is what I've got:

Let (a,b) be the center point of the circle, let 'r' be the radius of the circle, and (x1, y1), (x2, y2) be the endpoints of the arc segment which lies on the circumference of the circle.

The following parametric equations give the x, and y locations of an arc. 't' is the parametric variable.

x = a + r * cos(t) y = b + r * sin(t)

To create the line segments from the arc, I wanted to walk the arc for some fixed ratio of 't' creating line segments along the way, until I've reached the end of the arc. To do this I figured I'd have to find the start and end angle. I'd start walking the arc from the start angle, and end at the end angle. Since I know the start and end points I figured I could use these equations to solve for these angles. The following are my equations for this:

t = arccos((x-a)/r)

or

t = acrcsin((y-b)/r)

The problem I'm having is that the range of values returned by these functions (http://en.wikipedia.org/wiki/Inverse_trigonometric_function) is limited, so there is a high probability that the angle I'm looking for will not be returned because these functions are multivalued: arcsin(0) = 0, but also arcsin(0) = π, arcsin(0) = 2π, etc

How do I get the exact angle(s) I'm looking for? Or, can you think of a better/different way of achieving my goal?

Community
  • 1
  • 1
Christopher Perry
  • 38,891
  • 43
  • 145
  • 187
  • I edited your question title because it seems like you're really asking how to compute angles, and the problem of approximating a curve with line segments is just the context. – David Z Sep 13 '10 at 22:55
  • the endpoints of the arc & the center of the circle specify either of two arcs (they complement eachother to make up the entire circle). how do you determine which arc is relevant? – Jonathan Sep 13 '10 at 23:03

3 Answers3

4

Take a look at the atan2 function, which should exist in whatever programming language or math library you're using. It takes two arguments, the x and y coordinates of a point (for you: (x-a)/r and (y-b)/r) and returns the angle in the range -π to +π.

David Z
  • 128,184
  • 27
  • 255
  • 279
3

At least IMO, you're going at this the wrong way. A line has an equation y=mx+b. A circle has an equation x2 + y2 = r2. You're looking for a point at which the x and y of the circle equals the x and y of the line. You can do that by substituting the mx+b equation for the line for the y equation in the circle, and then solve using the quadratic equation.

The equations involved do get a bit long, but quite a few web pages (e.g., http://www.sonoma.edu/users/w/wilsonst/papers/geometry/circles/default.html) have them, at which point it's simple matter of implementing the equations as a couple of functions and plugging in the values for your particular circle/line. A solution based on these equations complete avoids the ambiguity from using an arg tangent.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • I agree. See where the line and circle intersect; if there is a point or points, then test whether they are on both the segment and the arc. – erickson Sep 13 '10 at 23:37
  • the equation quoted for a circle is only for a circle centered at the origin, by the way. – Jonathan Sep 14 '10 at 02:13
  • @Jonathon: True, I didn't want to get things too complex here -- the idea was to point out the general idea of how one can be substituted into the other to find where (if anywhere) they're equal. The cited page uses the full equation though. – Jerry Coffin Sep 14 '10 at 03:07
1

Your pseudo-code looks a lot like Python. If you don't mind using Python I would recommend the Shapely Library. If you just want the algorithm, check the source.

Shapely objects have the 'simplify' and 'intersection' methods.

Paulo Scardine
  • 73,447
  • 11
  • 124
  • 153