Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I want to produce a polygon inside an arbitary 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

share|improve this question
    
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. –  sarahm 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
3  
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
1  
Where's the fun in that? –  RobCurr Mar 24 '13 at 7:39

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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