• Advertisement

Archived

This topic is now archived and is closed to further replies.

Point in a Polygon

This topic is 4998 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was just wondering if there is any algorithm out there that allows me to determine if a point is in a polygon. I can do it for a triangle, by using a system of three equations. I looked at the stuff at Magic-Software.com, but there techniques need to know if it is a convex, or concave, or con-shit... Too complicated. Any help is appreciated. Thanks in advance. Sagar.Indurkhya

Share this post


Link to post
Share on other sites
Advertisement
There are a few different algorithms.

One technique is to measure the angle between each vertex of the polygon with the intersection point as your point of reference. If you get roughly 360 degrees, the point is in the poly. This method is slow and suffers from numerical imprecision.

You can also form a plane for each edge of the poly whose normal points toward the interior of the poly. If the intersection point is in front of each of these planes, then it is in the poly. This method is also slow.

The method I use is plucker coordinates, but this assumes that your intersection point originated from a ray/poly intersection test. With plucker coordinates you can quickly and robustly determine if a ray intersects a convex polygon. If it does, than you can proceed to calculate the point of intersection.

If you just stick to triangles, there are several fast shortcut algorithms that I''ve seen. I still use plucker lines, but you can also use barycentric coordinates and a few other methods.

Hope that helps...

Share this post


Link to post
Share on other sites
Here''s another method that I forgot. It may be similar to the winding number mentioned above, but I only glanced over the article so I''m not sure.

This method is to compute a normal for the triangle formed by every vertex n, n + 1, and the intersection point. If you encounter a normal that points in the opposite direction of the polygon normal, the point is outside the poly. If all normals point in the same direction as the poly normal, the point is inside the poly. Like the other methods, this one is somewhat slow and unstable.

If the intersection point you are testing comes from a ray/polygon intersection, I would still encourage you to look into plucker lines. It requires a lot less code than the winding number method mentioned above, requires fewer (none, actually) special cases, and I''m guessing is more robust.

Just giving you some options.

Share this post


Link to post
Share on other sites
Here is a very lightwwight way that I did it.

Most of the tools that I work with have graphics tools. I wrote this in C#. The idea is that you create a bitmap object with your polygon, and fill it with black. Then you just get the pixel associated with your point and if it is black then it is in the polygon. It doesn''t use any of the segment crossing algorithms, but it is very intuitive, and VERY quick to code.

code with a GUI:

using System;
using System.Windows.Forms;
using System.Collections;
using System.Drawing;

