8

I have a list of point2D that makes a closed polygon. Now I want to create another set of 2D points by offsetting the polygon given an option inside or outside and an offset value. How can I do it? enter image description here

N.T.C
  • 658
  • 2
  • 9
  • 20
  • 4
    Possible duplicate of [An algorithm for inflating/deflating (offsetting, buffering) polygons](https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons) – Maurice Perry Jan 04 '19 at 06:24
  • You want to get either inner or outer "parallel" sides, don't you? – Muhammad Magdi Jan 04 '19 at 09:02
  • Note that a lot of discussion here is about how to compute offset vertices, but that's actually the easy part. Short edges offset to the inside can result in a polygon with edge crossings. More processing is needed to get a simple polygon. Same with sharp concave angles and outside offsets. – Gene Aug 18 '22 at 02:14

2 Answers2

12

enter image description here

For every polygon vertex calculate outer bisector vector as sum of normalized normals na and nb of two neighbor edges), then normalize it

 bis = na + nb 
 bis = bis / Length(bis)

Then find needed length of bisector to provide offset distance as

 l = d / Sqrt((1 + dotproduct(na,nb))/2)

(derived from l=d/cos(fi/2) and half-angle cosine formula)

And get offset polygon vertex (use minus for inner offset!):

P' = P + l * bis

Added: python implementation here

MBo
  • 77,366
  • 5
  • 53
  • 86
  • May I ask if it is correct to do something slightly different? Instead of choosing na and nb as normals to the neighbor edges, I set na and nb as the normalized vectors pointing to the previous and next vertices. Then l = d / Sqrt(1 - dotproduct(na,nb)) instead of + dotproduct. Sperimentally it seems to be correct, but I just guessed. – user6369958 Oct 24 '21 at 16:37
  • 1
    @Claudio It might cause errors in case of three neighbor collinear vertices. If it is impossible in your case - you can use side directions (forward and backward for two neigbor sides) . Note that normal vectors are very simple - for direction vector `dx,dy` (left) normal is `-dy, dx` – MBo Oct 24 '21 at 16:42
  • I'm offsetting polygons with coplanar vertices but in 3d space, so the normal isn't easy as `-dy, dx`, but obviously achievable. Thanks for your hint. – user6369958 Oct 24 '21 at 18:23
  • 1
    Yes, having plane normal N, we can find edge normals as `in_edge_dir x N` and `N x out_edge_dir`, but definitely spend more calculations. – MBo Oct 25 '21 at 04:00
  • I'm having a really hard time understanding how the derivation is for L (l). It almost feels like its a ratio. Also when I use the source code and lets say I have a unit cube (0,0), (1,0), (1,1), (0,1) = Counter clockwise and expand by d=1. I would expect my cube to be (-1,1), (2,-1), (2,2), (-1,2). But i'm getting a 1/sqrt(2) for some of the corners. Any help is appreciated. – gimp3695 Aug 18 '22 at 01:12
  • Thank you. I have been bashing my head wondering why I can't figure it out. From what I understand is the l and d make a triangle. Where l = hypotonous and d is the adjacent side. So wouldn't it be l = d * cos (fi/2) – gimp3695 Aug 18 '22 at 01:50
  • Thank you for being so responsive. Just for my slow brain. I always though sin (theta) = (opposite/hypotenuse). Where cosine(theta) = (adjacent/hypotenuse). I figured that looking at the diagram l = hypotenuse, d = adjancent in a right angle triangle. Am I wrong? – gimp3695 Aug 18 '22 at 02:01
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/247354/discussion-between-gimp3695-and-mbo). – gimp3695 Aug 18 '22 at 02:02
  • OK, now formula is corrected (`/2` added) – MBo Aug 18 '22 at 02:15
  • You can optimize this a bit. If you formulate it like P' = P + r * (na + X * ) solving for X, you get X = tan(fi/2) = sin(fi) / (1 + cos(fi)), where sin(fi) = (na cross nb).z and cos(fi) = (na dot nb). Then you don't have to normalize the bisector or compute sqrt() – kylefinn Aug 30 '22 at 23:06
  • @kylefinn Thanks for the note, will explore it later – MBo Aug 31 '22 at 04:26
3

You need to work with dircetion to be able to define what is outside/inside. Better is to work with to the left/right of the arrow (vector).

In my example the offset is to the right of the vector, now you need to calculate all intersections of the red lines to define the new start-end points of the lines.

Example: P0 = (5,2) & P1 = (2, 1.7)

V1 = -3, -0.3. Rotating clock wise 90deg gives us vector -0.3, 3 (a,b) -> (b, -a)

Divide the vector by 3 (thats about the distance in the drawing) gives us (-0.1, 1) ofsetting point P0 by the vector gives P0' (5,2) - v(-0.1,1) = (4.9, 3)

enter image description here

Aldert
  • 4,209
  • 1
  • 9
  • 23
  • I know that a vector v2 is on the right of v1 if the cross product v2 × v1 is positive, but would be 0 if they are parallel. How to offset a vector to its right? – N.T.C Jan 04 '19 at 09:20
  • Thats smart. I have also realized that vector P1P1' divides angle P0P1P2 into 2 equal angles. Thus vector P1P1' can be determined. Also the distance P1P1' can be determined. Thus P1' can be found, without having to determining intersection between new lines. – N.T.C Jan 04 '19 at 09:59
  • Hope I helped you further, please mark as answered when you are happy. – Aldert Jan 04 '19 at 10:05