java - 2次元点と行列の間の最短距離を見つけるためのJavaアルゴリズム

Question

私はこの質問に数日間立ち往生しており、本当に助けを求めています.

(0.5,0.2) のような (1 を含まない 0-1) の範囲の 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;
    }

}