查找包含点的矩形-高效算法 [英] Find rectangles that contain point – Efficient Algorithm

问题描述

下午好。

我的情况：

• 在二维空间中。


• 输入：一组矩形（重叠的矩形）。
  
  
  
  
  • 矩形坐标为整数类型。
  
  
  • 矩形没有任何约束，大小和矩形位置（仅整数范围）。
  
  
  • 没有矩形的width = 0或height = 0。
  
  
  • In two-dimensional space.
  • Input: a set of rectangles (overlapping rectangles too).
    • Rectangles coordinates are integer type.
    • There are not any constraints on rectangle-size and rectangle-location (only extent of integer).
    • No rectangles have width=0 or height=0.

    问题：

    
    
    • 保持矩形的有效结构是什么？
    
    
    • 在这种情况下哪种算法有效？
      
      
      
      
      • 什么算法仅在不删除矩形的情况下有效？
      
      

      谢谢：-）。

      推荐答案

      R-树是适合此用例的最佳数据结构。 R树是用于空间访问方法（即索引诸如地理坐标，矩形或多边形之类的多维信息）的树数据结构。所有矩形的信息都可以树形形式存储，因此搜索将很容易

      R-Tree is the best data structure suitable for this use case. R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The information of all rectangles can be stored in tree form so searching will be easy

      维基百科页，简短的ppt 和研究论文将帮助您理解概念。

      Wikipedia page, short ppt and the research paper will help you understand the concept.

      这篇关于查找包含点的矩形-高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！