1

I am writing a converter for 2D geometry data. One of the elements I have to convert is an arc. In the source system the arc is described with two axis aligned rectangles. The first rectangle is a boundingbox for the circle of which the arc is part of. The second rectangle is a boundingbox for the arc itself. The constraint is, that the arc's boundingbox must intersect two edges of the circle's boundingbox. I know the coordinates of the top left and bottom right points of each rectangle.

The target system describes an arc as follows: A rectangle is a bounding box around the circle of which the arc is part of. So far it is the same as above. Then I have two points designating the start and end points of the arc. Both points must be exactly on the circle's "edge".

The question is: do you see an easy way to calculate the start and end-point of the arc? I have already seen this question but it seems really complicated. Perhaps there is an easier way to do this...

My thoughts so far:

It seems I must calculate the intersections of the edges of the arc's boundingbox with the circle. Two cases are possible (due to the restrictions mentioned above): only one edge intersects with the circle or two edges intersect with the circle. Additionally all other edges will always be outside of the circle.

Update: the start and end points cut the circle in two parts. Which of the two parts is draw as the arc, is determined by the order of the start and end points. The arc is always drawn counter clockwise from start to end point.

Community
  • 1
  • 1
McNumber
  • 177
  • 10
  • Which is the case when "only one edge intersects with the circle"? – Dr. belisarius Mar 11 '11 at 13:05
  • Also, the bounding box for a circle is a square, isn't it? (perhaps I am missing something important!) – Dr. belisarius Mar 11 '11 at 13:06
  • @belisarius: You are right, the bounding box for the circle is a square. But the second bounding box can and in most cases will be a rectangle. The case when "only one edge intersects with the circle" is when the edge intersects the circle two times. The arcs end points will both have the same x or y coordinate. – McNumber Mar 11 '11 at 18:54

1 Answers1

1

Call the outer box coordinates top, left, bottom and right. The centre and radius are then:

centre.x = (left + right)/2
centre.y = (top + bottom)/2
radius = (right - left)/2

From this we can write an equation that must be satisfied for all points on the circle perimeter:

(x - centre.x) * (x - centre.x) + (y - centre.y) * (y - centre.y) = radius * radius

The inner box coordinates give you possible values of x and y. Substitute one in at a time and solve as a standard quadratic equation. If there is a real solution and the corresponding point is within the span of the inner box, that's a point. Given the constraints of the original data, you should find there are two points -- those are your answer.

walkytalky
  • 9,453
  • 2
  • 36
  • 44
  • Thanks a lot, that's a good solution. I have already implemented it. Currently I am fighting with some minor issues, but these should be solved soon. – McNumber Mar 11 '11 at 18:56