java - 如何获取java多边形的边界

Question

假设我有一个点网格，我使用一些函数来“标记”其中一些并将它们添加到常规 Java Polygon 中，像这样:

我应该如何确定Polygon的外边界是什么？最好根据需要返回尽可能少的点，如下所示:

我尝试了像 getBounds 或 getPathIterator 这样的 Polygon 方法，但它们在我的情况下不起作用，因为它们也会使用内部点。

此外，点之间的红线不应呈对角线。

Answer 1

您的图像已经说明了解决方案:您可以安全地删除 3 个连续点的中间如果这 3 个点形成一条垂直线或水平线(即全部具有相同的 x 或相同的 y 坐标。

这可以编码为循环(伪代码，没有在编译器中测试它):

Point previous = null;
int vCount = 0, hCount = 0;
Iterator<Point> i = ...
List<Point> removablePoints = new ArrayList<>();
while (i.hasNext()) {
    Point current = i.next();
    if (previous != null) {
        if (current.x == previous.x) {
            ++hCount;
        } else {
            hCount = 1;
        }
        if (current.y == previous.y) {
            ++vCount;   
        } else {
            vCount = 1;
        }
   }
   if (vCount > 2) {
       removablePoints.add(current);
        --vCount;
   } else if (hCount > 2) {
       removablePoints.add(current);
       --hCount;
   }
   previous = current;
}

由于不可能在迭代器循环中轻松删除前一个点，因此只需将这些点收集在列表中并在循环后删除它们(未显示)。

原理很简单，只需计算有多少个连续的水平/垂直点，一旦发现两个以上，就删除中间的点(调整计数器以反射(reflect)删除的点)。