1
\$\begingroup\$

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?

Something like this

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Is the input polygon guaranteed to lay on a plane? \$\endgroup\$
    – danijar
    Mar 23, 2013 at 19:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Exilyth
    Mar 23, 2013 at 20:01
  • \$\begingroup\$ @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. \$\endgroup\$
    – RobCurr
    Mar 23, 2013 at 20:26
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Nathan Reed
    Mar 23, 2013 at 21:27
  • 1
    \$\begingroup\$ Where's the fun in that? \$\endgroup\$
    – RobCurr
    Mar 24, 2013 at 7:39

1 Answer 1

Reset to default
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Fredrik Johansson
    Mar 24, 2013 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .