In my game I want users to be able to draw arbitrary 2D shapes of any length around game objects. The shapes must be closed and drawn with a single stroke that does not overlap.

For example:

enter image description here

I want to detect the presence of any game object in the green areas above.

I know how to detect whether a point is within a given polygon, but how do I tell where the polygons (green areas) are from just the points in the line?

  • 1
    \$\begingroup\$ Some special flood fill I would guess. Interesting question. \$\endgroup\$
    – House
    Aug 9, 2013 at 5:53
  • \$\begingroup\$ Just to disambiguate that top-right case: there are actually two ways to draw that shape, one of which involves overlapping of lines (and is thus invalid; the stroke is cancelled when the lines overlap), one of which doesn't (and is thus perfectly valid). \$\endgroup\$ Aug 9, 2013 at 7:07
  • 2
    \$\begingroup\$ Can you record the stroke as it is drawn by the user, or do you only have the image of the stroke? If the former, why can't you just do the point in polygon test? \$\endgroup\$
    – GuyRT
    Aug 9, 2013 at 10:54
  • \$\begingroup\$ It's the former. The problem with the point-in-polygon test (in my mind, at least) is that it considers the points it gets as a representation of a closed polygon. Whereas the polygon may not be closed, as in the top-right and bottom-left pictures. \$\endgroup\$ Aug 9, 2013 at 12:55

1 Answer 1


First, define what is 'neighbour'. In your case, pixels 'A' and 'B' are connected if abs(A.x - B.x) <= 1 && abs(A.y - B.y) <= 1. This is the rule that Microsoft Paint uses when doing flood fill.

Your Valid and Invalid-shape isn't closed can be easily detected using a Flood fill. A flood fill marks a non-empty pixel green. It then continues the flood fill with its neighbours, eventually filling the full shape. To do this, pick a random pixel, then find an empty neighbour. Do a flood fill starting from this neighbour with a unique color. Re-iterate over all pixels to ensure you have filled all of the areas. (Picture 2)

Now find out which colors touch the edges of your picture. These colors should be erased, as they do not constitute a closed space. (Picture 3)

Now, you want to detect lines that do not contribute to a filled area. To do this, mark all black pixel neighbours of a filled pixel in BLUE. (Picture 4)

All lines which are still black do not contribute to the edges of an area. They are invalid. (Picture 5).

Explanation of algorithm

Detecting your 'Valid, within a single stroke' requires a small extra step. For every invalid pixel, start a flood fill. If, during your flood fill, you touch the edges of two different areas, this line actually connects two areas and it is therefore part of your valid image.

You need to decide whether this algorithm is good enough. For example, drawing a thick edge by going back a few pixels will be marked as 'invalid', as this extra 'blob of ink' does not connect two areas. You could improve this algorithm by adding a 'time' dimension: you give a list of pixels in the order in which they were drawn.

Finally, think about user experience. Drawing a 'V' shape will most likely result in >2 pixel neighbours for a new pixel drawn in the tip of the V. Can you algorithm that detects overlapping edges cope with that?

  • \$\begingroup\$ Interesting approach, and it's plain to see that it works. Thanks for taking the time to provide a detailed explanation. An issue with it though is that the runtime of the flood fill increases quadratically with the size of the canvas (or at the very least, the size of the rectangle that the drawing occupies on it), and I was planning to have a huge canvas world that the user could scroll around, with very frequent updates of the valid areas - so I was hoping (perhaps naively) to solve this problem geometrically, heh. But I'll definitely use your algorithm if I can't find a faster approach! \$\endgroup\$ Aug 9, 2013 at 13:17
  • 1
    \$\begingroup\$ Ways to optimize this: find min/max X/Y coordinates of a drawn line and crop the image. You could also use a heuristic (e.g. manhattan distance) to prioritise a flood fill towards the other edges. This would do a flood fill just touching the edges (which is enough for you to know if the figure is closed or not) \$\endgroup\$
    – parasietje
    Aug 14, 2013 at 15:18

You must log in to answer this question.

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