I've got a 2D-map, largely consisting of rectangular tiles, but with some none-rectangular objects mixed in as well (tilted lines on corners for example).
Take this image as an example:
I now need all the largest possible (straight) lines around the two bodies inside that map. There are no additional required attributes to the lines.
In this image, I've marked the lines that I'm trying to find, each one with a different color to make sure there are no confusions:
It's important however, that the algorithm doesn't produce lines inside those two objects, as it would be a waste of resources.
Are there algorithms suited for that or will I have to research an algorithm myself?
By the way, the algorithm will run at loading-time of the game, so it doesn't need to be optimized for runtime-speed. Also, principally, an algorithm that is just able to find the lines around bodies which consist only of square or rectangular tiles would suffice as well.
Answer
If you're dealing with discrete positions (eg. a tile-map or pixel based map), then an easy way to find the contours would be the Marching Squares algorithm (Wikipedia).
No comments:
Post a Comment