Quote:> I am trying to write some routines to clip and crop polygons. The problem

> is that the polygons are composed of both arcs and line segments. All of

> the books and web sites that I have seen only discuss polygons that are

> exclusively comprised of line segments. Does anyone know if there is a

> publication that discusses the type of polygon I'm working with?

You can always use O(N^2) algorithms, just as for the simple

implementations of Boolean operations on polygons. The faster

algorithms for polygons use sweep methods to reduce the order

of complexity. I do not think these methods directly apply to

objects made up of line segments and circular arcs. For the sake

of naming your objects, let's call them "polyarcs". The term "arc"

will refer to "line segment" or "circular arc".

The idea is to "segment" one polyarc against another. For

each arc A of the first polyarc, split any arc B of the second

polyarc that intersects A into two arcs B0 and B1. When

the splitting is done, the second polyarc is still the union of

its individual arcs, but there will usually be many more arcs

than what you started with. Similarly, for each arc B of the

original second polyarc, split any arc A of the first polyarc

that intersects B into two arcs A0 and A1. The first polyarc

is still a union of its individual arcs, but there will usually be

many more arcs than what you started with. This process

is similar to a BSP of the plane, but now you have to consider

segment-segment, segment-arc, and arc-arc intersections.

Moreover, when you "partition" using the "circle of the arc"

(compare with the standard BSP "line of the segment"), you

partition into pieces inside the circle and outside the circle.

Once you have subdivided the polyarcs, to apply a Boolean

operation, you need to determine which arcs of the two

polyarcs belong to the Boolean result. The tagging algorithm

that is mentioned in the polysolid paper at my web site should

easily extend to this setting. If you do the tagging correctly, the

Boolean operations are simple to implement.

And you will need an implementation for finding intersections

between line segments and circular arcs. I have some code

for 2D linear-linear, linear-circular, and circular-circular

intersection code {linear = line, ray, or segment; circular =

circle, arc}. It should appear at my web site in a day or so.

Quote:> Actually, I know that technically, this structure isn't a polygon. So if

> anyone could give me the actual term for this structure, It would get me

> started in the right direction.

I am not aware of a term for this type of structure.

--

Dave Eberly

http://www.magic-software.com