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.

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?

share|improve this question
1  
Some special flood fill I would guess. Interesting question. –  Byte56 Aug 9 '13 at 5:53
    
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). –  user1953221 Aug 9 '13 at 7:07
2  
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? –  GuyRT Aug 9 '13 at 10:54
    
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. –  user1953221 Aug 9 '13 at 12:55
add comment

1 Answer 1

up vote 3 down vote accepted

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?

share|improve this answer
    
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! –  user1953221 Aug 9 '13 at 13:17
1  
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) –  parasietje Aug 14 '13 at 15:18
add comment

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.