Polygons with lines and arcs

Polygons with lines and arcs

Post by Hossein Sharif » Sun, 01 Oct 2000 04:00:00



Hello,

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?

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.  

Thanks,

--
Hossein Sharifi

 
 
 

Polygons with lines and arcs

Post by Dave Eberl » Thu, 05 Oct 2000 13:40:37



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

 
 
 

Polygons with lines and arcs

Post by Fernando Cacciol » Thu, 05 Oct 2000 04:00:00


Hello Hossein,

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?

I've been working with exactly that kind of polygons for some years now, but
I'v never seen any 'general' book or reference.

The book:

Farin, G.
Curves and Surfaces for Computer Aided Geometric Design
Academic Press
1988

provides all the basic information for dealing with the polygon pieces
(segments or arcs).

You can consult the EXCELENT online math encyclopedia at:
www.mathworld.wolfram.com for particular math issues.

Look at the Dave's site for implementation of the fundamental tools, as he
already told you.

Also, note this:

Most straight-edge polygon algorithms, particularly the sweepline
algorithms, relies on the fact that a straight line is monotonous in either
X or Y direction. This is not so for circular arcs, but you can always
'split' an arc into quadrants -or perhaps octants- in which case each piece
is monotonous in any direction just like a segment. This can introduce
'tiny' arcs which might be problems in their own right, but otherwise, this
'normalized' curvilinear polygon might be easier to treat.

For a good reference for the particular boolean operations problem (for
straight-edge polygons), contact:

Klaas. Holwerda.

(I've downloaded his work but I can't find his site, all there is in a
readme.txt is the above contact info).

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 call this 'curvilinear polygon'.

P.S: If you have specific question you are welcome to ask me directly.
Perhaps I'm able to answer you.

--
Fernando Cacciola
Sierra s.r.l.

www.gosierra.com

 
 
 

Polygons with lines and arcs

Post by klaas holwerd » Sat, 07 Oct 2000 04:00:00


This is my site:

http://www.xs4all.nl/~kholwerd/bool.html

BTW the approach i took for  "arcpolygons", which my program is able to
handle/display,
i first convert to normal polygons before doing a boolean operation.
After that i have a arc recognition routine, the find back arc shaped parts.
That means if a number of segments can be represented by an arc within a certain
accuracy it will replace
those segments. This approach was enough for me.

I do think the boolean algorithm i have based on graphs could be made to handle
arc segments also.
As long as they are continues in x, so split them if not.
But it will certainly slow down things, when trying to find intersection.

Klaas

> Klaas. Holwerda.

> (I've downloaded his work but I can't find his site, all there is in a
> readme.txt is the above contact info).

 
 
 

Polygons with lines and arcs

Post by Fernando Cacciol » Tue, 10 Oct 2000 04:00:00




Quote:

> This is my site:

> http://www.xs4all.nl/~kholwerd/bool.html

Thanks.

Quote:> BTW the approach i took for  "arcpolygons", which my program is able to
> handle/display,
> i first convert to normal polygons before doing a boolean operation.
> After that i have a arc recognition routine, the find back arc shaped
parts.
> That means if a number of segments can be represented by an arc within a
certain
> accuracy it will replace
> those segments. This approach was enough for me.

> I do think the boolean algorithm i have based on graphs could be made to
handle
> arc segments also.
> As long as they are continues in x, so split them if not.

I agree.

Quote:> But it will certainly slow down things, when trying to find intersection.

I'm not sure wheter decomposing arcs to segments and then back to arcs isn't
even slower. Anyway, as you said your graph approach should work for arcs
properly arranged.

Regards,

Fernando Cacciola.