Map POI Label Occlusion Solution Using 2D Collision Detection and A* Pathfinding

When displaying points of interest (POI) on a map, the proximity of POIs often leads to severe label occlusion, making it impossible for users to view all relevant information and degrading visual experience.

The problem is reproduced with five closely spaced POIs whose labels overlap, as shown in the accompanying screenshots. The scene analysis identifies three characteristics: the task is lightweight with high timeliness requirements, the area of interest is limited to a fixed radius around the community, and the map scale does not change nor does it involve POI clustering.

To resolve the occlusion, the solution is divided into two main steps: (1) arrange POI labels to avoid mutual overlap using 2D collision‑detection algorithms, and (2) determine connector lines between each POI and its label using the A‑Star path‑finding algorithm. The front‑end JavaScript API requests a back‑end service that returns the final label positions and connector paths.

2D Collision Detection Algorithms

Four collision‑detection cases are covered:

Circle‑circle detection – two circles collide if the distance between their centers is less than the sum of their radii. Example code:

math.sqrt(math.pow(circleA.x - circleB.x, 2) + math.pow(circleA.y - circleB.y, 2)) < circleA.radius + circleB.radius

Axis‑aligned rectangle‑rectangle detection – collision is determined by comparing the x and y extents of the rectangles. Example code:

rect1.x < rect2.x + rect2.width and rect1.x + rect1.width > rect2.x and rect1.y < rect2.y + rect2.height and rect1.y + rect1.height > rect2.y

Circle‑rectangle detection – find the closest point on the rectangle to the circle centre and test the distance against the circle radius.

Separating Axis Theorem (SAT) for arbitrary convex polygons – project both polygons onto each edge normal; if any projection interval does not overlap, the polygons are not colliding.

A‑Star Path‑Finding Algorithm

A‑Star computes the shortest path on a grid by combining the actual cost from the start node (g) and a heuristic estimate to the goal (h), typically Manhattan distance. The algorithm iteratively expands the node with the lowest f = g + h, updates neighbour costs, and stops when the goal is reached or the open list is empty.

Implementation in Python (OpenCV & NumPy)

The workflow is:

Calculate the centroid of all POI coordinates.

Determine a radius that covers the farthest POI from the centroid.

Generate equally spaced points on the circle to serve as candidate label anchors.

Map each anchor to a rectangle position based on its angular sector, using collision checks to keep rectangles inside the map bounds.

Pair each POI with the nearest rectangle (starting with the farthest POI) and draw a connector line using A‑Star.

Key code snippets:

def get_centroid(points):
    """Compute centroid of a list of (x, y) points"""
    xs, ys = [], []
    for p in points:
        xs.append(p[0])
        ys.append(p[1])
    return [int(np.mean(xs)), int(np.mean(ys))]

def euclidean_dis(p_start, p_end):
    """Euclidean distance between two points"""
    return np.linalg.norm(np.array(p_start) - np.array(p_end))

def get_equal_points(centroid, points, radius):
    """Compute equally spaced points on a circle"""
    equal_points = []
    trig_values = []
    for i in range(len(points)):
        cos = math.cos(2 * math.pi * i / len(points))
        sin = math.sin(2 * math.pi * i / len(points))
        x = int(centroid[0] + radius * cos)
        y = int(centroid[1] + radius * sin)
        equal_points.append([x, y])
        trig_values.append([cos, sin])
    return equal_points, trig_values

def get_rectangles(equal_points, trig_values):
    """Determine rectangle positions from equal points and their trig values"""
    rectangles = []
    for [x, y], [cos, sin] in zip(equal_points, trig_values):
        # Example for top‑side midpoint
        if abs(sin) < 1e-9 and abs(cos - 1) < 1e-9:
            delta_x = -int(DeblockConfig.label_W / 2)
            delta_y = 0
            tl = [x + delta_x, y + delta_y]
            br = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
            rectangles.append(tl + br)
            continue
        # Additional cases for other sides and corners omitted for brevity
    # Boundary checks omitted for brevity
    return rectangles

After placing the rectangles and drawing the A‑Star connectors, the final map shows non‑overlapping labels with clear POI‑label relationships. The approach is fast, simple, and accurate, though it may produce long connector lines and reduced visual compactness in dense scenarios.

Conclusion

The presented method dramatically improves map readability by eliminating label occlusion. Future work may explore divide‑and‑conquer strategies for further optimization.