Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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

share|cite|improve this answer

Your Answer


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.