namespace DefaultNamespace
{
///
/// Description of MainForm.
///

public class MainForm : System.Windows.Forms.Form
{
private System.Windows.Forms.Panel panel;
private System.Windows.Forms.NumericUpDown numericUpDown;
private System.Windows.Forms.Button button;
private System.Windows.Forms.Button button3;
private System.Windows.Forms.Button button2;
private System.Windows.Forms.NumericUpDown numericDel;
public MainForm()
{
//
// The InitializeComponent() call is required for Windows Forms designer support.
//
InitializeComponent();

//
// TODO: Add constructor code after the InitializeComponent() call.
//
}

[STAThread]
public static void Main(string[] args)
{
Application.Run(new MainForm());
}

#region Windows Forms Designer generated code
///
/// This method is required for Windows Forms designer support.
/// Do not change the method contents inside the source code editor. The Forms designer might
/// not be able to load this method if it was changed manually.
///

private void InitializeComponent() {
this.numericDel = new System.Windows.Forms.NumericUpDown();
this.button2 = new System.Windows.Forms.Button();
this.button3 = new System.Windows.Forms.Button();
this.button = new System.Windows.Forms.Button();
this.numericUpDown = new System.Windows.Forms.NumericUpDown();
this.panel = new System.Windows.Forms.Panel();
((System.ComponentModel.ISupportInitialize)(this.numericDel)).BeginInit();
((System.ComponentModel.ISupportInitialize)(this.numericUpDown)).BeginInit();
this.SuspendLayout();
//
// numericDel
//
this.numericDel.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
this.numericDel.Location = new System.Drawing.Point(456, 472);
this.numericDel.Maximum = new System.Decimal(new int[] {
1000000,
0,
0,
0});
this.numericDel.Minimum = new System.Decimal(new int[] {
1,
0,
0,
0});
this.numericDel.Name = "numericDel";
this.numericDel.TabIndex = 4;
this.numericDel.Value = new System.Decimal(new int[] {
100,
0,
0,
0});
//
// button2
//
this.button2.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
this.button2.Location = new System.Drawing.Point(592, 472);
this.button2.Name = "button2";
this.button2.TabIndex = 3;
this.button2.Text = "delete last";
this.button2.Click += new System.EventHandler(this.Button2Click);
//
// button3
//
this.button3.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
this.button3.Location = new System.Drawing.Point(344, 464);
this.button3.Name = "button3";
this.button3.TabIndex = 5;
this.button3.Text = "CLEAR";
this.button3.Click += new System.EventHandler(this.Button3Click);
//
// button
//
this.button.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
this.button.Location = new System.Drawing.Point(160, 464);
this.button.Name = "button";
this.button.Size = new System.Drawing.Size(144, 23);
this.button.TabIndex = 1;
this.button.Text = "generateRandomPoints";
this.button.Click += new System.EventHandler(this.ButtonClick);
//
// numericUpDown
//
this.numericUpDown.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
this.numericUpDown.Location = new System.Drawing.Point(24, 464);
this.numericUpDown.Maximum = new System.Decimal(new int[] {
100000,
0,
0,
0});
this.numericUpDown.Name = "numericUpDown";
this.numericUpDown.TabIndex = 2;
this.numericUpDown.Value = new System.Decimal(new int[] {
10,
0,
0,
0});
//
// panel
//
this.panel.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom)
| System.Windows.Forms.AnchorStyles.Left)
| System.Windows.Forms.AnchorStyles.Right)));
this.panel.AutoScroll = true;
this.panel.Location = new System.Drawing.Point(8, 8);
this.panel.Name = "panel";
this.panel.Size = new System.Drawing.Size(680, 448);
this.panel.TabIndex = 0;
this.panel.MouseUp += new System.Windows.Forms.MouseEventHandler(this.PanelMouseUp);
this.panel.Paint += new System.Windows.Forms.PaintEventHandler(this.PanelPaint);
this.panel.MouseMove += new System.Windows.Forms.MouseEventHandler(this.PanelMouseMove);
this.panel.MouseDown += new System.Windows.Forms.MouseEventHandler(this.PanelMouseDown);
//
// MainForm
//
this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
this.ClientSize = new System.Drawing.Size(688, 501);
this.Controls.Add(this.button3);
this.Controls.Add(this.numericDel);
this.Controls.Add(this.button2);
this.Controls.Add(this.numericUpDown);
this.Controls.Add(this.button);
this.Controls.Add(this.panel);
this.Name = "MainForm";
this.Text = "MainForm";
((System.ComponentModel.ISupportInitialize)(this.numericDel)).EndInit();
((System.ComponentModel.ISupportInitialize)(this.numericUpDown)).EndInit();
this.ResumeLayout(false);
}
#endregion
void PanelPaint(object sender, System.Windows.Forms.PaintEventArgs e)
{
if(this.points.Count == 0) {
} else if(this.points.Count == 1) {
Point p = (Point)this.points[0];
e.Graphics.DrawEllipse(new Pen(Color.White),p.X,p.Y,3,3);
} else if (this.points.Count == 2) {
Point p1 = (Point)this.points[0];
Point p2 = (Point)this.points[1];
e.Graphics.DrawLine( new Pen(Color.White),p1.X,p1.Y,p2.X,p2.Y);
} else {
Point[] ps = new Point[this.points.Count];
for(int i = 0; i < this.points.Count; i++) {
ps = (Point)this.points[i];
}
e.Graphics.DrawPolygon(new Pen(Color.White),ps);
}
if(bmpPoly != null) {
for(int i = 0; i < this.randpPoints.Count; i++) {
Point p = (Point)this.randpPoints[i];
Color pxl = bmpPoly.GetPixel(p.X,p.Y);
SolidBrush brush = new SolidBrush(Color.Red);
//txtStatus.Text = txtStatus.Text + "\r\n"+pxl;
if(pxl.A==255) {
brush = new SolidBrush(Color.Green);
}
e.Graphics.FillEllipse(brush,p.X,p.Y,2,2);
}
}
}

public ArrayList points = new ArrayList();
public ArrayList randpPoints = new ArrayList();
void PanelMouseUp(object sender, System.Windows.Forms.MouseEventArgs e)
{
this.points.Add(new Point(e.X,e.Y));
this.panel.Refresh();
down = false;
}

void Button2Click(object sender, System.EventArgs e)
{
for(int i = 0; i < int.Parse(this.numericDel.Value+""); i++) {
if(this.points.Count > 0) {
this.points.RemoveAt(this.points.Count-1);
}
}
this.panel.Refresh();
}

void PanelMouseMove(object sender, System.Windows.Forms.MouseEventArgs e)
{
if(down) {
this.points.Add(new Point(e.X,e.Y));
this.panel.Refresh();
}
}
private bool down = false;
void PanelMouseDown(object sender, System.Windows.Forms.MouseEventArgs e)
{
down = true;
}

