I am developing a CAD software which has line,circle and arc objects in the drawing. I need to select the objects by dragging a window. Whichever objects come inside the window should be selected.
I can determine if a line or circle is inside the window or not. But I cannot determine how to detect if an arc lies inside the window. Can anyone please explain me the logic for the arc case?
If your curve is composed of Bezier segments you should be able to attain a bound as the union of their convex hulls.
Hi mukul
Do you mean circular arc (or elliptical arc)? If so, read on. I assume 2d here, but easily ported to 3d geometries.
If you already have the code to select full circle, you could modify/extend that to select a part of the circle - ie, a circular arc.
Special cases first:
If the full circle of the arc is inside the selection window, the your arc is selected. If the start or end point of the arc are inside the selection window, then the arc is selected as well.
The general case:
It’ll help a lot if you have some sort of parameterisation for the circle. Any point on the circle can be assigned a unique parameter, typically this is angle, and the full circle run from 0 to 2pi, but this could be something different, depending on how you do your bookkeeping internally. The selection of the point that correcponds to 0 is of no great importance, as long as you have one. For circular arcs, you could set the start point to be at parameter 0. In general the circular arc has start-end parameters, which correspond to the start and end point.
Find the intersections between the selection window and the full circle. In general these would be either 0, 1, 2, 3, 4. 1 means you only have a touching point, 2 means you have 2 clear intersections (ie, the circle goes from outside the window to inside), 3 means you have 2 intersection and a touching point, and 4 means you have 4 intersections. These intersection split your full circle into segments, say Si.
Find the segments of the full circle that are inside the selection window. You must to have a point-inside-selection-window test already. The brute-force way is to get an interior point from each segment Si and do a point-inside-selection-window
test. The smart way is to do this for only one segment, say its inside. Then the next segment will be still be inside if the intersection is actually a touching, other-wise it’ll be outside.
When you have the Si that are inside the selection window, have to test if any of you arc overlaps any of the inside Si’s.
Simple, eh? (not!) I think it’ll look much simpler in math or code, the actual idea is straightfoward but looks tricky in words.
If this is a UI feature, then you shouldn’t have to worry too much about tolerances, but it helps to have a strategy to deal with those.
The same approach should help for elliptic arcs - and actually any type of curve.
I hope this gives you any idea.
Madmortigan
Hi again
Quick and dirty version:
You can also generate points on your arc and test each one of them for containment in the selection window. If it’s a UI selection feature and you generate enough points (say, 50 for a full circle), the user won’t notice she’s actually selecting point sets. Actually, having said that, if you’re doing a CAD system, you may want more points here. To improve this, you can generate the line segments for these points (thus approximating the arc with a polyline, which is what you’re doing when you draw this anyway), and then you can use the selection routine for line segments, you said you already have in place.
Speed shouldn’t be a problem, given a reasonable implementation of your point-inside-window routine on a pc.
Hope this helps more.
madm