Yuxu Ge
Article · 2024-09-30

Using R-Tree for 2D Point Deduplication and Visualization Optimization

R-Tree (Rectangle Tree) is a widely-used spatial indexing data structure that operates on principles similar to B-trees but is optimized for multidimensional space. The core idea of R-Tree is to approximate the spatial extent of data objects (such as points or polygons) using Minimum Bounding Rectangles (MBR). Each node in the tree is associated with a rectangular region that contains the extent of all objects in its child nodes or leaf nodes. During queries, nested rectangles allow for rapid pruning—discarding subtrees that do not intersect the query range—so only potentially relevant data objects are traversed.

Using R-Tree in Java

With an understanding of R-Tree principles, we can leverage existing libraries to simplify development. In Java, the open-source com.github.davidmoten:rtree library provides a convenient implementation. Maven projects can add this dependency:

<dependency>
    <groupId>com.github.davidmoten</groupId>
    <artifactId>rtree</artifactId>
    <version>0.9.3</version> <!-- 具体版本可根据需要选择 -->
</dependency>

Once imported, we can use the R-Tree data structure. This library implements R-Tree as a generic class, allowing us to specify the object type and the geometric extent type. For example, to store custom 2D point objects called MapPoint and use the library's Rectangle class (representing 2D axis-aligned rectangles) as the extent type, we create an R-Tree instance like this:

RTree<MapPoint, Rectangle> rtree = RTree.create();

Here, MapPoint is a custom data type representing a 2D point. Assume it has fields: id (unique identifier), x and y (coordinates), and optional attributes such as height and speed as needed. Rectangle is the library's class for describing rectangular extents. We can use it to represent a point's "collision area"—for a point, we treat it as a very small rectangle centered on the point (either zero-width/zero-height, or a square within a given radius).

The following code demonstrates inserting several MapPoint objects into R-Tree and creating corresponding rectangular extents. To simulate point overlap, we define a 1×1 square area for each point (using Geometries.rectangle(x1, y1, x2, y2)), so nearby points will have overlapping extent rectangles:

// 创建R-Tree实例
RTree<MapPoint, Rectangle> rtree = RTree.create();

// 添加示例数据点及其范围
rtree = rtree.add(EntryDefault.entry(new MapPoint(1, 1.0, 1.0, 1.0, 1.0),
                               Geometries.rectangle(1.0, 1.0, 2.0, 2.0)));
rtree = rtree.add(EntryDefault.entry(new MapPoint(2, 2.0, 2.0, 1.0, 1.0),
                               Geometries.rectangle(2.0, 2.0, 3.0, 3.0)));
rtree = rtree.add(EntryDefault.entry(new MapPoint(3, 1.5, 1.5, 1.0, 1.0),
                               Geometries.rectangle(1.5, 1.5, 2.5, 2.5)));

The code above inserts three points:

Notice that Point 1 and Point 3 have overlapping extents, and Point 2 and Point 3 also overlap. Point 1 and Point 2 touch only at the boundary (at point (2.0, 2.0)). Through these extent definitions, Point 3 collides with both Point 1 and Point 2.

Deduplication and Hiding Algorithm

With this data structure in place, we can implement 2D point deduplication and hiding logic. The problem: for any two or more overlapping points, keep only the point with the largest ID and mark others as hidden. Finally, output the list of all visible (non-hidden) points.

Algorithm outline: Leveraging R-Tree's fast overlap retrieval, we process all points as follows:

This ensures that for each group of overlapping points, only the one with the highest ID is retained. In implementation, we use a data structure (such as a Set) to track hidden point IDs, then filter the original list.

Code implementation: The following code demonstrates the algorithm:

// 用于记录需要隐藏的点
Set<MapPoint> pointsToHide = new HashSet<>();

// 获取R-Tree中所有点的条目集合
List<Entry<MapPoint, Rectangle>> entries = rtree.entries().toList().toBlocking().single();

