finding if a point is in a polygon

[kettch]

I know that the rectangle object has a "contains" method, but what would be the best way to find if a given point is inside the boundaries of a series of points fed into the GraphicsPath.AddLines() method.

One method I had suggested to me was to take that point and draw a line starting there and going along the x-axis to an arbitrary value that is definetely father than any point in the shape. If that line intersects any other line 0 or 2 times then it is outside the shape. If it intersects 1 time then it is inside the shape. Follow? My dilemma, if this is the best way to do what I want to do, is to figure out how to determine if a line intersects any other lines.


Let me know if any of this needs clarifying.

Thanks in advance!

 

[NeilTrain]

Your on the right track, but the number of times your imaginary line intersects lines of the polygon cannot be just 1 to be inside, it has to be ANY odd number, because the line could leave the polygon and come back in, and even leave and re-enter another time. Just realize that once your line goes off the screen (assuming your polygon is contained within the screen) that its state is OUTSIDE, and the state that it started in (what you are looking for) is dependent on wether it crossed an odd or even number of lines.

 

[NeilTrain]

Ok ive researched it a little more, whats described above is the Crossing Number algorithm, which works in most cases, but has some flaws. It gets messy when the imaginary lines cross a vertex, for example.

The more accurate algorithm is called the "Winding Point" algorithm, which counts how many times the lines "wrap around" the point being tested. If the lines turn torward the point more than they turn away, the point is inside the polygon. (I think i described that thouroughly, i may be missing something though)

Anyways, heres a function that I attempted to convert from some C++ code I had to C# hope I didnt screw this up too much, the IsLeft function below it is required.

public bool IsPointWithin(Point point, Point[] poly)
		{
			// winding number test for a point in a polygon
			//      Input:   P = a point,
			//               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
			//      Return:  wn = the winding number (=0 only if P is outside V[])

			int Counter = 0;

			// loop through all edges of the polygon
			for (int i = 0; i < poly.Length; i++) 
			{   // edge from poly[i] to poly[i+1]
				if (poly[i].Y <= point.Y) 
				{   
					// start y <= point.Y
					if (poly[i+1].Y > point.Y)  // an upward crossing
					{
						if (isLeft(poly[i], poly[i+1], point) > 0)  // point left of edge
						{
							++Counter;  // have a valid up intersect
						}
					}
				}
				else 
				{   
					// start y > point.y (no test needed)
					if (poly[i+1].Y <= point.Y)     // a downward crossing
						if (isLeft( poly[i], poly[i+1], point) < 0)  // point right of edge
						{
							--Counter;            // have a valid down intersect
						}
				}
			}
			if(Counter != 0)
			{
				return true;
			}
			else
			{
				return false;
			}
		}

private int isLeft(Point LinePoint1, Point LinePoint2, Point TestPoint )
		{
			// tests if a point is Left|On|Right of an infinite line.
			//    Input:  three points LinePoint1, LinePoint2, and TestPoint
			//    Return: >0 for TestPoint left of the line through LinePoint1 and LinePoint2
			//            =0 for TestPoint on the line
			//            <0 for TestPoint right of the line
			return ((LinePoint2.X - LinePoint1.X) * (TestPoint.Y - LinePoint1.Y) - (TestPoint.X - LinePoint1.X) * (LinePoint2.Y - LinePoint1.Y));
		}

 

[kettch]

That's pretty hairy, but I think I understand, thanks!