+3  A: 

Each line should split the plane to "inside" and "outline"; you can find this out using the usual inner-product method.

Move all lines outward by some distance.

Consider all pair of neighbor lines (lines, not line segment), find the intersection. These are the new vertex.

Cleanup the new vertex by removing any intersecting parts. -- we have a few case here

(a) Case 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by one, you got this:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 and 4 overlap.. if you see this, you remove this point and all points in between.

(b) case 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by two, you got this:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

to resolve this, for each segment of line, you have to check if it overlap with latter segments.

(c) case 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

expend by 1. this is a more general case for case 1.

(d) case 4

same as case3, but expend by two.

Actually, if you can handle case 4. All other cases are just special case of it with some line or vertex overlapping.

To do case 4, you keep a stack of vertex.. you push when you find lines overlapping with latter line, pop it when you get the latter line. -- just like what you do in convex-hull.

J-16 SDiZ
This looks like a half-plane intersection algorithm?
Igor Brejc
+2  A: 

Sounds to me like what you want is:

  • Starting at a vertex, face anti-clockwise along an adjacent edge.
  • Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one.
  • Repeat for all edges.
  • Find the intersections of the new edges to get the new vertices.
  • Detect if you've become a crossed polynomial and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.

The resulting polygon lies at the required distance from the old polygon "far enough" from the vertices. Near a vertex, the set of points at distance d from the old polygon is, as you say, not a polygon, so the requirement as stated cannot be fulfilled.

I don't know if this algorithm has a name, example code on the web, or a fiendish optimisation, but I think it describes what you want.

Steve Jessop
"detect if you've become a crossed polynomial" is the hard part :)
J-16 SDiZ
Darn straight. Until you eventually become convex, after which it's not such an issue any more :-)
Steve Jessop
This is an approach I was thinking about myself - but I couldn't find anything in the usual algorithms places on the net.
Igor Brejc
+3  A: 

Here is an alternative solution, see if you like this better.

  1. Do a triangulation, it don't have to be delaunay -- any triangulation would do.

  2. Inflate each triangle -- this should be trivial. if you store the triangle in the anti-clockwise order, just move the lines to right-hand-side and do intersection.

  3. Merge them using a modified Weiler-Atherton clipping algorithm

J-16 SDiZ
And (optionally) remember the triangulation for next time. Nice.
Steve Jessop
how do you inflate the triangles exactly? Does your output depend on the triangulation? With this approach can you handle the case when you shrink the polygon?
balint.miklos
Are you sure this approach really works for polygon inflation? What happens when the concave parts of the polygon are inflated to such extent that some vertices have to be eliminated. The thing is: when you look what happens to triangles after poly. inflation, the triangles are not inflated, instead they are distorted.
Igor Brejc
Igor: Weiler-Atherton clipping algorithm can handle the "some vertices have to be eliminated" case correctly;
J-16 SDiZ
@balint: inflate an triangle is trivial: if you store the vertrex in normal order, the right-hand-side is always "outward". Just treat those line segment as lines, move them outward, and find the interaction -- they are the new vertex. For the triangulation itself, on a second thought, delaunay triangulation may give better result.
J-16 SDiZ
Note: If you implement everything from the ground up, this method is more complex then the another method i have proposal. However, if you have a good computational geometry library, both (1) and (3) are standard algorithm and should be readily available.
J-16 SDiZ
I think this approach can easily give bad results. Even for a simple example as quad triangulated using a diagonal. For the two enlarged triangles you get: http://img200.imageshack.us/img200/2640/counterm.png and their union is just not what you are looking for. I don't see how this method is useful.
balint.miklos
+10  A: 
balint.miklos
Thanks for the tip! This will give me new avenues of googling around :)
Igor Brejc
+2  A: 

Hi,

I wrote some blog posts on my experiences of trying to implement the straight skeleton algorithm for precicely this case (polygon expansion / reduction through offsetting). At the time I had two blogs. It may be helpful to read about some of the problems I encountered:

  1. http://max-on-graphics.blogspot.com/2008/06/straight-skeleton-madness-plea-for-help.html

Regards,

Max

Max Palmer
Max, any chance your code gets open-sourced? :)
Igor Brejc
No plans at present I'm afraid.
Max Palmer
A: 

here is a demo for polygon offset in C# winform. http://www.cppblog.com/aqazero/archive/2010/09/09/126241.html

brent
Is it possible to get the source code?
Zenya
Looks nice. The source code would help :)
Igor Brejc
the demo is updated: http://www.cppblog.com/aqazero/archive/2010/09/09/126241.html Sorry the source code could not be provided.
brent