5

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
  • 608
  • 2
  • 9
  • 19
  • 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

2 Answers2

9

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))

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

P' = P + l * bis

Added: python implementation here

MBo
  • 72,080
  • 5
  • 47
  • 77
  • 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. – Claudio 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. – Claudio 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
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
  • 3,812
  • 1
  • 7
  • 20
  • 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