# Generate inner polygon from a parent polygon

I want to produce a polygon inside an arbitrary polygon. The inner polygon shall be distanced from the outer polygon with a fixed distance, d. I will use the inner polygon as a border for player movements, and the player radius will be 2 * d.

If the outer polygon contains sections with width less than 2 * d the inner polygon will not fill that space, or any space on the other side of that passage.

Keeping the distance to the outer polygon means that the inner polygon will form circles, by a number of segments, around sharp vertexes.

How do I generate the red polygon? • Is the input polygon guaranteed to lay on a plane? – danijar Mar 23 '13 at 19:50
• Looks like en.wikipedia.org/wiki/Erosion_%28morphology%29. No ideas for code, but scaling down and cutting off parts with a thickness below a certain treshhold might be useable as an approximation. – Exilyth Mar 23 '13 at 20:01
• @sarahm it looks like your article is referring to image morphology rather than dealing with vertices of a polygon. I would approach this in 2 steps. Step 1) determine the loops, essentially find points that are less than 2d apart and split the polygon into 2 at that place. Step 2) determine the centroid of each resulting polygon by averaging all points together and then create a vector between each point and the centroid, moving it along the vector d distance. – RobCurr Mar 23 '13 at 20:26
• This question has been asked before on StackOverflow. Note: it is not at all simple to do this type of operation robustly, so the right answer is usually to use someone else's library that has already solved the problem. – Nathan Reed Mar 23 '13 at 21:27
• Where's the fun in that? – RobCurr Mar 24 '13 at 7:39

## 1 Answer

Note, that your "inner polygon" is not a polygon (!!!) (because, as you said, it contains parts of circles).

If you just want your object to move inside polygon, keeping the distance from edges, I recommend you to compute the distance between your inner point and the closest point on polygon edges, then compare, whether is that distance bigger or smaller than your d, to check the collision.

BTW. here is the Javascript library & demo of finding closest point on polygon edge: http://polyk.ivank.net/?p=demos&d=closestedge

• I plan to use the inner polygon as input to an A* path finding algorithm, so I guess I need it. As Nathan Reed states, the question has been answered before. I will look at that answer. – Fredrik Johansson Mar 24 '13 at 17:47