Scanline算法：如何计算交点

我必须从我们的教授实施扫描线算法，但我并不真正了解如何从扫描线与多边形获得交点。下面是算法： scanline algorithm Scanline算法：如何计算交点

我实现我自己的多边形（与像paint()，等方法），我已对从保存在一个数组这样的多边形的所有边：

int[] pointsX; 
int[] pointsY;

和我保存在

int ymin, ymax, xmin, xmax;

x和y的最小值和最大值所以我首先想到的是，我要创建从开始扫描线，如果下一个点位于多边形内，则检查一个循环。我实现了这个方法是这样的：

public boolean contains(Point test) { 
    boolean result = false; 

    java.awt.Polygon polygon = new java.awt.Polygon(pointsX, pointsY, pointsX.length); 
    if (polygon.contains(test)) { 
     result = true; 
    } 

    return result; 
}

所以当第二点是在多边形内部，我有一个交叉点等。为此我有这个循环：

ArrayList<Point> intersectionPoints = new ArrayList<>(); 
wasInside = false; 
    for (int yTemp = ymin; yTemp <= ymax; yTemp++) { 
     for (int xTemp = xmin; xTemp <= xmax; xTemp++) { 
      if (wasInside != this.contains(new Point(xTemp, yTemp))) { 
       intersectionPoints.add(new Point(xTemp, yTemp)); 
       wasInside = !wasInside; 
      } 
     } 
    }

但我得到一个暗示，这是从my stackoverflow question没有适当的解决方案。

有人可以给我一个提示，我可以从我的教授开始实施算法吗？我在哪里得到x1，y1，x2，y2，c点？我知道这些是边缘，但我怎么知道我必须采取哪些边缘？

编辑：好吧，现在我有所有的边缘按y值排序。我可以用给定的公式计算交点：Sx = x1 +（x2-x1）/ ...？我的第一次尝试是这样的：

for (int c = ymin; c <= ymax; c++) { 
     for (int xTemp = xmin; xTemp <= xmax; xTemp++) { 
      for (int currentEdge = 0; currentEdge < edges.size() - 1; currentEdge++) { 
       int x1 = edges.get(currentEdge).x; 
       int x2 = edges.get(currentEdge + 1).x; 
       int y1 = edges.get(currentEdge).y; 
       int y2 = edges.get(currentEdge + 1).y; 
       if ((y1 <= c && y2 > c) || (y2 <= c && y1 > c)) { 
        intersectionPoints.add(new Point((x1 + (x2 - x1)/(y2 - y1) * (c - y1)),c)); 
       } 
      } 
     } 
    }

但是，这似乎是错误的，因为我在intersectionPoints得到了很多错误之分的。

来源

2014-06-28 Peter

扫描线算法通常保持一组“活动边”（即与当前扫描线相交的边）。 “c”只是扫描线的当前y位置。（x1，y1）和（x2，y2）点只是一个有效边的端点。您必须根据y值对所有边进行排序，然后让c从ymin走到ymax，每当您扫描一个角时更新一组活动边。 – Marco13

感谢您的提示。我添加了我的尝试来计算intersectionPoints，但它有错误。我究竟做错了什么？我想我没有很好地理解这个算法...... – Peter

你从来没有设法说出你想要计算的东西。“扫描线”是一类可以计算许多事物的算法。正如@ Marco13所说，扫描线本身就是一个数据结构，通常包括它当前相交的边缘，线段，弧线等列表。边缘等的端点以及交叉点被处理为改变扫描线的“事件”。 – Gene

问题是我用int数字计算和int除以另一int结果不准确。所以只要用double这个数字来解决这个问题。

这是我如何计算交点： edges是一个ArrayList<Point>包含边缘点。 ymin是最低的y值，'ymax`是最高的。

for (int yTemp = ymin; yTemp <= ymax; yTemp++) { 
     ArrayList<Point> intersectionPoints = new ArrayList<>(); 

     for (int p = 0; p < edges.size() - 1; p++) { 
      int x1, x2, y1, y2; 
      double deltax, deltay, x; 
      x1 = edges.get(p).x; 
      y1 = edges.get(p).y; 
      x2 = edges.get(p + 1).x; 
      y2 = edges.get(p + 1).y; 

      deltax = x2 - x1; 
      deltay = y2 - y1; 

      int roundedX; 
      x = x1 + deltax/deltay * (yTemp - y1); 
      roundedX = (int) Math.round(x); 
      if ((y1 <= yTemp && y2 > yTemp) || (y2 <= yTemp && y1 > yTemp)) { 
       intersectionPoints.add(new Point(roundedX, yTemp)); 
      } 
     } 
     //for the last interval 
     int x1, x2, y1, y2; 
     x1 = edges.get(edges.size() - 1).x; 
     y1 = edges.get(edges.size() - 1).y; 
     x2 = edges.get(0).x; 
     y2 = edges.get(0).y; 
     if ((y1 <= yTemp && y2 > yTemp) || (y2 <= yTemp && y1 > yTemp)) { 
      intersectionPoints.add(new Point(x1 + (x2 - x1)/(y2 - y1) * yTemp - y1, yTemp)); 
     } 
     //you have to sort the intersection points of every scanline from the lowest x value to thr highest 
     Collections.sort(intersectionPoints, new SortXPoints()); 
     pointsOfScanline.add(intersectionPoints);

这将为您提供一个ArrayList，其中包含每个Scanline的扫描线点的ArrayLists。所以你只需要用drawLine(x1, y2, x2, y2)来绘制它们。

来源

2014-07-12 11:32:39 Peter

Scanline算法：如何计算交点

回答

相关问题