I'm trying to determine if a point is inside a polygon. the Polygon is defined by an array of Point objects. I can easily figure out if the point is inside the bounded box of the polygon, but I'm not sure how to tell if it's inside the actual polygon or not. If possible, I'd like to only use C# and WinForms. I'd rather not call on OpenGL or something to do this simple task.
Here's the code I have so开发者_运维知识库 far:
private void CalculateOuterBounds()
{
//m_aptVertices is a Point[] which holds the vertices of the polygon.
// and X/Y min/max are just ints
Xmin = Xmax = m_aptVertices[0].X;
Ymin = Ymax = m_aptVertices[0].Y;
foreach(Point pt in m_aptVertices)
{
if(Xmin > pt.X)
Xmin = pt.X;
if(Xmax < pt.X)
Xmax = pt.X;
if(Ymin > pt.Y)
Ymin = pt.Y;
if(Ymax < pt.Y)
Ymax = pt.Y;
}
}
public bool Contains(Point pt)
{
bool bContains = true; //obviously wrong at the moment :)
if(pt.X < Xmin || pt.X > Xmax || pt.Y < Ymin || pt.Y > Ymax)
bContains = false;
else
{
//figure out if the point is in the polygon
}
return bContains;
}
I've checked codes here and all have problems.
The best method is:
/// <summary>
/// Determines if the given point is inside the polygon
/// </summary>
/// <param name="polygon">the vertices of polygon</param>
/// <param name="testPoint">the given point</param>
/// <returns>true if the point is inside the polygon; otherwise, false</returns>
public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint)
{
bool result = false;
int j = polygon.Count() - 1;
for (int i = 0; i < polygon.Count(); i++)
{
if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
{
if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
{
result = !result;
}
}
j = i;
}
return result;
}
The accepted answer did not work for me in my project. I ended up using the code found here.
public static bool IsInPolygon(Point[] poly, Point p)
{
Point p1, p2;
bool inside = false;
if (poly.Length < 3)
{
return inside;
}
var oldPoint = new Point(
poly[poly.Length - 1].X, poly[poly.Length - 1].Y);
for (int i = 0; i < poly.Length; i++)
{
var newPoint = new Point(poly[i].X, poly[i].Y);
if (newPoint.X > oldPoint.X)
{
p1 = oldPoint;
p2 = newPoint;
}
else
{
p1 = newPoint;
p2 = oldPoint;
}
if ((newPoint.X < p.X) == (p.X <= oldPoint.X)
&& (p.Y - (long) p1.Y)*(p2.X - p1.X)
< (p2.Y - (long) p1.Y)*(p.X - p1.X))
{
inside = !inside;
}
oldPoint = newPoint;
}
return inside;
}
See this it's in c++ and can be done in c# in a same way.
for convex polygon is too easy:
If the polygon is convex then one can consider the polygon as a "path" from the first vertex. A point is on the interior of this polygons if it is always on the same side of all the line segments making up the path.
Given a line segment between P0 (x0,y0) and P1 (x1,y1), another point P (x,y) has the following relationship to the line segment. Compute (y - y0) (x1 - x0) - (x - x0) (y1 - y0)
if it is less than 0 then P is to the right of the line segment, if greater than 0 it is to the left, if equal to 0 then it lies on the line segment.
Here is its code in c#, I didn't check edge cases.
public static bool IsInPolygon(Point[] poly, Point point)
{
var coef = poly.Skip(1).Select((p, i) =>
(point.Y - poly[i].Y)*(p.X - poly[i].X)
- (point.X - poly[i].X) * (p.Y - poly[i].Y))
.ToList();
if (coef.Any(p => p == 0))
return true;
for (int i = 1; i < coef.Count(); i++)
{
if (coef[i] * coef[i - 1] < 0)
return false;
}
return true;
}
I test it with simple rectangle works fine:
Point[] pts = new Point[] { new Point { X = 1, Y = 1 },
new Point { X = 1, Y = 3 },
new Point { X = 3, Y = 3 },
new Point { X = 3, Y = 1 } };
IsInPolygon(pts, new Point { X = 2, Y = 2 }); ==> true
IsInPolygon(pts, new Point { X = 1, Y = 2 }); ==> true
IsInPolygon(pts, new Point { X = 0, Y = 2 }); ==> false
Explanation on the linq query:
poly.Skip(1) ==> creates a new list started from position 1 of the poly list and then by
(point.Y - poly[i].Y)*(p.X - poly[i].X) - (point.X - poly[i].X) * (p.Y - poly[i].Y) we'll going to calculate the direction (which mentioned in referenced paragraph).
similar example (with another operation):
lst = 2,4,8,12,7,19
lst.Skip(1) ==> 4,8,12,7,19
lst.Skip(1).Select((p,i)=>p-lst[i]) ==> 2,4,4,-5,12
meowNET anwser does not include Polygon vertices in the polygon and points exactly on horizontal edges. If you need an exact "inclusive" algorithm:
public static bool IsInPolygon(this Point point, IEnumerable<Point> polygon) { bool result = false; var a = polygon.Last(); foreach (var b in polygon) { if ((b.X == point.X) && (b.Y == point.Y)) return true; if ((b.Y == a.Y) && (point.Y == a.Y)) { if ((a.X <= point.X) && (point.X <= b.X)) return true; if ((b.X <= point.X) && (point.X <= a.X)) return true; } if ((b.Y < point.Y) && (a.Y >= point.Y) || (a.Y < point.Y) && (b.Y >= point.Y)) { if (b.X + (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X) <= point.X) result = !result; } a = b; } return result; }
You can use the ray casting algorithm. It is well-described in the wikipedia page for the Point in polygon problem.
It's as simple as counting the number of times a ray from outside to that point touches the polygon boundaries. If it touches an even number of times, the point is outside the polygon. If it touches an odd number of times, the point is inside.
To count the number of times the ray touches, you check intersections between the ray and all of the polygon sides.
My answer is taken from here:Link
I took the C code and converted it to C# and made it work
static bool pnpoly(PointD[] poly, PointD pnt )
{
int i, j;
int nvert = poly.Length;
bool c = false;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((poly[i].Y > pnt.Y) != (poly[j].Y > pnt.Y)) &&
(pnt.X < (poly[j].X - poly[i].X) * (pnt.Y - poly[i].Y) / (poly[j].Y - poly[i].Y) + poly[i].X))
c = !c;
}
return c;
}
You can test it with this example:
PointD[] pts = new PointD[] { new PointD { X = 1, Y = 1 },
new PointD { X = 1, Y = 2 },
new PointD { X = 2, Y = 2 },
new PointD { X = 2, Y = 3 },
new PointD { X = 3, Y = 3 },
new PointD { X = 3, Y = 1 }};
List<bool> lst = new List<bool>();
lst.Add(pnpoly(pts, new PointD { X = 2, Y = 2 }));
lst.Add(pnpoly(pts, new PointD { X = 2, Y = 1.9 }));
lst.Add(pnpoly(pts, new PointD { X = 2.5, Y = 2.5 }));
lst.Add(pnpoly(pts, new PointD { X = 1.5, Y = 2.5 }));
lst.Add(pnpoly(pts, new PointD { X = 5, Y = 5 }));
My business critical implementation of PointInPolygon function working on integers (as OP seems to be using) is unit tested for horizontal, vertical and diagonal lines, points on the line are included in the test (function returns true).
This seems to be an old question but all previous examples of tracing have some flaws: do not consider horizontal or vertical polygon lines, polygon boundary line or the order of edges (clockwise, counterclockwise).
The following function passes the tests I came up with (square, rhombus, diagonal cross, total 124 tests) with points on edges, vertices and just inside and outside edge and vertex.
The code does the following for every consecutive pair of polygon coordinates:
- Checks if polygon vertex equals the point
- Checks if the point is on a horizontal or vertical line
- Calculates (as double) and collects intersects with conversion to integer
- Sorts intersects so the order of edges is not affecting the algorithm
- Checks if the point is on the even intersect (equals - in polygon)
- Checks if the number of intersects before point x coordinate is odd - in polygon
Algorithm can be easily adapted for floats and doubles if necessary.
As a side note - I wonder how much software was created in the past nearly 10 years which check for a point in polygon and fail in some cases.
public static bool IsPointInPolygon(Point point, IList<Point> polygon)
{
var intersects = new List<int>();
var a = polygon.Last();
foreach (var b in polygon)
{
if (b.X == point.X && b.Y == point.Y)
{
return true;
}
if (b.X == a.X && point.X == a.X && point.X >= Math.Min(a.Y, b.Y) && point.Y <= Math.Max(a.Y, b.Y))
{
return true;
}
if (b.Y == a.Y && point.Y == a.Y && point.X >= Math.Min(a.X, b.X) && point.X <= Math.Max(a.X, b.X))
{
return true;
}
if ((b.Y < point.Y && a.Y >= point.Y) || (a.Y < point.Y && b.Y >= point.Y))
{
var px = (int)(b.X + 1.0 * (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X));
intersects.Add(px);
}
a = b;
}
intersects.Sort();
return intersects.IndexOf(point.X) % 2 == 0 || intersects.Count(x => x < point.X) % 2 == 1;
}
Complete algorithm along with C code is available at http://alienryderflex.com/polygon/
Converting it to c# / winforms would be trivial.
For those using NET Core, Region.IsVisible is available from NET Core 3.0. After adding package System.Drawing.Common,
using System;
using System.Drawing;
using System.Drawing.Drawing2D;
namespace Example
{
class Program
{
static bool IsPointInsidePolygon(Point[] polygon, Point point)
{
var path = new GraphicsPath();
path.AddPolygon(polygon);
var region = new Region(path);
return region.IsVisible(point);
}
static void Main(string[] args)
{
Point vt1 = new Point(0, 0);
Point vt2 = new Point(100, 0);
Point vt3 = new Point(100, 100);
Point vt4 = new Point(0, 100);
Point[] polygon = { vt1, vt2, vt3, vt4 };
Point pt = new Point(50, 50);
bool isPointInsidePolygon = IsPointInsidePolygon(polygon, pt);
Console.WriteLine(isPointInsidePolygon);
}
}
}
Of lesser importance is that, adding System.Drawing.Common package increased size of publish folder by 400 KB. Maybe compared to custom code, this implementation could also be slower (above function timed to be 18 ms on i7-8665u). But still, I prefer this, for one less thing to worry about.
All you really need are 4 lines to implement the winding number method. But first, reference the System.Numerics to use complex library. The code below assumes that you have translate a loop of points (stored in cpyArr) so that your candidate point stands at 0,0.
For each point pair, create a complex number c1 using the first point and c2 using the 2nd point ( the first 2 lines within the loop)
Now here is some complex number theory. Think of c1 and c2 as complex number representation of vectors. To get from vector c1 to vector c2, you can multiply c1 by a complex number Z (c1Z=c2). Z rotates c1 so that it points at c2. Then it also stretches or squishes c1 so that it matces c2. To get such a magical number Z, you divide c2 by c1 (since c1Z=c2, Z=c2/c1). You can look up your high school notes on dividing complex number or use that method provided by Microsoft. After you get that number, all we really care is the phase angle.
To use the winding method, we add up all the phases and we should +/- 2 pi if the point is within the area. Otherwise, the sum should be 0
I added edge cases, 'literally'. If your phase angle is +/- pi, you're right on the edge between the points pair. In that case, I'd say the point is a part of the area and break out of the loop
/// <param name="cpyArr">An array of 2 coordinates (points)</param> public static bool IsOriginInPolygon(double[,] cpyArr) { var sum = 0.0; var tolerance = 1e-4; var length = cpyArr.GetLength(0); for (var i = 0; i < length-1; i++) { //convert vertex point pairs to complex numbers for simplified coding var c2 = new Complex(cpyArr[i+1, 0], cpyArr[i+1, 1]); var c1 = new Complex(cpyArr[i, 0], cpyArr[i, 1]); //find the rotation angle from c1 to c2 when viewed from the origin var phaseDiff = Complex.Divide(c2, c1).Phase; //add the rotation angle to the sum sum += phaseDiff; //immediately exit the loop if the origin is on the edge of polygon or it is one of the vertices of the polygon if (Math.Abs(Math.Abs(phaseDiff) - Math.PI) < tolerance || c1.Magnitude < tolerance || c2.Magnitude < tolerance) { sum = Math.PI * 2; break; } } return Math.Abs((Math.PI*2 ) - Math.Abs(sum)) < tolerance; }
I recommend this wonderful 15-page paper by Kai Hormann (University of Erlangen) and Alexander Agathos (University of Athens). It consolidates all the best algorithms and will allow you to detect both winding and ray-casting solutions.
The Point in Polygon Problem for Arbitrary Polygons
The algorithm is interesting to implement, and well worth it. However, it is so complex that it is pointless for me to any portion of it directly. I'll instead stick with saying that if you want THE most efficient and versatile algorithm, I am certain this is it.
The algorithm gets complex because is is very highly optimized, so it will require a lot of reading to understand and implement. However, it combines the benefits of both the ray-cast and winding number algorithms and the result is a single number that provides both answers at once. If the result is greater than zero and odd, then the point is completely contained, but if the result is an even number, then the point is contained in a section of the polygon that folds back on itself.
Good luck.
This is an old question, but I optimized Saeed answer:
public static bool IsInPolygon(this List<Point> poly, Point point)
{
var coef = poly.Skip(1).Select((p, i) =>
(point.y - poly[i].y) * (p.x - poly[i].x)
- (point.x - poly[i].x) * (p.y - poly[i].y));
var coefNum = coef.GetEnumerator();
if (coef.Any(p => p == 0))
return true;
int lastCoef = coefNum.Current,
count = coef.Count();
coefNum.MoveNext();
do
{
if (coefNum.Current - lastCoef < 0)
return false;
lastCoef = coefNum.Current;
}
while (coefNum.MoveNext());
return true;
}
Using IEnumerators and IEnumerables.
If you are drawing Shapes on a Canvas this is a quick and easy Solution.
private void Canvas_MouseMove(object sender, MouseEventArgs e)
{
if (e.OriginalSource is Polygon)
{
//do something
}
}
"Polygon" can be any shape from System.Windows.Shapes.
Here's some modern C# code:
public record Point(double X, double Y);
public record Box(Point LowerLeft, Point UpperRight)
{
public Box(Point[] points)
: this(
new Point(
points.Select(x => x.X).Min(),
points.Select(x => x.Y).Min()),
new Point(
points.Select(x => x.X).Max(),
points.Select(x => x.Y).Max()))
{
}
public bool ContainsPoint(Point point)
{
return point.X >= LowerLeft.X
&& point.X <= UpperRight.X
&& point.Y >= LowerLeft.Y
&& point.Y <= UpperRight.Y;
}
}
public record Polygon(Point[] Points, Box Box)
{
public Polygon(Point[] points)
: this(points, new(points))
{
}
public bool ContainsPoint(Point point)
{
do
{
if (Box.ContainsPoint(point) == false)
{
break;
}
bool result = false;
int j = Points.Length - 1;
for (int i = 0; i < Points.Length; i++)
{
if ((Points[i].Y < point.Y && Points[j].Y >= point.Y)
|| (Points[j].Y < point.Y && Points[i].Y >= point.Y))
{
if (Points[i].X +
((point.Y - Points[i].Y) / (Points[j].Y - Points[i].Y) * (Points[j].X - Points[i].X))
< point.X)
{
result = !result;
}
}
j = i;
}
return result;
}
while (false);
return false;
}
}
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论