shank_punk's blog

Draw a polygon inside another polygon
By shank_punk, history, 8 years ago, In English

I'm facing a problem while trying to write a code that'll give the vertices of the inner polygon if the Outer polygon's vertices are given along with the "setback values" of each face.

in the example above, we'll be given the outer polygon vertices and the setback values a, b, c where a = distance from face A of the outer polygon to face A' of the inner polygon, b = distance from face A of the outer polygon to face B' and so on...

What's an optimal way to find the vertices of the inner polygon?

I tried to solve it but I'm unable to find the correct vertices while the slope value is > 0.

The number of vertices will be from 1 to 100 and the area of the polygon will not exceed 10^6.

Your help will be much appreciated :)

Thank you

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry for the pic quality. I had to use MS Paint

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you just find the point on A' that is a distance of a away from A with perpendicular lines, and then find the equation of A'. After you acquire the lines of the new polygon, you do a brute force intersection check.

Or am I missing something?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry. I couldn't understand what you wrote. how do I find the equation of A'?

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I am not sure if this can handle the corner cases but here are my thoughts.

I suppose that you can compute the corresponding vertices of the inner polygon by considering the setback value of the adjacent sides. For the sake of easy trigonometry naming I will call the vertices on the figure in your post as x, y, z, in clockwise order and x is the vertice between line a and c.

If I am not mistaken, the delta of position between x and x' can be computed by a and c, as a contributes the vertical transposition while c contributes to horizontal transposition.

Therefore I propose that you can sort the vertices in the clockwise order, then compute the slope of each line, and use sine cosine ratio to compute the transposition of each vertice.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks. I didn't think of the sorting method.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do we find the sin cos ratio? If I'm not wrong we can't calculate the angle between two point.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shank_punk (previous revision, new revision, compare).

→ Reply