Polygon offset, PROBLEM.

4100 views
Skip to first unread message

Patrik Svensson

unread,
Jun 14, 1994, 5:35:12 AM6/14/94
to
Hi,

I have a problem I need help with.

I'm offsetting a simple polygon, vertices counter clockwise.
The offset can be both positive or negativ (swelling or shrinking).
You can assume positiv offset if this makes things easier.

I do the offset just by offsetting every line segment and then
connect them togheter again.

NOW, problems arises when the offset is to large. The resulting
polygon is non-simple, it intersects itself. This results in that
I would like to remove some vertices to get several new polygons
that correctly describes the offset.

EX.


-------------
| --------- |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| -- ----- |
| | | |
---- -------

^
|
|will cause trouble when offsetting with to large offset

The narrow passage will cause the polygon to intersect itself.
The result I would like to have from this example is two polygons:


---------------
| |
| |
| ------- |
| | | |
| | | |
| | | |
| | | | Offset
| | | |
| ------- |
| |
| |
| |
---------------

This example would be quite easy to find, however you can get much
much more complex stuff and I would like an algorithm finding all the
polygons that are "valid" after the offset.

After spending a couple of days thinking of different solutions I
have some ideas but would like to hear what you all think.

The best I've come up with is to find "loops" and "loops" in "loops"
then building a tree structure of these loops and keeping the
"loops" on every second layer in the tree, don't know if this will
work (it will on simple cases) on general polygons. I know you won't
understand my description of the algorithm so if you want to know
more please email me.

Maybe you could do something like dividing the original polygon in
several convex polygons offsetting those and then try to patch all
together again?

Maybe you could find all simple polygons resulting from the offset
and the check their distance from the original polygon, if the
distance is smaller than the offset the polygon should be removed.
A simple example of this is:


......... .........
. .
. .
-------- -------- -------- . . --------
\ / \ . . /
\ / \ . . /
\ / \ .. /
\ / -> \ a.. /
\ / \. ./
\ / .\ /.
\/ . \/ .
..........
b c

The simple polygon a-b-c is a result of the offset and clearly the
distance to the original polygon is 0 (or at least smaller than the
offset distance). This polygon could safely be removed.
This might work but how do you calculate the minimum distance between
two polygons in an effectiv way? O(n) or something not O(n^2).
(Is this in the FAQ or GEMS? I'll check there).

I have written a program finding the outer boundary of a polygon and
that could be used to find the outermost polygon you get from the
offset, BUT the problem is I also need some of the "internal polygons".
The simplest example is the first example in this text, think of it
as a doughnut with a opening at the side.

Well these are my thoughts on this, please mail me your comments and
opinions on the best way to do this.

If you don't understand the problem and/or the output I'm looking
for please email me and I'll try to clarify.

If you can help me or have any ideas or references on offsetting polygons
please email me.

If there is an interest I'll sum up the answers and solutions and
post it to this group. I know many people are interested in offset
because it's vital in many industrial applicatins, for example milling
(that is why I need this).

Hope of hearing from you.

Patrik Svensson, Cadcraft AB, Sweden.
pat...@csd.uu.se

Reply all
Reply to author
Forward
0 new messages