1

How does one determine whether one or more points lie within an area whose boundary is given? For instance, in the following figure, three blue points lie within the area bounded in red, two red points lie within the area bounded in blue, and there are three points - two blue and one red - which do not lie within either of the indicated areas.

enter image description here

Patrick87
  • 27,682
  • 3
  • 38
  • 73
Topol-M
  • 83
  • 1
  • 7

3 Answers3

2

look here
It's C, but code/algorithm can be converted to C# with ease.

atoMerz
  • 7,534
  • 16
  • 61
  • 101
2

Draw a line from the point. check if it crosses any of the region edges and what side of the line it is.
If it crosses them odd number of times on each side it is in the region.

Daniel
  • 30,896
  • 18
  • 85
  • 139
  • Not really true in case of concave surfaces. If you immagine a point out of the polygon but inside a "cave" , drawed line will cross polygon but continue to be out of it – Tigran Aug 18 '11 at 15:45
  • @Tigran, but again, it will first cross the cave wall, and then cross the polygon wall again on the way out which makes it 2 crosses which is not an odd number. – Daniel Aug 18 '11 at 15:48
  • You can immagine that that immaginary line will cross 2 times on one side and 1 time exactly on vertex of the polygon. Just touching it... – Tigran Aug 18 '11 at 15:50
  • @Tigran, if its touching a vertex if will cross both lines that make that vertex. for that there should be a special case that is not too hard to think of. – Daniel Aug 18 '11 at 15:56
1

I don't know the "algorithm" to do this, but in C# (.NET framework) you could do it with Region.IsVisible method of the class Region. You can create a custom region using GraphicPath constructor. A GraphicPath itself could be constructed by a Point array.

Ehsan88
  • 3,569
  • 5
  • 29
  • 52