Consider these polygons:

Consider these polygons

For reasons of simplicity I only consider triangles or polygons with 4 vertices. These shapes are specified by the vertices, the output of the program should be modified vertices.

I am trying to find an algorithm to create a space between the polygons, the colored area depicts the space:

polygons with space

I have tried these things:

  • scaling each polygon around it's center of gravity
  • scaling the bounding box of each polygon

None of those worked.

I am thinking of an algorithm to modify the corner points of each polygon to create the equidistant space.

What would be a feasible algorithm for this problem?

  • 1
    What do you mean by "create a space"? What is the input & output of your algorithm? Is the output an image? – CaptainCodeman Jul 9 '14 at 7:12
  • @CaptainCodeman legitimate question, I edited my answer – x0r Jul 9 '14 at 7:59
  • does just plotting with a larger line weight work for you? if not why? – jk. Jul 9 '14 at 10:05
  • @jk. good idea, but unfortunately I need the line weight additionally to create a visible line. The part that is colored in the images is transparent in my program – x0r Jul 9 '14 at 10:38

Basically you just have to think about sliding edges inward and imagine where they intersect to form an interior polygon. Picture that and you'll be set.


What determines the size of the space?

I think you're focusing on the vertices when you should be focusing on the lines.

Since you've changed the shape as well as the size, it would seem to be pretty easy. Given a gap width W, slice W/2 each side of all internal lines and W away from all borders. Then revise the vertices locations to match the new borders.

  • having thought about it, your approach is the way to go, many thanks! – x0r Jul 9 '14 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.