java - 在 X-Y 平面上查找附近的矩形

Question

我在 x-y 平面上有几个矩形。有一个引用矩形。引用矩形的位置是可变的。我需要有效的方法来找到

• 在引用矩形的左侧找到的第一个矩形。
• 在引用矩形右侧找到的第一个矩形。
• 在引用矩形的顶部找到的第一个矩形。
• 在引用矩形的底部找到的第一个矩形。

伪代码或 Java 代码都可以。 强调比占用空间更快的代码。
解决一侧将解决其他 3 个方面。 比方说，我们需要找到落在“REFERENCE RECT”左侧的最近矩形的列表。 “REFERENCE RECT”是可移动的。 所有其他矩形在计算时都是静止的。

附言。每个框都可以是“REFERENCE RECT”。一次将一个框添加到 X-Y 平面。

Answer 1

此伪代码在设置过程中可能不会很快 (O(N^2))，但是一旦构建了 NearestBoxes，它将击败其他任何东西(因为它不必重新计算任何事物)。当心拼写错误 - 我还没有对此进行测试。

public enum RPos { Up, Down, Left, Right };

public class Box {
    int x1, x2, y1, y2;        
    boolean isRelative(b, RPos rp) {
       // returns true if b can be said to be "rp" 
       // (say, left) of this box
    }
    double dist(Box b, RPos rp) {
       // assumes non-overlapping
       // add some simple trig here:
       //   if boxes adjacent in chosen direction, distance 
       //      (if Right, then x2-p.x1, ...)
       //   if boxes not adjacent, then euclidean distance between 
       //   nearest corners.
    }
}

class NearestBoxes {    

    HashMap<RPos, HashMap<Box, TreeMap<Double, ArrayList<Box>>>> 
        = new HashMap<>();

    public NearestBoxes(List<Box> boxes) {
       for (RPos rp : RPos.values) {
          nearest.put(rp, 
             new HashMap<Box, TreeMap<Double, ArrayList<Box>>>();
          for (Box a : boxes) {
             TreeMap<Double, ArrayList<Box>> n = 
                new TreeMap<Double, ArrayList<Box>>());
             nearest.get(rp).put(a, n);                    
             for (Box b : boxes) {
                 if (a.isRelative(b, rp)) {
                    double d = a.dist(b, rp);                        
                    if (d == n.firstKey()) {
                       n.get(d).add(b);
                    } else if (d < n.firstKey()) {
                       n.put(d, new ArrayList());
                       n.get(d).add(b);
                    }
                 }
             }
          }
       }
    }

    public List<Box> getNearest(Box b, RPos rp) {
       TreeMap<Double, ArrayList<Box>> n = nearest.get(rp).get(b);
       return (n.isEmpty()) ? new ArrayList<Box>() 
                            : n.get(n.firstKey());           
    }
}