二维点集的环绕

Question

我有一个二维点列表。

例如：

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

和

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

这些二维点的图是

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

注意，boundary(wrapper)到最近点的垂直距离是2个单位

注意：像上面的点集我有很多点集。我想对所有集合做同样的事情。

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

任何想法都非常感谢，Janak。

Answer 1

要实现这一点，您可以使用这个简单的算法。
首先，我们需要您坐标的 中心（红点）。
这可以通过添加所有 x-values 并将结果除以它们的数量来完成，与 y-values.
相同
下一步将是计算一个 包含当前坐标和中心 点的矩形。（不要忘记在此处添加 2 个单位的偏移量）

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

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

请注意，我们只需要离中心最远的边和交点。
我们现在可以通过连接共享一个公共坐标且 'neighbours'.

的点来连接这些蓝点

更新：

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;
    }
}

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

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

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]

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

Answer 2

使用Java，这就变得很简单了。该程序通过绘制结果来演示结果。轮廓也可以通过迭代 area.getPathIterator(at) 来获得，这将 return 所有的点，一个一个地

import java.awt.*;
import java.awt.geom.*;
import java.util.*;

public class PointSet {
public static final int W = 2;
Area area = new Area();

public void add( double x, double y ){
    area.add( new Area( new Rectangle2D.Double( x-W, y-W,2*W, 2*W ) ) );
}
public void plot(){
    Board board = new Board();
    board.go( area );
}
public static void main( String[] args ){
    PointSet ps = new PointSet();
    ps.add( 4, 5);
    ps.add( 3, 3);
    ps.add( 3, 1);
    ps.add( 5, 0);
    ps.add( 6, 1);
    ps.add( 6, 3);
    ps.plot();
}
}

和：

import java.awt.*;
import java.awt.geom.*;
import javax.swing.*;
import java.util.*;
public class Board extends JPanel {
Area area;
void go( Area area ) {
    this.area = area;
    JFrame frame = new JFrame("Circle Test");
    frame.getContentPane().add(this);
    frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
    repaint();
    frame.setPreferredSize(new Dimension(800,800));
    frame.pack();
    frame.setVisible(true);
}

public void paintComponent(Graphics g) {
  AffineTransform at = new AffineTransform();
  at.translate( 100, 100 );
  at.scale( 50, 50 );
  PathIterator pit = area.getPathIterator( at );
  Path2D path = new Path2D.Double();
  path.append( pit, true );
  Graphics2D g2d = (Graphics2D)g;
  g2d.draw( path );
}
}

二维点集的环绕

Wraping of two dimensional point set

java

algorithm

r