Calculate pixels within a polygon
- by DoomStone
In an assignment for school do we need to do some image recognizing, where we have to find a path for a robot.
So far have we been able to find all the polygons in the image, but now we need to generate a pixel map, that be used for an astar algorithm later. We have found a way to do this, show below, but the problem is that is very slow, as we go though each pixel and test if it is inside the polygon. So my question is, are there a way that we can generate this pixel map faster?
We have a list of cordinates for the polygon
private List<IntPoint> hull;
The fuction "getMap" is called to get the pixel map
public Point[] getMap()
{
List<Point> points = new List<Point>();
lock (hull)
{
Rectangle rect = getRectangle();
for (int x = rect.X; x <= rect.X + rect.Width; x++)
{
for (int y = rect.Y; y <= rect.Y + rect.Height; y++)
{
if (inPoly(x, y))
points.Add(new Point(x, y));
}
}
}
return points.ToArray();
}
Get Rectangle is used to limit the search, se we don't have to go thoug the whole image
public Rectangle getRectangle()
{
int x = -1, y = -1, width = -1, height = -1;
foreach (IntPoint item in hull)
{
if (item.X < x || x == -1)
x = item.X;
if (item.Y < y || y == -1)
y = item.Y;
if (item.X > width || width == -1)
width = item.X;
if (item.Y > height || height == -1)
height = item.Y;
}
return new Rectangle(x, y, width-x, height-y);
}
And atlast this is how we check to see if a pixel is inside the polygon
public bool inPoly(int x, int y)
{
int i, j = hull.Count - 1;
bool oddNodes = false;
for (i = 0; i < hull.Count; i++)
{
if (hull[i].Y < y && hull[j].Y >= y
|| hull[j].Y < y && hull[i].Y >= y)
{
try
{
if (hull[i].X + (y - hull[i].X) / (hull[j].X - hull[i].X) * (hull[j].X - hull[i].X) < x)
{
oddNodes = !oddNodes;
}
}
catch (DivideByZeroException e)
{
if (0 < x)
{
oddNodes = !oddNodes;
}
}
}
j = i;
}
return oddNodes;
}