void Button3Click(object sender, System.EventArgs e)
{
this.randpPoints = new ArrayList();
this.panel.Refresh();
}
Bitmap bmpPoly;
void ButtonClick(object sender, System.EventArgs e)
{
bmpPoly = new Bitmap(this.panel.Width,this.panel.Height);
Graphics poly = Graphics.FromImage(bmpPoly);
Random r = new Random();
if(this.points.Count > 2) {
Point[] ps = new Point[this.points.Count];
int topX = 0;
int topY = 0;
int botX = 200000;
int botY = 200000;
for(int i = 0; i < this.points.Count; i++) {
ps[i] = (Point)this.points[i];
topX = Math.Max(topX,ps[i].X);
topY = Math.Max(topY,ps[i].Y);
botX = Math.Min(botX,ps[i].X);
botY = Math.Min(botY,ps[i].Y);
}
SolidBrush brush = new SolidBrush(Color.Black);
poly.FillPolygon(brush,ps);


int num = int.Parse(this.numericUpDown.Value+"");
for(int i = 0; i < num; i++) {
Point p = new Point(r.Next(botX,topX),r.Next(botY,topY));
this.randpPoints.Add(p);
}
}
this.panel.Refresh();

}

}
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by sip8980
Here is a very lightwwight way that I did it.


While intuitive, it''s not really an option in a 3d-engine

Share this post


Link to post
Share on other sites
Thread closing. This is a very common question that is referenced in the Forum FAQ and has been discussed many times in the past. I see no need to let this thread remain open.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
This method is to compute a normal for the triangle formed by every vertex n, n + 1, and the intersection point. If you encounter a normal that points in the opposite direction of the polygon normal, the point is outside the poly. If all normals point in the same direction as the poly normal, the point is inside the poly. Like the other methods, this one is somewhat slow and unstable.


This doesn't work for some concave polygons.

The best way is the crossing number method imho. It's much faster than the winding order method. It might go wrong with self intersecting polygons, but you shouldn't use that kind of polygons anyway. You only have to watch out when crossing a vertex or horizontal edge, but that's all explained in the article sneftel posted

Here is my function, you may use it if you want.


bool Polygon2D::PointInPol(const Vector2D &point) const
{
// test how many edges are intersected with the line from point to somewhere infinitely outside the pol
bool intersect = false;
Vector2D curvert;
Vector2D nextvert = verts[verts.size() - 1].GetPosition();
for(int i = 0;i < (int)verts.size();i++)
{
curvert = nextvert;
nextvert = verts[i].GetPosition();

// test if the line lays on a vert
if(curvert.y == point.y || nextvert.y == point.y)
{
// horizontal edges will be ignored
if(curvert.y != nextvert.y)
{
if(curvert.y == point.y && curvert.x < point.x && curvert.y < nextvert.y)
intersect = !intersect;
else if(nextvert.y == point.y && nextvert.x < point.x && curvert.y > nextvert.y)
intersect = !intersect;
}
}

// if the line doesn't lay on a vert, we can test if the line intersects with the edge
// so we first test if the edge possibly intersects with the line
else if((point.y > curvert.y && point.y < nextvert.y) || (point.y < curvert.y && point.y > nextvert.y))
{
// if the line is entirely at the right side of the point, it will intersect
if(point.x > curvert.x && point.x > nextvert.x)
intersect = !intersect;
// if the point is in the bounding rect of the line, we need to do a perfect test
else if(curvert.x < point.x || nextvert.x < point.x)
{
float intersectionx = nextvert.x - curvert.x;
intersectionx = intersectionx / (nextvert.y - curvert.y) * (point.y - curvert.y);
intersectionx += curvert.x;

if(intersectionx < point.x)
intersect = !intersect;
}
}
}

return intersect;
}



[Edited by - quasar3d on June 19, 2004 6:07:28 AM]

Share this post


Link to post
Share on other sites
"This doesn't work for some concave polygons."

Sorry, I wasn't suggesting that it does. I was just assuming (perhaps incorrectly) that he was working with convex polys.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
You can also form a plane for each edge of the poly whose normal points toward the interior of the poly. If the intersection point is in front of each of these planes, then it is in the poly. This method is also slow.


So 'n' dotproducts for an 'n' sided/surfaced polygon is slow?

Share this post


Link to post
Share on other sites

for(int j = Poly.numverts-1, i = 0; i < Poly.numverts; j = i, i ++)
{
Vector E = Poly.V[i] - Poly.V[j];
Vector D = P - V[i];
Vector En= E.Cross(Poly.Normal);
float d = D.Dot(En);

if (d < 0.0f) return false;
}
return true;


two subs + one cross + one dot per edge. Hardly a stretch for a processor. And it should be easy to really optimise the hell of it. And unrolling for triangles, ...

Share this post


Link to post
Share on other sites

This topic is 4998 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.

  • Advertisement