1

I am trying to implement an algorithm to offset complex polygons following this paper, however I am stuck when trying to compute the winding number for the different sub-polygons of the polygon. (See 4.1 for a description of the algorithm as well as figures 11.(c) and 12.(c)).

#Edit: Some more details on the algorithm in question.
The goal is to offset (i.e. inflate/deflate) a polygon (including non-convex ones) by a certain value. The rough procedure is:

  1. Offset each edge of the polygon towards the normal of the edge by the offset value.
  2. Join the offset edges based on some rules. We now have a complex polygon which may have intersections.
  3. That's the stage I am stuck with: the intersections in the polygon create smaller polygons inside the big one, I need to find those smaller polygons and calculate the winding number for them, probably by finding a point inside and calculating the winding number for this point.
  4. To obtain the inflated polygon, join the sub-polygons with a positive winding number.

#endEdit

I guess I could find cycles within the graph to obtain the different polygons, then implement an algorithm to find a point inside a concave polygon, but this is quite complex, and the fact that they do not detail this more in the paper makes me believe I am missing something relatively obvious.

Any idea would be much appreciated, thanks.

GGberry
  • 929
  • 5
  • 21
Leherenn
  • 520
  • 5
  • 16
  • 1) You should explain the problem in the question, rather than rely on a link to a document on another site. 2) The algorithm seems to involve finding intersections between various line segments and arcs, which is tedious but straightforward. After that I think it would be simpler to calculate the area of each simple polygon and reject the negative ones, rather than worry about winding numbers. – Beta Nov 07 '16 at 21:38
  • @Beta I have added a small explanation of the algorithm, sorry for that. However it is not clear how to obtain the simple polygons based on the intersections. Unless I am missing something, this is a non-trivial problem that is equivalent to finding the cycles in the graph. – Leherenn Nov 08 '16 at 07:52
  • Why do you not take a straight skeleton for this. It looks like you want mitered offsets of the polygon. The paper that you refer to uses an approach that will yield many special cases in real world applications. Also, for the straight skeleton there are already quit a few efficient implementation. – gue Nov 08 '16 at 08:05
  • @Leherenn see [How can I create an internal spiral for a polygon?](http://stackoverflow.com/a/31013424/2521214) may be it will make it a bit more clear. (Especially the sublinks) – Spektre Nov 08 '16 at 09:02
  • 1
    @gue I mostly wanted to implement it myself, and it looked much easier than the methods using skeletons. Of course I could use a library like CGAL or Clipper, but that's not really fun. Do you have examples of those specials cases that might happen? Spektre: Thanks for the links. – Leherenn Nov 08 '16 at 09:45
  • @Leherenn A couple of years later - did you even figure this out? – Snail May 07 '20 at 15:34
  • 1
    @Snail In a sense. I loaded the complex polygon in a DCEL data structure. From there, finding the internal faces is trivial. Creating the DCEL is not trivial though. Once you have your polygons, take 3 consecutive vertices and compute the center of gravity, it should always be inside the polygon. – Leherenn May 08 '20 at 07:40

1 Answers1

0

I am stuck when trying to compute the winding number for the different sub-polygons

The idea of "Polygon Offsetting by Computing Winding Numbers" article is to prepare special self-intersecting curve for an input polygon, this curve is given to OpenGL Utility library (GLU) tessellator, which will produce offset result (in GLU BOUNDARY ONLY mode) by computing winding numbers inside, so you do not need to implement their computation by yourself unless you want to rewrite GLU tessellator.

See 4.1 for a description of the algorithm as well as figures 11.(c) and 12.(c)

Figure 11.c:

Inner offset

Here input polygon is dashed blue, red is prepared special curve given to GLU tessellator and the boundary of grey region (+1) is expected inner offset. This boundary is returned from the tessellator with the winding rule GLU TESS WINDING POSITIVE.

Figure 12.c:

Outer offset

Here we see the same input polygon in dashed blue, red is prepared special curve given to GLU tessellator and the boundary of united grey regions (+1) and (+2) is expected outer offset.

Fedor
  • 17,146
  • 13
  • 40
  • 131