java - 实现这个最有效的方法是什么？

Question

我有一个 1 公里的正方形，我将其正反面均分为 100 米。

         __________y__________
         |         |         |
         |         |         |
         |         |         |
         |---------|---------| x
         |         |         |
         |         |         |
         |_________|_________|

基本上我正在制作一个像上面那样的正方形。我将它分成 100 平方米的正方形，分别位于 x 轴的正侧和负侧。然后我在各自的坐标中绘制每个点，我计划通过一堆 if/else 语句(至少 50 ，最多 100 )抛出一个 (x,y) 值，但我关心的是如何这会很贵。有没有更有效的方法来做我想做的事情？

这是我计划如何做的一个例子......

              if(tlat < lat && tlat > lat - 89930.7){
            //point is within 100 meters on lat
            //On the NEGATIVE SIDE.
            if(tlng > lng && tlng < lng + 147999.8){
            //point is within 100 meters on lat NEGATIVE &&
            //withing 100 meters on lng POSITIVE
                layers.addcube(highlng100p, lowlng100p, yhigh, ylow, highlat100p, lowlat100p);
                highlng100p = highlng100p + 5;
                lowlng100p = lowlng100p + 5;
                highlat100p = highlat100p + 5;
                lowlat100p = lowlat100p + 5;
            }else if(tlng < lng && tlng > lng - 147999.8){
                //point is within 100 meters on lat NEGATIVE &&
                //withing 100 meters on lng NEGATIVE
                layers.addcube(highlat100n, lowlat100n, yhigh, ylow, highlng100n, lowlng100n);
                highlat100n = highlat100n + 5;
                lowlat100n = lowlat100n + 5;
                highlng100n = highlng100n + 5;
                lowlat100n = lowlat100n + 5;
            }else if(tlng > lng && tlng < lng + 295999.6){
                //point is within 200 meters on lat NEGATIVE &&
                //withing 200 meters on lng POSITIVE
                layers.addcube(highlat200n, lowlat200n, yhigh, ylow, highlng200p, lowlng200n);
                highlat200n = highlat200n + 5;
                lowlat200n = lowlat200n + 5;
                highlng200p = highlng200p + 5;
                lowlng200p = lowlng200p + 5;
            }else if(tlng < lng && tlng > lng - 295999.6){
                //point is within 200 meters on lat NEGATIVE &&
                //withing 200 meters on lng NEGATIVE
                layers.addcube(highlat200n, lowlat200n, yhigh, ylow, highlng200n, lowlng200n);
                highlat200n = highlat200n + 5;
                lowlat200n = lowlat200n + 5;
                highlng200n = highlng200n + 5;
                lowlng200n = lowlng200n + 5;
            }else if(tlng > lng && tlng < lng + 443999.4){
                //point is within 300 meters on lat NEGATIVE &&
                //withing 300 meters on lng POSITIVE
                layers.addcube(highlat300n, lowlat300n, yhigh, ylow, highlng300p, lowlng300p);
                highlat300n = highlat300n + 5;
                lowlat300n = lowlat300n + 5;
                highlng300p = highlng300p + 5;
                lowlng300p = lowlng300p + 5;
            }else if(tlng < lng && tlng > lng - 443999.4){
                //point is within 300 meters on lat NEGATIVE &&
                //withing 300 meters on lng NEGATIVE
                layers.addcube(highlat300n, lowlat300n, yhigh, ylow, highlng300n, lowlng300n);
                highlat300n = highlat300n + 5;
                lowlat300n = lowlat300n + 5;
                highlng300n = highlng300n + 5;
                lowlng300n = lowlng300n + 5;
            } else if(tlng > lng && tlng < lng + 591999.2){
                //point is within 400 meters on lng
                //on the POSITIVE SIDE
                layers.addcube(highlat400n, lowlat400n, yhigh, ylow, highlng400p, lowlng400p);
                highlat400n = highlat400n + 5;
                lowlat400n = lowlat400n + 5;
                highlng400p = highlng400p + 5;
                lowlng400p = lowlng400p + 5;
            }else if(tlng < lng && tlng > lng - 591999.2){
                //point is within 400 meters on lng
                //on the NEGATIVE SIDE
                layers.addcube(highlat400n, lowlat400n, yhigh, ylow, highlng400n, lowlng400n);
                highlat400n = highlat400n + 5;
                lowlat400n = lowlat400n + 5;
                highlng400n = highlng400n + 5;
                lowlng400n = lowlng400n + 5;
            }else if(tlng > lng && tlng < lng + 739999){
                //point is within 500 meters on lng
                //on the POSITIVE SIDE
                layers.addcube(highlat500n, lowlat500n, yhigh, ylow, highlng500p, lowlng500p);
                highlat500n = highlat500n + 5;
                lowlat500n = lowlat500n + 5;
                highlng500p = highlng500p + 5;
                lowlng500p = lowlng500p + 5;
            }else if(tlng < lng && tlng > lng - 739999){
                //point is within 500 meters on lng
                //on the NEGATIVE SIDE
                layers.addcube(highlat500n, lowlat500n, yhigh, ylow, highlng500n, lowlng500n);
                highlat500n = highlat500n + 5;
                lowlat500n = lowlat500n + 5;
                highlng500n = highlng500n + 5;
                lowlng500n = lowlng500n + 5;
            }
            } 

如果有人可以帮助我使我想做的事情更有效率，我将不胜感激! 谢谢，

Answer 1

一种方法是制作一个单元格网格，并使用点到原点的距离和单元格的大小来计算出该点进入哪个单元格。计算单元的公式是 O(1) - 因此其效率不依赖于网格的大小。这是对某些代码的粗略尝试 - 未编译和未经测试，因此您可能需要修改它才能使其正常工作:

public class SquareGrid
{
    /** Lower, left corner of the grid */
    private Point2D m_origin;
    private double  m_cellSize;
    private List<List<List<Point2D>>> m_cells;

    public SquareGrid(Point2D origin, int numberOfCellsPerSide, double cellSize)
    {
        m_origin = origin;
        m_cellSize = cellSize;
        m_cells = new ArrayList<List<List<Point2D>>>(numberOfCellsPerSide);

        for (int i = 0; i < numberOfCellsPerSide; i++)
        {
            List<List<Point2D>> row = new ArrayList<List<Point2D>>(numberOfCellsPerSide);
            m_cells.add(row);

            for (int j = 0; j < numberOfCellsPerSide; j++)
            {
                row.add(new ArrayList<Point2D>>());
            }
        }
    }

    public void add(Point2D point)
    {
        int xCell = Math.floor((point.getX() - m_origin.getX()) / m_cellSize);
        int yCell = Math.floor((point.getY() - m_origin.getY()) / m_cellSize);

        m_cells.get(xCell).get(yCell).add(point);
    }
}

如果您希望原点位于网格中间，则需要调整添加算法，并决定如何处理每侧奇数个单元格。

专业人士可能会使用 R 树或其他一些可用于构建高效空间索引的数据结构，而不是网格。