2
$\begingroup$

I need to invent an algorithm for determining if a figure is inside another figure. Until now this was done using only straight lines (circles were replaced by a list of straight lines). In that case the following algorithm was used:

For every point (x,y) of figure1, create a straight half-line from (-$\infty$,y) to (x,y) and calculate the number of intersections of that line with figure2. In case the number of intersections is even, then the point is located outside of figure2, in case the number of intersections is odd, then the point is located inside of figure2.

Obviously this algorithm is only applicable when both figure1 and figure2 are composed out of straight lines. Once you are dealing with arcs (pieces of circles) then the situation becomes more difficult, as you can see in following image:

enter image description here

Figure1 is composed out of the points ABC, while figure2 is composed out of the points DEFGH, and as you can see, the fact whether or not figure1 is inside of figure2 depends on the centre of the coloured arc: - in case the center is the point E, then figure1 is inside figure2. - in case the center is the point I, then figure1 is not inside figure2.

Does anybody have any ideas on how to implement this algorithm? (any idea, even not complete, is welcome)

Thanks

$\endgroup$
0
1
$\begingroup$

I think that in the general case you need to consider Boolean operations on conic polygons.

Here are two papers on this subject that Google found:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.