多边形内的像素计算 [英] Calculate pixels within a polygon

问题描述

在学校分配我们需要做一些图像识别，我们必须找到一个机器人的路径。

到目前为止，已经我们已经能够找到图像中的所有的多边形，但现在我们需要生成一个像素图，即在今后用于一个ASTAR算法。我们已经找到一种方法来做到这一点，下面显示的，但问题是，很慢，因为我们去，虽然每个像素，并测试它是否在多边形内部。所以我的问题是，有没有我们可以更快地生成此像素图的方法吗？

我们有多边形坐标列表

 私有列表< ; IntPoint>船体; 
  

功能的GetMap之称，以获得像素图

 公共点[]的GetMap（）
 {
名单，LT;点和GT;点=新的List<点和GT;（）; 
锁（船体）
 {
矩形RECT = getRectangle（）; 
的for（int x = rect.X; X< = rect.X + rect.Width; X ++）
 {
为（INT Y = rect.Y; Y< = RECT .Y + rect.Height; Y ++）
 {
如果（inPoly（X，Y））
 points.Add（新点（x，y））; 
} 
} 
} 
返回points.ToArray（）; 
} 
  

获取矩形就是用来限制搜索，本身我们不必去thoug的整体形象。

 公共矩形getRectangle（）
 {
 INT X = -1，Y = -1，宽度= -1，高度= -1; 
的foreach（船体IntPoint项）
 {
如果（item.X< X ||点¯x== -1）
 X = item.X; 
如果（item.Y< Y ||Ÿ== -1）
 Y = item.Y; 
 
 
如果（item.X>宽度||宽度== -1）
宽度= item.X; 
如果（item.Y>高度||高度== -1）
高度= item.Y; 
 
 
} 
返回新的Rectangle（X，Y，宽度x，高度y）的; 
} 
  

和atlast这就是我们如何检查，看是否有像素的多边形内

 公共BOOL inPoly（INT X，int y）对
 {
 INT I，J =船体。计数 -  1; 
布尔oddNodes = FALSE; 
 
为（i = 0; I< hull.Count;我++）
 {
如果（船体[I] .Y< Y&放大器;&安培;船体[J ] .Y> = Y 
 ||船体[J] .Y< Y&放大器;&安培;船体[I] .Y> = Y）
 {
试
 {
如果（船体[I] .X +（Y  - 船体[I] .X）/（船体[J] .X  - 船体[I] .X）*（船体[J] .X  - 船体[I] .X）LT; X）
 {
 oddNodes = oddNodes！; 
} 
} 
赶上（DivideByZeroException E）
 {
如果（0℃; X）
 {
 oddNodes = oddNodes！; 
} 
} 
} 
 J =; 
} 
返回oddNodes; 
} 
  

解决方案

您可能想寻找一个 Plygon三角算法。

另外请注意，捕获异常是更为费时该检查正确条件。所以我建议你到现有的代码转换成：

 公共BOOL inPoly（INT X，int y）对
 { 
 INT I，J = hull.Count  -  1; 
 VAR oddNodes = FALSE; 
 
为（i = 0; I< hull.Count;我++）
 {
如果（船体[I] .Y< Y&放大器;&安培;船体[J ] .Y> = Y 
 ||船体[J] .Y< Y&放大器;&安培;船体[I] .Y> = Y）
 {
 VAR增量=（船体[J] .X  - 船体[I] .X）; 
如果（增量== 0）
 {
如果（0℃; X）= oddNodes oddNodes！; 
} 
，否则如果（船体[I] .X +（Y  - 船体[I] .X）/ *三角洲三角洲< X）！
 {
 oddNodes = oddNodes ; 
} 
 
} 
 J =; 
} 
返回oddNodes; 
} 
  

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 coordinates for the polygon

private List<IntPoint> hull;

The function "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;
}

解决方案

You may want to look for a Plygon Triangulation algorithm.

Also, note that catching an exception is far more time-consuming that checking the right condition. So i suggest you to convert your existing code in:

   public bool inPoly(int x, int y)
    {
        int i, j = hull.Count - 1;
        var 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)
            {
                var delta = (hull[j].X - hull[i].X);
                if (delta == 0)
                {
                    if (0 < x) oddNodes = !oddNodes;
                }
                else if (hull[i].X + (y - hull[i].X) / delta * delta < x)
                {
                    oddNodes = !oddNodes;
                }

            }
            j = i;
        }
        return oddNodes;
    }

这篇关于多边形内的像素计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！