如何实现具备矩形键约束的优化坐标型数据结构？

Awesome question! You’re looking for a spatial map structure that enforces non-overlapping rectangular keys and lets you look up values using a point coordinate. Let’s break down how to build this, step by step.

First, let’s outline the core components we need:

• A storage layer to hold our rectangles and their linked values (an array works well here, since we’ll need to check overlaps against existing entries)
• An assign method that validates no overlap before adding a new entry
• A retrieve method that finds which rectangle contains a given (x,y) point

Step 1: Build Helper Functions for Spatial Checks #

We need two key utility functions to make this work: one to check rectangle overlaps, and another to verify if a point sits inside a rectangle. Let’s use JavaScript for concrete examples (you can adapt this logic to any language):

// Check if two rectangles overlap
function doRectanglesOverlap(rectA, rectB) {
  // Rectangles don't overlap if one is fully left, right, above, or below the other
  return !(
    rectA.x + rectA.width < rectB.x ||
    rectA.x > rectB.x + rectB.width ||
    rectA.y + rectA.height < rectB.y ||
    rectA.y > rectB.y + rectB.height
  );
}

// Check if a point (x,y) lies inside a rectangle
function isPointInRectangle(x, y, rect) {
  return (
    x >= rect.x &&
    x <= rect.x + rect.width &&
    y >= rect.y &&
    y <= rect.y + rect.height
  );
}

Step 2: Wrap Logic into a Reusable Class #

Now we can package this into a class that behaves like your desired map structure:

class RectMap {
  constructor() {
    this.entries = []; // Stores objects: { rect: {x,y,width,height}, value: ... }
  }

  // Assign a value to a rectangle key; returns true if successful, false if overlap exists
  assign(rect, value) {
    // First check for overlaps with existing entries
    const hasOverlap = this.entries.some(entry => doRectanglesOverlap(entry.rect, rect));
    if (hasOverlap) {
      console.warn("Assignment failed: rectangle overlaps with an existing entry");
      return false;
    }
    // No overlap, add the new entry
    this.entries.push({ rect: {...rect}, value });
    return true;
  }

  // Retrieve the value for the rectangle containing (x,y); returns undefined if no match
  retrieve(x, y) {
    const matchingEntry = this.entries.find(entry => isPointInRectangle(x, y, entry.rect));
    return matchingEntry ? matchingEntry.value : undefined;
  }

  // Optional helper: Get all entries for debugging
  getAllEntries() {
    return [...this.entries];
  }
}

Step 3: Test It Out #

Let’s run through a quick example to confirm everything works as expected:

// Initialize our map
const myRectMap = new RectMap();

// Add non-overlapping rectangles
myRectMap.assign({ x: 0, y: 0, width: 10, height: 10 }, "Top-left zone");
myRectMap.assign({ x: 10, y: 0, width: 10, height: 10 }, "Top-right zone");

// Try adding an overlapping rectangle (should fail)
myRectMap.assign({ x: 5, y: 5, width: 10, height: 10 }, "Overlapping zone"); // Logs warning, returns false

// Look up values by point
console.log(myRectMap.retrieve(2, 2)); // Output: "Top-left zone"
console.log(myRectMap.retrieve(15, 5)); // Output: "Top-right zone"
console.log(myRectMap.retrieve(20, 20)); // Output: undefined

Performance Optimization Note #

If you plan to work with hundreds or thousands of rectangles, the O(n) checks in the basic implementation might get slow. For better performance, consider using a spatial partitioning structure like:

• A Quadtree: Divides the 2D space into quadrants, so you only check relevant regions for overlaps/lookups
• A grid-based index: Split your coordinate space into fixed-size cells, reducing the number of entries you need to compare

These tweaks will bring your operations down to O(log n) or better, depending on the structure.

内容的提问来源于stack exchange，提问作者Griffort