1

I have a simple, not self-intersecting polygonal chain and want to create a second polygonal chain with parallels with fixed distance.

I think this topic is called polygon offsetting or buffering (this finds for example An algorithm for inflating/deflating (offsetting, buffering) polygons)

MATLAB has bufferm and polybuffer but none of them is implemented in GNU Octave.

I've started my own implementation:

close all
rotm = @(a) [cos(a) -sin(a); sin(a) cos(a)];
h = 3; # distance from existing polygon
p = [1 5 18.7 21 34 34;
     36.1 36.1 42.1 22.5 16.0 13];
dp = diff(p, [], 2);
a = atan2 (dp (2, :), dp(1, :)); 
da = diff (a);
horiz = abs (da) < 16 * eps;
f = 2 * h./sin(da).*sin(da/2);
f(horiz) = h;
f = [h f h];
r = a(1:end-1) + diff(a)/2;
r = pi/2 + [a(1) r a(end)];
p2 = zeros(size(p));

for k=1:columns(p)
  p2(:,k) = p(:,k) + rotm(r(k)) * [f(k); 0];
  line ([p(1, k);p2(1,k)], [p(2, k);p2(2,k)], "color", "magenta");
endfor

line (p(1, :), p(2, :), "color", "green");
line (p2(1, :), p2(2, :), "color", "red");
axis equal
grid on

generated plot

but at that point I really think there might be an easier way to do this.

Is there an easier way or some already implemented function which might help? (btw, I haven't vectorized the code yet)

Andy
  • 7,931
  • 4
  • 25
  • 45
  • Are you willing to implement it in terms of a signed distance transform? or is that overkill? if yes, then the solution becomes a simple +/- contour over the distance transform. Or you can presumably achieve similar results using morphological dilation and then contouring at 0.5 to get the periphery back. Both the above involve discrete positions of course. – Tasos Papastylianou Jul 24 '19 at 11:21

1 Answers1

0

This is not as simple as it may initallly seem. For example, offsetting complex polygons involves collisions between the offsets:

CGAL
Image from CGAL manual, Chap.16: 2D Straight Skeleton and Polygon Offsetting
Joseph O'Rourke
  • 4,346
  • 16
  • 25