2
$\begingroup$

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/

  • 0
    What if all the red points end up inside the shape?2012-09-06
  • 0
    @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.2012-09-06
  • 0
    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?2012-09-06
  • 0
    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?2012-09-06
  • 0
    @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...2012-09-07
  • 0
    @Daryl You're right. I just want to do that. I found a way by counting the number of time an horizontal line cross the shape. But this method has a lot of exceptions I have to deal with.2012-09-07

1 Answers 1

0

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