Testing to see if a Point is within a Polygon
I’m on a brief respite from my Compact Framework woes: I am instead in the process of rewriting a very old Java Sketching program. Our legacy application stores text-based vectors for drawing 2D sketches of the external footprint of structures. Until I wrote this Java program in 2001, our sketches were always rendered in Text. Yes, I said TEXT. Dashes, underlines, plus signs, forward slashes and backward slashes – well you get the idea. We began displaying some of this information on the Internet and needed something a little more modern. This program in particular reads through our entire database and creates all the Sketches as JPGs, storing them locally on the C drive. There is a companion program that creates and displays in a GUI a single sketch requested by the user (via a function key in our iSeries RPG program).
In fact, one interesting note about it: this was the first PC based program I ever wrote. Since I was in the throes of learning Java anyway (my first PC or Web related language), I took on the task of making something out of nothing. Of course, I had no idea what I was getting in to, but I ended up with a crash course in Object Oriented design, JDBC and disconnected databases, Swing (shoot me if I ever go down THAT path again!), and of course 2D graphics. For someone who did not know the first thing about GUI development, this project was way too much for a first try. But 5-6 months of reading, studying, trial and error, and labor and I ended up with a workable program.
Don’t get me wrong: it is an abhorrent behometh, chock full of bad techniques and poor implementations. Worst of all, it is a Java program, and on more than one occasion has broken due to updates in the JRE. Couple that with the fact that it is slow as death (again, certainly my own fault) and almost NEVER deploys properly thanks to myriad Classpath woes and divergent operating system. After my last machine bit the dust, I never even bothered to recreate my Java environment (as I had completely moved on to VS2003 by then). As a result, legitimate complaints by users have gone unaddressed, largely because of my own unwillingness to return to Java.
Fast forward to today: now experienced in Java, PHP, Perl, and of course my favorite, C#, and having done quite a bit of GUI and OO development in the intervening years, I finally decided to tackle the rewrite of my old behometh. I rewrote the engine Wednesday afternoon, and by the end of the day had rudimentary sketching working. 5 Hours to do what originally took 5 months. I spent part of yesterday working on the Text labelling, which is quite a bit more difficult than the actual drawing. I’ll probably spend another few days hashing all that out.
During my labors, though, I discovered a shocking omission in the C# language: there is no Polygon Class. Drawing the Polygons is easy enough using the Graphics DrawPolygon member, but as I am inserting labels, I need to check and see if the proposed position is within the Bounds of the Polygon, and I would like to center some labels, so I need to know what the center point is, etc., etc. So, I quickly whipped up my own Polygon class. The class manages a read-only Array of PointF objects, so right now it is immutable. I may change that if the need arises, but for now I need to work with the complete closed Polygon.
It is not overly complex or anything like that, but here are some of the key features
- Bounds of the Polygon
- CenterPoint of those Bounds
- Minimum and Maximum X and Y
- Number of Points
- Determine if a PointF is in the Bounds
- Calculate Area of the Polygon
- Determine if the Polygon Contains a PointF (different than above)
That last one was a real challenge. A PointF could easily be in the Rectangular Bounds of a Polygon but not inside the Polygon itself, so the Contains check determines whether or not the PointF is actually inside the boundaries of the Polygon. This required more math than I was able to come up with, so I turned to my trusty friend Google and found this link. At this site, you can find the formula originally written in Fortran and converted to C. Naturally, I converted it on to C#, and I am now sharing that code with you.
public bool Contains(PointF pt)
{
bool isIn = false;
if (IsInBounds(pt))
{
int i, j = 0;
for (i = 0, j = NumberOfPoints - 1; i < NumberOfPoints; j = i++)
{
if (
(
((_pts[i].Y <= pt.Y) && (pt.Y < _pts[j].Y)) || ((_pts[j].Y <= pt.Y) && (pt.Y < _pts[i].Y))
) &&
(pt.X < (_pts[j].X - _pts[i].X) * (pt.Y - _pts[i].Y) / (_pts[j].Y - _pts[i].Y) + _pts[i].X)
)
{
isIn = !isIn;
}
}
}
return isIn;
}
You can see that I bypass any points that are outside the rectangular bounds altogether since there is no point in running the rest of the checks at that point, but that is really the only fundamental change I made. Of course, I return an actual Boolean but the orginial C returned an int.
When I complete the rest of the Polygon code, I’ll post it in the Free Code section. This one is actually PolygonF for using floats, but it could easily be modified to use Integers instead.
UPDATE:
Developing For .NET 
thank You very much, that’s what i needed 🙂
I’m glad you found it useful, and on the one year anniversary of that post too!
thank you very much , but i have a requestion about if i can have your whole demo about this project?
hi ,
i wrote a code about drawing polygon ,and judge some points if there are in or not in the polygon using c# ,but the result is very different , some times the judge is right ,some times it is wrong to the same situation ,i don’t kown why . and i need your help,ple leave a email ,so that i can send it to you.
thank you
I can’t share the complete code as this is in live proprietary software, but I will say that using the actual PolygonF code is very simple:
PolygonF poly = new PolygonF(POINTF_ARRAY);
if (poly.Contains(SOME_POINTF))
{
…
}
And it works in our production code every time, millions of calls in a single thread execution.
This is a very complex application, and there is a lot of code prior to this that sets up the POINTF_ARRAY, taking into consideration adjustments for margins, padding, available size, centering, etc. In the end, there are a few things that I think are critical. First, all the points are in positive space. Mathematically speaking, this probably shouldn’t matter, but I know in positive space it always works. Second, the points are added to the array in the correct order, ensuring that the proper shape is represented.
This is a great time to try some Unit Testing! I added a Test project to my Solution, used TestInitialize to create a PolygonF object, and then wrote a test method to test various points. Here is a simple example:
[TestInitialize()]
public void MyTestInitialize()
{
List pointList = new List()
{
new PointF(10, 10),
new PointF(10, 20),
new PointF(20, 20),
new PointF(20, 10)
};
PolyF = new PolygonF(pointList.ToArray());
}
[TestMethod]
public void PolygonContainsPoint()
{
Assert.IsTrue(PolyF.Contains(new PointF(15,15)));
}
Simply change this last point around to test within/without responses. While this example is a simple square, this code is currently funcitoning with some fairly complex non-symmetrical polygons, up to 20 sides (a limit of our application, not this class).
this is my code ,can you help me to correct it ,or add your methods to it let it gain right result ?
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Drawing.Drawing2D;
using System.Collections.Generic;
namespace LineAndPolygon
{
public partial class Form1 : Form
{
private Point lastPoint = new Point(-1, -1);
private List alPoints; //save all vertex of polygon
private IEnumerator enumerator;
private Region areaRegion = null;
private GraphicsPath areaPath = null;
//test if pp is in the polygon
Point[] pp = { new Point(81, 24), new Point(200, 158) };
//m_Bitmap1 store the opened image info
Bitmap m_Bitmap1 = new Bitmap(2, 2);
public Form1()
{
InitializeComponent();
alPoints = new List();
}
protected GraphicsPath AreaPath
{
get
{
return areaPath;
}
set
{
areaPath = value;
}
}
protected Region AreaRegion
{
get
{
return areaRegion;
}
set
{
areaRegion = value;
}
}
///
/// ??????????
///
///
///
private bool PointInObject(Point point)
{
return AreaRegion.IsVisible(point);
}
private void CreateObject()
{
if (AreaPath != null)
return;
AreaPath = new GraphicsPath();
int x1 = 0, y1 = 0;
int x2, y2;
enumerator = alPoints.GetEnumerator();
if (enumerator.MoveNext()) //point to the first value
{
x1 = ((Point)enumerator.Current).X;
y1 = ((Point)enumerator.Current).Y;
}
while(enumerator.MoveNext())
{
x2 = ((Point)enumerator.Current).X;
y2 = ((Point)enumerator.Current).Y;
AreaPath.AddLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
}
AreaPath.CloseFigure();
AreaRegion = new Region(AreaPath);
}
private void panel1_MouseDown(object sender, MouseEventArgs e)
{
Graphics g = panel1.CreateGraphics();
//Random rand = new Random();
//int rc = rand.Next(255);
//int gc = rand.Next(255);
//int bc = rand.Next(255);
if (e.Button == MouseButtons.Left &&?this.radioButton1.Checked)
{
g.FillRectangle(new SolidBrush(Color.Black), e.X, e.Y, 5, 5);
if (lastPoint.X != -1 && lastPoint.Y != -1)
{
g.DrawLine(new Pen(new SolidBrush(Color.Red)),
lastPoint, new Point(e.X, e.Y));
}
lastPoint.X = e.X;
lastPoint.Y = e.Y;
alPoints.Add(lastPoint);
}
else if (e.Button == MouseButtons.Right && this.radioButton1.Checked)
{
Point[] points = alPoints.ToArray();
//if (rand.Next(1) == 0)
//{
g.DrawPolygon(new Pen(new SolidBrush(
Color.FromArgb(0, 255, 0))), points);
//}
//else
//{
// g.FillPolygon(new SolidBrush(Color.FromArgb(rc, gc, bc)),points);
//}
// alPoints.Clear();
lastPoint.X = -1;
lastPoint.Y = -1;
CreateObject();
testPoint(pp);
alPoints.Clear();
}
// g.Dispose();
}
public void testPoint(Point[] pp)
{
////i :?????j? ??????pp.y=i,pp.x=j; pp.length=i*img.width+j;
for (int k = 0; k < pp.Length; k++)
{
if (PointInObject(pp[k]))
{
MessageBox.Show(” pp[“+k.ToString()+”] is in the polygon”);
label1.Text = Convert.ToString(k);
}
else
{
MessageBox.Show(” pp[” + k.ToString() + “] is not in the polygon”);
label1.Text = “none point in”;
}
}
label1.Text = “”;
}
private void button1_Click(object sender, EventArgs e)
{
openFileDialog1.Filter = “Bitmap??(*.bmp)|*.bmp| Jpeg??(*.jpg)|*.jpg| ??????(*.bmp/*.jpg)|*.bmp/*.jpg”;
if(DialogResult.OK == openFileDialog1.ShowDialog())
{
m_Bitmap1 = (Bitmap)Bitmap.FromFile(openFileDialog1.FileName, false);
}
////???????????
for (int k = 0; k < m_Bitmap1.Width * m_Bitmap1.Height; k++)
{
// for (int i = 0; i < m_Bitmap1.Height; i++)
// {
// for (int j = 0; j < m_Bitmap1.Width; j++)
// {
// positonPoint[k] = new Point(i, j);
// pixelValue = m_Bitmap1.GetPixel(i, j);
// rValue = pixelValue.R;
// gValue = pixelValue.G;
// bValue = pixelValue.B;
// }
// }
}
//panel1.Invalidate();
//panel1.Refresh();
Graphics g = panel1.CreateGraphics();
g.DrawImage(m_Bitmap1, new Point(0, 0));
//g.Dispose();
}
Thanks!
Thank u very much!