检查矩形列表中哪个矩形被单击的最快方法

Question

我有一个带有 x、y、宽度和高度的矩形对象。我有一个显示在屏幕上的这些矩形的列表。保证它们都不重叠。给定用户的点击位置（x 和 y 坐标），我想查看哪些矩形被点击（因为它们不重叠，最多可以点击一个矩形）。我显然可以浏览所有这些并检查每个用户是否单击它，但这非常慢，因为屏幕上有很多。当我在列表中插入一个新的矩形时，我可以使用某种比较来保持矩形的排序。是否有某种方法可以使用类似于二分搜索的方法来减少查找单击哪个 rect 所需的时间？注意：矩形可以是任何大小。谢谢：）编辑：要了解我在做什么，请访问koalastothemax.com

Answer 1

我能想出的最快方法绝对不是最有效的内存方法。这是通过利用摊销哈希表具有恒定查找时间这一事实来实现的。它会将矩形所具有的每个点映射到该矩形。这仅在您使用整数时才真正有效。如果您使用一点舍入，您也许可以让它与浮点数一起使用。

确保Point该类具有哈希码和等于函数。

public class PointCheck

{

    public Map<Point, Rect> pointMap;

    public PointCheck()

    {

        pointMap = new HashMap<>();

    }

    /**

     *  Map all points that contain the rectangle

     * to the rectangle.

     */

    public void addRect(Rect rect)

    {

        for(int i = rect.x; i < rect.x + rect.width; ++i)

        {

            for(int j = rect.y; j < rect.y + rect.height; ++i)

            {

                pointMap.put(new Point(i, j), rect);

            }

        }

    }

    /**

     *  Returns the rectangle clicked, null

     * if there is no rectangle.

     */

    public Rect checkClick(Point click)

    {

        return pointMap.get(click);

    }

}

编辑： 只是想我应该提到这一点：哈希映射值中保存的所有矩形都是对原始矩形的引用，它们不是克隆。

Answer 2

这在很大程度上取决于您的应用程序和细节，我们还不太清楚最佳解决方案是什么。但是，据我所知，我想说您可以制作一个指向矩形的二维数组。该二维数组将直接映射到屏幕上的像素。因此，如果您将数组设为 10x20，那么坐标 x 除以屏幕宽度乘以 10（转换为 int）将是第一个索引，而 y 划分的屏幕高度乘以 20 将是您的 y 索引。使用 x 和 y 索引，您可以直接映射到它指向的矩形。有些索引可能是空的，有些索引如果布局不完美，可能指向多个矩形，但这对我来说似乎是最简单的方法，我对应用程序不太了解。