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:

enter image description here

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:

enter image description here

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.


1 Answer 1


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).

  • \$\begingroup\$ That algorithm helps me to find the outline - but that's just a part of the problem. I still need to extract the lines from the outline, as well as the exact pixel-position of the lines. After all, I can't do anything with lines which are as thick as a tile itself. \$\endgroup\$
    – TravisG
    Commented Jul 18, 2011 at 9:56
  • \$\begingroup\$ Based on the movement of the marching square, you should be able to tell if the edge is left, right, bottom or top. An alternative would be a radial sweep algorithm, where you start at a corner point and check against the edges of the "tiles" \$\endgroup\$
    – bummzack
    Commented Jul 18, 2011 at 11:44

You must log in to answer this question.

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