// 遍历每个点条目
for (Entry<MapPoint, Rectangle> entry : entries) {
    MapPoint point = entry.value();
    Rectangle region = entry.geometry();

    // 查找与当前点区域相交的所有点（包括它自身）
    Iterable<Entry<MapPoint, Rectangle>> collisions = rtree.search(region).toBlocking().toIterable();
    // 找出相交点中ID最大的点
    MapPoint maxIdPoint = point;
    for (Entry<MapPoint, Rectangle> otherEntry : collisions) {
        MapPoint other = otherEntry.value();
        if (other.getId() > maxIdPoint.getId()) {
            maxIdPoint = other;
        }
    }
    // 如果当前点不是最大ID点，则将其标记为隐藏
    if (maxIdPoint.getId() != point.getId()) {
        pointsToHide.add(point);
    } else {
        // 当前点是此碰撞集合中ID最大的，隐藏所有其他与之碰撞的点
        for (Entry<MapPoint, Rectangle> otherEntry : collisions) {
            MapPoint other = otherEntry.value();
            if (other.getId() != point.getId()) {
                pointsToHide.add(other);
            }
        }
    }
}

// 收集所有未隐藏的（可见）点
List<MapPoint> visiblePoints = new ArrayList<>();
for (Entry<MapPoint, Rectangle> entry : entries) {
    MapPoint p = entry.value();
    if (!pointsToHide.contains(p)) {
        visiblePoints.add(p);
    }
}

// 输出结果
System.out.println("可见点 ID 列表: ");
for (MapPoint p : visiblePoints) {
    System.out.println("  - Point " + p.getId());
}

Here, we first retrieve all entries from the R-Tree using rtree.entries().toList().toBlocking().single(). Each entry contains a MapPoint and its corresponding Rectangle. For each point, rtree.search(region) finds all entries whose extents intersect. Since we included the point's own location when defining extents, the query result includes at least the current point itself.

Next, we iterate through the conflicting points to identify the one with maximum ID (maxIdPoint). If the current point is not the maximum-ID point, it should be hidden according to the rule; we add it to pointsToHide. Otherwise, if the current point is the maximum-ID point, we add all other intersecting points to pointsToHide (because their IDs are smaller).

Finally, by filtering out points in pointsToHide, we obtain visiblePoints, the list of all non-hidden points. Printing their IDs verifies correctness.

Verification

Using the sample data above, we can verify the algorithm. Initially we have three points:

Point 3's extent overlaps both Point 1 and Point 2. Thus, {Point 1, Point 2, Point 3} form one overlap group, with Point 3 having the maximum ID. Points 1 and 2 are marked hidden; only Point 3 remains visible. The algorithm output is:

可见点 ID 列表:
  - Point 3

If we add non-overlapping points—for example, Point 4 (ID=4, coordinates (10.0, 10.0)) far from the above region—it remains visible since it doesn't overlap with any other point.

Performance Analysis

R-Tree plays a crucial role in this problem. Without spatial indexing, finding overlapping points requires comparing each point against all others, giving O(N²) complexity (N = number of points). This becomes impractical for large N. With R-Tree, we exclude most irrelevant points, querying only spatially nearby points.

Each range query averages O(log N) complexity. If points are uniformly distributed and collision radii are small, most queries return few results, making the overall algorithm average O(N log N). Even in the worst case—all points clustered in one region—R-Tree performance may degrade, but the problem itself unavoidably approaches O(N²) complexity. Overall, R-Tree enables efficient deduplication for typical distributions, with benefits growing as data volume increases.

R-Tree's memory overhead is moderate, and insertion/query performance meets real-time requirements. In systems requiring frequent spatial collision detection or proximity queries (real-time map rendering, game engines), R-Tree often serves as a core data structure for performance gains.

Practical Applications

R-Tree-based 2D point deduplication and hiding has multiple real-world applications:

Conclusion

R-Tree efficiently solves the 2D point overlap problem by enabling rapid retrieval of spatial relationships among massive point datasets, avoiding expensive global traversal. Combined with sound algorithm logic, selective retention of points greatly improves visualization quality.

This technique has broad value in map visualization, game engines, and other spatial-data domains. In practice, the definition of "overlap" can be tuned to requirements (e.g., collision radius size or shape), and retention criteria adjusted (e.g., newest update vs. highest ID). Regardless, spatial indexing like R-Tree lets us manage vast 2D datasets with confidence, maintaining accuracy while improving system performance and user experience.

© 2026 Yuxu Ge ·