Thread: How to select an arc using a window?

I am developing a CAD software which has line, circle and arc objects. I want to select the objects using a window. Whichever objects lie inside the window 'completely' should be selected. I can determine if a line or circle lies inside the window. But I don't know how to determine if an arc lies inside the window. Can anyone please help me?

I'm not 100% sure about this, but I think that assuming your window is rectangular you should just calculate the four points on the circle containing the arc which are on the circle diameters that are parallel to the sides of the rectangle (so probably the north,south,east and west points on the circle). If both the end points of the arc, and all of these points that are in the arc are also in the window the arc lies entirely in the window, otherwise not. The arc could not reenter the circle without passing through one of these points and these points are the ones that are bound to be outside the rectangle if any are.

Thank you very much! I tried the logic and it worked!! My processing time has greatly reduced. This is much optimized solution.

Now, if I want to select the arc if it is 'partly' inside the window, is there any optimized solution? My algorithm right now takes 30 seconds to make the selection for a huge profile. I want to reduce this time.

By partly I mean if only a part of the arc is inside the window.

The solution will depend on how you want to choose which arc to select when multiple arcs lie partly within the window: for example do you want to select the arc with the highest percentage of itself inside the window or the arc with the longest length in the window.
But in any case you would probably need to calculate the intersections of the arc with the sides of the rectangle, so that you could work out exactly how much of each arc is in the rectangle. That's likely to be slow, so instead maybe you could do things another way: if an arc is partly outside the window calculate how much you would have to grow the window for that arc to be totally visible. You can use the end-points of the arc and the north,south,east,west points as before. If the arc is partly outside the window at least one of these points is outside and as far outside the window as possible, so if no arc is partly inside the window just pick the one that minimises this distance. That will probably be a good choice, though your program should probably allow the user to specify which arc he wants when several choices are plausible, for example by attaching some widget they can click to each arc.

Hey, Thanks for providing that useful information. But I am very-very sorry that my second question was wrong. Actually, it was after posting the question that I found that it was not 'cause of the 'arcs' but because of the 'lines' that my program is taking time. My algorithm for selecting arcs is running fine; but for selecting 'line partly lying inside the window' is eating time. So, my problem is 'how to select a line which is partly inside the window??' Can I get help for this?

Again, I am sorry for the inconvenience.

How are you testing whether lines (and I presume you actually mean line segments) are inside the window? Are you doing this with a general segment-segment intersection test?
If so it *might* be better to do some other tests first. For example you can check whether at least one endpoint of the segment is inside the window. If so the segment overlaps the window. Also if the segment is entirely to the left, right,above or below the window then the segment does not overlap the window at all. These tests are probably cheaper than a full segment-segment intersection test since they only need comparisons, so you might be able to save time by doing these tests first and only doing a full segment-segment test for the doubtful cases.
If this doesn't speed things up you should look into whether your intersection test can be speeded up. For example, assuming you are writing in C++ or C if you are using some library function to test segment intersection maybe you should see if you can implement your own more efficient test better. If you are not using a natively compiled language than you probably won't be able to get the same performance that you could from C/C++. Possibly you can look into whether you could speed things up by precalculating some of the values you need for doing the tests, or sorting the segments somehow.

Before taking the intersections, I check whether either end-point is inside the window.

But I don't know how to decide if line is entirely above,below,right or left to the window. To decide, whether line is passing partly, I take the distance of the line from the centre of window.

If (distance <= length/2) or (distance <= breadth/2), I take the intersections
otherwise I return false. (where length is length of window and breadth is breadth of window)

Will this logic work to decide above,below,left,right case? Or is there any other method?

If your lines are actually segments then I'd expect you to be storing the two end-points. Clearly if both end-points are above the window then the segment is completely above the window. The cheapest way to calculate this for all four sides is probably to compute and store the rectangle containing the segment, and to check this intersects the window rectangle. If not the segment is entirely outside the window.

How do you calculate the distance of the line from the centre of the window? You should not use Pythagoras. Instead store the line as a triple [a,b,c] representing equation ax+by+c=0 of the line with a^2+b^2=1. Now for any point ax+by+c is the signed distance of the point from the line. Now your test for the line should be to compute the absolute value of this quantity for the centre of the window. It it is less than sqrt(width^2+height^2)/2 then the segment might intersect the window but you only need to do this test if the rectangle intersection test passed. Obviously you should compute the maximum radius of the window just once.

If a significant proportion of your lines are parallel to the sides of the window you should probably treat these as special cases, because much simpler tests will determine if they intersect the window than for segments in general position.

