在 Java 中，存储和测试点是否位于一组平面内的最佳方法是什么？

Question

我做了很多研究试图找到最好的方法，但无法想出一个好的和简单的解决方案。

在二维平面上，我有 [x1=10, y1=10, x2=30, y2=20], [x1=50, y1=60, x2=80, y2=100]等等，它们组成了许多不同的矩形（可以是大量的矩形）。我需要测试给定点 [x=15, y=15] 是否位于其中一个矩形内，并获取它位于哪个矩形内。我还需要能够从列表中添加和删除单个矩形。存储大量矩形并循环遍历它们以查看给定点是否位于其中一个矩形内的最佳且资源占用最少的方法是什么？

我已经尝试创建一个对象来为每个矩形保留两个点并将它们全部存储在地图中，尽管每秒多次循环遍历地图中的对象时 java 似乎无法保持向上。

有谁知道更好的方法吗？

Answer 1

首先，如果要检查一个点是否在矩形内部（位置是矩形中的一个点class，宽度，高度也是如此）：

public boolean contains(Point point)
{

    return (point.getX() >= position.getX() && point.getX() <= position.getX() + width) 
            && 
            (point.getY() >= position.getY() && point.getY() <= position.getY() + height);
}

就检查点是否在矩形内部而言，您可以将矩形存储在四叉树中：https://en.wikipedia.org/wiki/Quadtree

然后搜索四叉树，用你想测试的点，四叉树只会在那个点附近 return 个矩形，所以做的比较少得多

在 Java 中，存储和测试点是否位于一组平面内的最佳方法是什么？

In Java, what is the best way of storing and testing if a point lies within a set of planes?

java

performance

bukkit