# point outside a non-convex shape

I have a non-convex shape (object) in black on the figure on the link. At the beginning, All red points are outside the shape. Next, I apply a random transformation on some points. This create a new shape (yellow).

What I want is to fill the outside of the shape with a specific color but because of the transformation, some red points are now inside the shape. I would like to know how to find a correct red point, i.e outside the shape to apply the filling algorithm.

Here is the link on the image. http://postimage.org/image/sbjmgi1tr/

-
What if all the red points end up inside the shape? – Rahul Sep 6 '12 at 7:49
@RahulNarain this is problematic but in real case it should not happend. If I can find something for all cases except this one, It would be ok. – Seltymar Sep 6 '12 at 7:55
I'm not sure I understand what you are asking. Do you just want to classify the red points as inside or outside the region? – Daryl Sep 6 '12 at 10:32
Can't you just try each of the red points one by one, check whether it is outside the shape, and pick the first one that is? – Rahul Sep 6 '12 at 20:54
@RahulNarain Maybe, it's not so difficult. I was thinking wrongly. At the moment, I count the number of time an horizontal line, from a red point to the left side of the image, cross the shape. I have now to deal with some special case when the line cross a corner of the shape, when the image does not cover all the shape... – Seltymar Sep 7 '12 at 0:11

## 1 Answer

In that case, use a point in polygon algorithm. Then you can test each point if it is in your new polygon or not.

-