查找出来，如果​​点内N（可能是重叠）在不到Ø矩形一（N） [英] Find out if point is inside one of N (possibly overlapping) rectangles in less than O(N)

问题描述

我有一个形象，我想显示工具提示当鼠标移动到某个矩形区域。该矩形区域可以达到1000。然而，只是检查每个矩形如果点在里面，这是O（N），移动鼠标时，使界面反应迟钝。

I have an image, and I want to show tooltips when mouse moves over certain rectangular areas. The rectangular areas can be up to 1000. However, just checking each rectangle if the point is in it, which is O(N), makes the interface unresponsive when moving the mouse.

有没有办法做到这一点，在不到O（N）？我可以事先矩形整理（我假定这将需要）。该矩形可能是（很少）重叠，但不超过4-5矩形可以重叠同一地区。在这种情况下，我可能需要得到所有的矩形的列表，但即使是任何人仍然是不够好。

Is there a way to do it in less than O(N)? I can sort the rectangles beforehand (I'm assuming it would be needed). The rectangles might be (very rarely) overlapping, but no more than 4-5 rectangles can overlap the same area. In that case I might need to get a list of all the rectangles, but even just any of them would still be good enough.

但我猜想，这个问题已经解决了窗口管理器等。

But I'm assuming that this problem has already been solved by window managers, etc.

推荐答案

这听起来像你想要一个的 R树，然后查询的。有几个实现可用的：

It sounds like you want to be storing your rectangles within an R-Tree and then querying that. There are a few implementations available:

• JTS拓扑套房（爪哇）
• 网络拓扑套件​​（.NET）
• GeoTools （.NET）

• JTS Topology Suite (Java)
• Net Topology Suite (.Net)
• GeoTools (.Net)

检查他们STRtree类。

Check out their STRtree classes.

这篇关于查找出来，如果​​点内N（可能是重叠）在不到Ø矩形一（N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！