英文:
In Java, what is the best way of storing and testing if a point lies within a set of planes?
问题
我已经进行了大量的研究，试图找到最佳的方法来做这件事，但是无法想出一个好的和简单的解决方案。
在一个二维平面上，我有诸如[x1=10，y1=10，x2=30，y2=20]，[x1=50，y1=60，x2=80，y2=100]等值，这些值组成了许多不同的矩形（可以是大量的矩形）。我需要测试给定的点[x=15，y=15]是否位于这些矩形之一内，并获取它位于哪个矩形内。我还需要能够从列表中添加和删除单个矩形。在存储众多矩形并循环遍历它们以查看给定点是否位于其中之间，最佳且资源占用最少的方法是什么？
我尝试过创建一个对象，为每个矩形保存两个点，并将它们全部存储在一个Map中，尽管每秒钟在Map中循环遍历对象多次时，Java似乎跟不上。
有没有人知道更好的方法？
英文:
I have done a lot of research trying to find the best way of doing this but can't come up with a good and simple solution.
On a 2D plane, I have values such as [x1=10, y1=10, x2=30, y2=20], [x1=50, y1=60, x2=80, y2=100] and so on which make up numerous different rectangles (can be a large amount of rectangles). I need to test if a given point [x=15, y=15] lies within one of the rectangles and get which rectangle it lies within. I also need to be able to add and remove individual rectangles from the list. What is the best and least resource intensive way of storing the numerous rectangles and looping through them to see if a given point lies within one of them?
I have tried creating an object to hold two points for each rectangle and storing all of them in a Map although when looping through the objects in the Map several times per second java can't seem to keep up.
Does anyone know of a better way of doing this?
答案1
得分: 0
首先，如果要检查一个点是否在一个矩形内（位置是在矩形类中的一个点，宽度和高度也是如此）：
public boolean contains(Point point)
{
return (point.getX() >= position.getX() && point.getX() <= position.getX() + width)
&&
(point.getY() >= position.getY() && point.getY() <= position.getY() + height);
}
在检查点是否在矩形内的方面，你可以将矩形存储在四叉树（Quadtree）中：https://en.wikipedia.org/wiki/Quadtree
并且使用要测试的点搜索四叉树，四叉树将只返回靠近该点的矩形，因此进行的比较会显著减少。
英文:
First of all if want to check if a point is inside a rectangle (position is a point in a rectangle class, as are width, height):
public boolean contains(Point point)
{
return (point.getX() >= position.getX() && point.getX() <= position.getX() + width)
&&
(point.getY() >= position.getY() && point.getY() <= position.getY() + height);
}
in terms of checking if the point is inside of rectangles, you could store your rectangles in a Quadtree: https://en.wikipedia.org/wiki/Quadtree
and search the quadtree, with the point you want to test, the quadtree will only return rectangles near that point, so are doing significantly less comparisons
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论