java - 二维点集的环绕

Question

我有一个二维点列表。

例如:

x=c(4,3,3,5,6,6,4)

和

y=c(5,3,1,0,1,3,5)

这些二维点的图是

我想像这样绘制这个点集的包装器:

请注意，边界(包装)与最近点之间的垂直距离为 2 个单位。

请注意:我有许多点集，如上面的点集。我想对所有集合做同样的事情。

我想要这个边界多边形。谁能建议我如何做到这一点。

非常感谢任何想法，Janak。

Answer 1

要实现这一点，您可以使用这个简单的算法。
首先，我们需要坐标中心(红点)。
这可以通过添加所有 x 值并将结果除以它们的数量来完成，与 y 值相同。

下一步是计算一个包含当前坐标和中心点的矩形。 (不要忘记在此处添加 2 个单位的偏移量)

我们将对所有坐标执行此操作

此时我们已经可以停下来了。只需渲染所有这些矩形，然后在图片顶部渲染坐标，但让我们再改进一下。
我们实际上并不需要所有这些矩形，我们想要的是一个多边形来包裹这些点。这个多边形由我们的矩形和它们的边(蓝点)的交点定义。

请注意，我们只需要离中心最远的边和交点。
我们现在可以通过连接共享一个公共(public)坐标且是“邻居”的点来连接这些蓝点。

更新:

import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;

public class PolyWrapper {

    public static void main(String[] args){

        //your example coords:
        int[] x_coords = {4,3,3,5,6,6,4};
        int[] y_coords = {5,3,1,0,1,3,5};       

        //make sure the coordinates have the same length, else they won't match
        if(x_coords.length != y_coords.length){
            System.err.println("Bad parameters given. X and Y don't match!");
            System.exit(1);
        }

        //this will hold our points:
        ArrayList<Point2D> points = new ArrayList<>();
        for(int i = 0; i < x_coords.length; i++){
            Point2D p = new Point2D.Double(x_coords[i], y_coords[i]);
            points.add(p);
        }
        //lets get the center of all those points:
        final Point2D center = get_center(points);
        ArrayList<Rectangle2D> rectangles = new ArrayList<>();

        //now lets create those wrapping rectangles:
        for(Point2D p : points){
            Rectangle2D r = new Rectangle2D.Double();
            r.setFrameFromDiagonal(center, p);
            rectangles.add(r);
        }

        //now show the wrapping rectangles:
        for(Rectangle2D r : rectangles){
            System.out.println(r.toString());
        }


    }

    //this method returns the center of a list of points
    public static Point2D get_center(ArrayList<Point2D> points){
        double x = 0,y =0;
        for(Point2D p : points){
            x += p.getX();
            y += p.getY();
        }
        x = x / points.size();
        y = y / points.size();
        Point2D c = new Point2D.Double();
        c.setLocation(x, y);
        return c;
    }
}

下面是一些示例代码。我还没有找到时间来完成它，但由于你的问题真的很有趣，我会继续努力。
到目前为止，此代码计算中心点并围绕中心和给定坐标创建矩形。

这个输出提供了每个矩形的左上角，它的宽度和高度。
示例输出:

java.awt.geom.Rectangle2D$Double[x=4.0,y=2.5714285714285716,w=0.4285714285714288,h=2.4285714285714284]
java.awt.geom.Rectangle2D$Double[x=3.0,y=2.5714285714285716,w=1.4285714285714288,h=0.4285714285714284]
java.awt.geom.Rectangle2D$Double[x=3.0,y=1.0,w=1.4285714285714288,h=1.5714285714285716]
java.awt.geom.Rectangle2D$Double[x=4.428571428571429,y=0.0,w=0.5714285714285712,h=2.5714285714285716]
java.awt.geom.Rectangle2D$Double[x=4.428571428571429,y=1.0,w=1.5714285714285712,h=1.5714285714285716]
java.awt.geom.Rectangle2D$Double[x=4.428571428571429,y=2.5714285714285716,w=1.5714285714285712,h=0.4285714285714284]
java.awt.geom.Rectangle2D$Double[x=4.0,y=2.5714285714285716,w=0.4285714285714288,h=2.4285714285714284]

附注:我试图从这一点改进算法，但遇到了一个似乎很难解决的问题——也许我会就这个问题开始一个新的问题。
(这是关于带有蓝点的图片。一旦您拥有矩形及其交点的所有点，就很难找出我们的多边形实际上需要哪些结果点)。我认为我已接近解决方案，因此请留意我的下一次编辑。