Also, if a significant proportion of the segments have common end-points it will probably pay to store information about the end-points, and for the segment information to contain references to shared end-point objects rather than duplicating this information in each segment. Then you can afford to do things like adding an "is_inside_window" bit to the end-point. You'd probably need an "is_inside_computed" bit as well which would be clear initially or after the window has moved and set after you had computed this for that end point.

Originally Posted by alunw

If your lines are actually segments then I'd expect you to be storing the two end-points. Clearly if both end-points are above the window then the segment is completely above the window. The cheapest way to calculate this for all four sides is probably to compute and store the rectangle containing the segment, and to check this intersects the window rectangle. If not the segment is entirely outside the window.

How do you calculate the distance of the line from the centre of the window? You should not use Pythagoras. Instead store the line as a triple [a,b,c] representing equation ax+by+c=0 of the line with a^2+b^2=1. Now for any point ax+by+c is the signed distance of the point from the line. Now your test for the line should be to compute the absolute value of this quantity for the centre of the window. It it is less than sqrt(width^2+height^2)/2 then the segment might intersect the window but you only need to do this test if the rectangle intersection test passed. Obviously you should compute the maximum radius of the window just once.

I calculate the distance of the line from centre using equation of the line, not by Pythagoras. And then I compare with sqrt(width^2+height^2) and process.

But you said to take intersection of the rectangular window with rectangle associated with line. How do you take that? If it means to take intersections of every individual line of one rectangle with that of the other, won't it take more time? I am not sure how to do this, so I haven't implemented this. Yet, now my algorithm is greatly optimized. Initially it would take 30 seconds and now it takes just 5 seconds to select the objects! Thank you very much!!

Say you stored the window rectangle as bottom,left,top,right in variable and window_rect, and the segment rectangle in bottom,left,top,right in segment_rect. Then this test checks if the rectangles intersect (assuming y axis points upwards rather than down). I'm also assuming a convention where rectangles contain the bottom and left boundary but not the right or top boundary.

Code:

rects_intersect = 
  segment_rect.right > window_rect.left  && 
  segment_rect.left <  window_rect.right &&
  segment_rect.top > window_rect.bottom &&
  segment_rect.bottom <  window_rect.top

I'd be inclined to do this before any other tests since if it shows there is no possibility of intersection you don't need to do anything else at all and a good compiler will optimise this test well.

Now maybe we can do the test for the centre of the window being near enough the segment since if that fails we know that there is no intersection with the actual segment. However, I suspect this test won't exclude many segments from further consideration, and it might not be very worthwhile.
In fact if you do it it might be best to do it first.

Next I'd check if either end point was in the rectangle like this:

Code:

contains_end_point = 
  window_rect.left <= end_point[0].x && 
  window_rect.right > end_point[0].x &&
  window_rect.bottom <= end_point[0].y && 
  window_rect.top > end_point[0].y

and a similar test for the other end point if the first one is not inside the window.
Now we have decided whether the segment intersects the window except in the case where the rectangles overlap and both end points are outside the window. In this case either the segment rectangle contains parts of two opposite sides in which case there is again an intersection, or it contains a corner, in which case we are not sure.

the test

Code:

segment_must_intersect = 
  segment_rect.left < window_rect.left &&
  segment_rect.right > window_rect.right ||
  segment_rect.bottom < window_rect.bottom &&
  segment_rect.top > window_rect.top

deals with the first of the two cases. If this is true the segment intersects the window.
Now if we are still in doubt the line is either wholly outside the window rectangle (but perhaps quite close if we did the centre distance test) or cuts through two adjacent sides, so that at one corner of the window is on the opposite side of the line to the others.

So finally we do this test, assuming line is ax+by+c=0

Code:

side = a*window_rect.left + b*window_rect.bottom + c
if (side < 0)
  intersect = 
    a*window_rect.right + b*window_rect.bottom +c >= 0 ||
    a*window_rect.right + b*window_rect.top +c >= 0 ||
    a*window_rect.left + b*window_rect.top +c >= 0
else
  intersect = 
     a*window_rect.right + b*window_rect.bottom +c <= 0 ||
     a*window_rect.right + b*window_rect.top +c <= 0 ||
     a*window_rect.left + b*window_rect.top +c <= 0

With these tests we hope most of the time only to do a few comparisons. Even if we have to do the final set of tests we can hope to be lucky and find that we only have to calculate the distance of only two or three of the window corners from the line.

I can't guarantee this will be faster than what you are doing, but it might be worth trying.