0

我在这个问题上停留了几天，真的很想得到一些帮助。

给我一个（0-1不包括1）范围内的二维点，如（0.5,0.2），以及N个其他点（也在0-1范围内）。问题的第一部分是实现“哑”算法，当给定某个点时，它会找到距离它最近的点，其复杂度为 O(N)。

我坚持的部分需要在 K 上构建一个矩阵 K，其中每个“单元”将包含属于该单元的点。完成后，当给定原始点时，我将需要仅在某些单元格而不是整个矩阵中搜索距离最短的点，这应该会产生更好的复杂性。

我最初的想法是划分点，以便每个块都有一个属于他的点的数组列表，然后以某种方式通过主块（原始点所属的那个）并继续通过它的邻居，但是实施起来并不是很成功。

我将非常感谢任何帮助/建议。

以下是我目前拥有的：

public class Point {
    private double x;
    private double y;
    private Block b;
    public Point(double x, double y)
    {
        this.x=x;
        this.y=y;
    }

    public Point(double x, double y, Block b) //consrtuctor for complex case
    {
        this.x=x;
        this.y=y;
        b.points.add(this);
    }
    public double getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public double getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }

    public double distance(Point p)
    {
        double res=0;
        res = Math.sqrt(Math.pow(this.x-p.getX(),2)+Math.pow(this.y-p.getY(),2));
        return res;

    }
}

import java.util.ArrayList;


public class Block {
    private int x;
    private int y;
    public ArrayList<Point> points;

    public Block(int x, int y) {

        points = new ArrayList<Point>();
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }

}

import java.util.Random;


public class ComplexCase {
    private Block[][] blockMat;

    public ComplexCase(int k, int n)
    {
        Random generator = new Random();
        Point p1;
        Block b1;
        double x,y;
        int bx1,by1;
        int t;
        t = 1/k;
        blockMat = new Block[k][k];
        for (int i =0;i<n;i++)
        {
            x = generator.nextDouble();
            y = generator.nextDouble();
            bx1 = (int) (x/t);
            by1 = (int) (y/t);
            b1 = new Block(bx1,by1);
            p1 = new Point(x,y,b1);
        }
    }
    public Block[][] getBlockMat() {
        return blockMat;
    }

    public void setBlockMat(Block[][] blockMat) {
        this.blockMat = blockMat;
    }

}
4

0 回答 0