mdmitry1 · December 9, 2025 12:10
diff --git a/quad_ex.py b/quad_ex.py
 #!/usr/bin/python3.12
 def visualize_quadtree(quadtree, points, query_rect=None, found_points=None,
                       filename="quadtree", title="Quadtree Visualization"):
    """Visualize the quadtree structure with points."""
    fig, ax = plt.subplots(figsize=(12, 12))
    
    # Draw all quadtree boundaries
    boundaries = quadtree.get_all_boundaries()
    for boundary in boundaries:
        x = boundary.x - boundary.width/2
        y = boundary.y - boundary.height/2
        rect = patches.Rectangle((x, y), boundary.width, boundary.height,
                                 linewidth=1, edgecolor='gray',
                                 facecolor='none', alpha=0.5)
        ax.add_patch(rect)
    
    # Draw all points
    for point in points:
        ax.plot(point.x, point.y, 'bo', markersize=4, alpha=0.6)
    
    # Draw query range if provided
    if query_rect:
        x = query_rect.x - query_rect.width/2
        y = query_rect.y - query_rect.height/2
        query_patch = patches.Rectangle((x, y), query_rect.width, query_rect.height,
                                       linewidth=2, edgecolor='red',
                                       facecolor='red', alpha=0.1)
        ax.add_patch(query_patch)
    
    # Highlight found points
    if found_points:
        for point in found_points:
            ax.plot(point.x, point.y, 'ro', markersize=8, alpha=0.8)
    
    # Set bounds
    boundary = quadtree.boundary
    margin = boundary.width * 0.05
    ax.set_xlim(boundary.x - boundary.width/2 - margin,
                boundary.x + boundary.width/2 + margin)
    ax.set_ylim(boundary.y - boundary.height/2 - margin,
                boundary.y + boundary.height/2 + margin)
    
    ax.set_aspect('equal')
    ax.set_title(title, fontsize=16, fontweight='bold')
    ax.set_xlabel('X', fontsize=12)
    ax.set_ylabel('Y', fontsize=12)
    ax.grid(True, alpha=0.3)
    
    # Add info
    info_text = f"Points: {len(points)}\nQuadrants: {quadtree.count_nodes()}"
    if found_points:
        info_text += f"\nFound: {len(found_points)}"
    ax.text(0.02, 0.98, info_text, transform=ax.transAxes,
            verticalalignment='top', bbox=dict(boxstyle='round',
            facecolor='wheat', alpha=0.5), fontsize=10)
    
    plt.tight_layout()
    filepath = os.path.join(OUTPUT_DIR, f"{filename}.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    return filepath


 def example_6_rectangles_collision():
    """Example 6: Collision detection with rectangles (circuit components)."""
    print("\n" + "="*70)
    print("EXAMPLE 6: Rectangle Collision Detection (Circuit Components)")
    print("="*70)
    
    print("\nScenario: Detecting overlapping circuit components")
    print("Use case: Design Rule Checking, component placement validation")
    
    # Create quadtree for circuit board
    boundary = Rectangle(500, 500, 1000, 1000)
    qt = Quadtree(boundary, capacity=6)
    
    # Create circuit components as rectangles
    random.seed(200)
    components = []
    
    print("\nPlacing circuit components...")
    
    # Add various sized components
    component_types = [
        ("Resistor", 20, 8),
        ("Capacitor", 15, 15),
        ("IC", 40, 40),
        ("Transistor", 12, 12),
        ("Connector", 30, 10)
    ]
    
    for i in range(80):
        comp_type, width, height = random.choice(component_types)
        x = random.uniform(50, 950 - width)
        y = random.uniform(50, 950 - height)
        
        rect = Rect(x, y, width, height, data=f"{comp_type}_{i}")
        components.append(rect)
        qt.insert_rect(rect)
    
    print(f"Placed {len(components)} components")
    print(f"Quadtree nodes: {qt.count_nodes()}")
    
    # Visualize all components
    filepath = visualize_quadtree_rects(qt, components,
                                       filename="6a_circuit_components_rects",
                                       title="Circuit Board with Component Rectangles")
    print(f"✓ Saved: {filepath}")
    
    # Query: Find components in a specific region
    query_region = Rectangle(400, 600, 250, 250)
    found = qt.query_rects(query_region)
    
    print(f"\nCollision detection query:")
    print(f"  Region: centered at (400, 600), size 250×250")
    print(f"  Found {len(found)} intersecting components")
    
    filepath = visualize_quadtree_rects(qt, components, query_region, found,
                                       filename="6b_collision_detection",
                                       title="Collision Detection - Green region finds overlapping components")
    print(f"✓ Saved: {filepath}")
    
    print("\nApplications:")
    print("  • Design Rule Checking: Ensure minimum spacing")
    print("  • Placement validation: Detect overlaps before manufacturing")
    print("  • Routing: Find components to connect")
    print("  • Interference analysis: Check EM compatibility")


 def example_7_polygon_operations():
    """Example 7: Polygon operations - realistic semiconductor masks."""
    print("\n" + "="*70)
    print("EXAMPLE 7: Polygon Operations (Semiconductor Masks)")
    print("="*70)
    
    print("\nScenario: Managing polygon masks for photolithography")
    print("Use case: Mask layer operations, design rule checking")
    
    # Create quadtree
    boundary = Rectangle(5000, 5000, 10000, 10000)  # 10µm x 10µm chip
    qt = Quadtree(boundary, capacity=8)
    
    # Create realistic polygon patterns (metal traces, vias, pads)
    random.seed(300)
    polygons = []
    
    print("\nCreating semiconductor mask polygons...")
    
    # Metal traces (long thin rectangles)
    for i in range(30):
        x = random.uniform(100, 9800)
        y = random.uniform(100, 9800)
        if random.random() < 0.5:
            # Horizontal trace
            width = random.uniform(200, 800)
            height = random.uniform(5, 15)
        else:
            # Vertical trace
            width = random.uniform(5, 15)
            height = random.uniform(200, 800)
        
        rect = Rect(x, y, width, height, data=f"metal_trace_{i}")
        polygons.append(rect)
        qt.insert_rect(rect)
    
    # Contact pads (squares)
    for i in range(40):
        x = random.uniform(100, 9900)
        y = random.uniform(100, 9900)
        size = random.uniform(30, 80)
        
        rect = Rect(x, y, size, size, data=f"contact_pad_{i}")
        polygons.append(rect)
        qt.insert_rect(rect)
    
    # Vias (small squares)
    for i in range(50):
        x = random.uniform(100, 9990)
        y = random.uniform(100, 9990)
        size = random.uniform(3, 10)
        
        rect = Rect(x, y, size, size, data=f"via_{i}")
        polygons.append(rect)
        qt.insert_rect(rect)
    
    print(f"Created {len(polygons)} polygons:")
    print(f"  - 30 metal traces")
    print(f"  - 40 contact pads")
    print(f"  - 50 vias")
    print(f"Quadtree nodes: {qt.count_nodes()}")
    
    # Visualize full layout
    filepath = visualize_quadtree_rects(qt, polygons,
                                       filename="7a_semiconductor_masks",
                                       title="Semiconductor Mask Layout (Metal layer)")
    print(f"✓ Saved: {filepath}")
    
    # Design rule check: Find polygons too close to a critical trace
    critical_trace = Rectangle(3000, 5000, 600, 600)
    nearby = qt.query_rects(critical_trace)
    
    print(f"\nDesign Rule Check:")
    print(f"  Checking proximity to critical region")
    print(f"  Found {len(nearby)} polygons within check region")
    print(f"  Application: Ensure minimum spacing rules")
    
    filepath = visualize_quadtree_rects(qt, polygons, critical_trace, nearby,
                                       filename="7b_design_rule_check",
                                       title="Design Rule Check - Finding polygons near critical trace")
    print(f"✓ Saved: {filepath}")
    
    # Benchmark: Compare with brute force
    start = time.time()
    for _ in range(100):
        found_qt = qt.query_rects(critical_trace)
    qt_time = (time.time() - start) / 100
    
    # Brute force check
    critical_as_rect = Rect(
        critical_trace.x - critical_trace.width/2,
        critical_trace.y - critical_trace.height/2,
        critical_trace.width,
        critical_trace.height
    )
    
    start = time.time()
    for _ in range(100):
        found_bf = [p for p in polygons if p.intersects(critical_as_rect)]
    bf_time = (time.time() - start) / 100
    
    print(f"\nPerformance:")
    print(f"  Quadtree: {qt_time*1000:.3f} ms")
    print(f"  Brute force: {bf_time*1000:.3f} ms")
    print(f"  Speedup: {bf_time/qt_time:.1f}x")
    
    print("\nSemiconductor applications:")
    print("  • Mask layer collision detection")
    print("  • Design rule verification (spacing, width)")
    print("  • Polygon boolean operations (union, intersection)")
    print("  • Optical proximity correction (OPC)")
    print("  • Fast spatial queries for multi-million polygon designs")
 """
 Quadtree Data Structure Examples
 Demonstrates spatial indexing for circuit design and polygon operations

 Quadtrees are hierarchical spatial data structures that recursively 
 partition 2D space into four quadrants. Essential for:
 - Fast spatial queries (range search, nearest neighbor)
 - Collision detection
 - Circuit layout optimization
 - Polygon intersection detection

 Install: pip install pyquadtree2
 Or we'll implement from scratch if not available
 """

 import random
 import time
 import matplotlib.pyplot as plt
 import matplotlib.patches as patches
 from collections import namedtuple
 import os

 # Create output directory
 OUTPUT_DIR = "quadtree_illustrations"
 if not os.path.exists(OUTPUT_DIR):
    os.makedirs(OUTPUT_DIR)

 # Try to import pyquadtree2, fall back to custom implementation
 try:
    from pyquadtree2 import Index as QuadtreeIndex
    HAS_PYQUADTREE = True
 except ImportError:
    HAS_PYQUADTREE = False
    print("Note: pyquadtree2 not installed. Using custom implementation.")
    print("To install: pip install pyquadtree2")


 # Custom Quadtree Implementation (educational)
 class Point:
    """Represents a 2D point."""
    def __init__(self, x, y, data=None):
        self.x = x
        self.y = y
        self.data = data
    
    def __repr__(self):
        return f"Point({self.x}, {self.y})"


 class Rect:
    """Represents a rectangle (for circuit components)."""
    def __init__(self, x, y, width, height, data=None):
        self.x = x  # Bottom-left x
        self.y = y  # Bottom-left y
        self.width = width
        self.height = height
        self.data = data
    
    @property
    def center(self):
        """Get center point of rectangle."""
        return Point(self.x + self.width/2, self.y + self.height/2)
    
    def intersects(self, other):
        """Check if this rectangle intersects another."""
        return not (self.x + self.width < other.x or
                   other.x + other.width < self.x or
                   self.y + self.height < other.y or
                   other.y + other.height < self.y)
    
    def __repr__(self):
        return f"Rect({self.x}, {self.y}, {self.width}x{self.height})"


 class Rectangle:
    """Represents a bounding box for quadtree boundaries."""
    def __init__(self, x, y, width, height):
        self.x = x  # Center x
        self.y = y  # Center y
        self.width = width
        self.height = height
    
    def contains(self, point):
        """Check if point is inside rectangle."""
        return (self.x - self.width/2 <= point.x <= self.x + self.width/2 and
                self.y - self.height/2 <= point.y <= self.y + self.height/2)
    
    def intersects(self, range_rect):
        """Check if this rectangle intersects with another."""
        return not (range_rect.x - range_rect.width/2 > self.x + self.width/2 or
                   range_rect.x + range_rect.width/2 < self.x - self.width/2 or
                   range_rect.y - range_rect.height/2 > self.y + self.height/2 or
                   range_rect.y + range_rect.height/2 < self.y - self.height/2)
    
    def intersects_rect(self, rect):
        """Check if this boundary intersects with a Rect object."""
        rect_left = rect.x
        rect_right = rect.x + rect.width
        rect_bottom = rect.y
        rect_top = rect.y + rect.height
        
        bound_left = self.x - self.width/2
        bound_right = self.x + self.width/2
        bound_bottom = self.y - self.height/2
        bound_top = self.y + self.height/2
        
        return not (rect_right < bound_left or
                   rect_left > bound_right or
                   rect_top < bound_bottom or
                   rect_bottom > bound_top)
    
    def __repr__(self):
        return f"Rect({self.x}, {self.y}, {self.width}x{self.height})"


 class Quadtree:
    """
    Custom Quadtree implementation for educational purposes.
    
    A quadtree recursively divides 2D space into 4 quadrants:
    - NW (northwest) - top-left
    - NE (northeast) - top-right
    - SW (southwest) - bottom-left
    - SE (southeast) - bottom-right
    
    Can store both points and rectangles.
    """
    
    def __init__(self, boundary, capacity=4):
        """
        Args:
            boundary: Rectangle defining the spatial bounds
            capacity: Max items before subdivision
        """
        self.boundary = boundary
        self.capacity = capacity
        self.points = []
        self.rectangles = []  # Store rectangle objects
        self.divided = False
        
        # Child quadrants (created on subdivision)
        self.northwest = None
        self.northeast = None
        self.southwest = None
        self.southeast = None
    
    def subdivide(self):
        """Divide this quadrant into 4 sub-quadrants."""
        x = self.boundary.x
        y = self.boundary.y
        w = self.boundary.width / 2
        h = self.boundary.height / 2
        
        # Create 4 child quadrants
        nw_boundary = Rectangle(x - w/2, y + h/2, w, h)
        self.northwest = Quadtree(nw_boundary, self.capacity)
        
        ne_boundary = Rectangle(x + w/2, y + h/2, w, h)
        self.northeast = Quadtree(ne_boundary, self.capacity)
        
        sw_boundary = Rectangle(x - w/2, y - h/2, w, h)
        self.southwest = Quadtree(sw_boundary, self.capacity)
        
        se_boundary = Rectangle(x + w/2, y - h/2, w, h)
        self.southeast = Quadtree(se_boundary, self.capacity)
        
        self.divided = True
    
    def insert(self, point):
        """Insert a point into the quadtree."""
        # Ignore if point is outside boundary
        if not self.boundary.contains(point):
            return False
        
        # If capacity not reached, add here
        if len(self.points) < self.capacity:
            self.points.append(point)
            return True
        
        # Otherwise, subdivide and redistribute
        if not self.divided:
            self.subdivide()
        
        # Try to insert into children
        if self.northwest.insert(point):
            return True
        if self.northeast.insert(point):
            return True
        if self.southwest.insert(point):
            return True
        if self.southeast.insert(point):
            return True
        
        return False
    
    def insert_rect(self, rect):
        """
        Insert a rectangle into the quadtree.
        Uses rectangle's center point for placement.
        """
        center = rect.center
        
        # Check if center is in this boundary
        if not self.boundary.contains(center):
            return False
        
        # If capacity not reached, add here
        if len(self.rectangles) < self.capacity:
            self.rectangles.append(rect)
            return True
        
        # Otherwise, subdivide and redistribute
        if not self.divided:
            self.subdivide()
        
        # Try to insert into children
        if self.northwest.insert_rect(rect):
            return True
        if self.northeast.insert_rect(rect):
            return True
        if self.southwest.insert_rect(rect):
            return True
        if self.southeast.insert_rect(rect):
            return True
        
        return False
    
    def query(self, range_rect, found=None):
        """
        Find all points within a rectangular range.
        This is the key operation that makes quadtrees fast!
        """
        if found is None:
            found = []
        
        # If range doesn't intersect boundary, return early
        if not self.boundary.intersects(range_rect):
            return found
        
        # Check points in this quadrant
        for point in self.points:
            if range_rect.contains(point):
                found.append(point)
        
        # Recursively search children if divided
        if self.divided:
            self.northwest.query(range_rect, found)
            self.northeast.query(range_rect, found)
            self.southwest.query(range_rect, found)
            self.southeast.query(range_rect, found)
        
        return found
    
    def query_rects(self, range_rect, found=None):
        """
        Find all rectangles that intersect with the query rectangle.
        Critical for collision detection in circuit design.
        """
        if found is None:
            found = []
        
        # If range doesn't intersect boundary, return early
        if not self.boundary.intersects_rect(Rect(
            range_rect.x - range_rect.width/2,
            range_rect.y - range_rect.height/2,
            range_rect.width,
            range_rect.height)):
            return found
        
        # Check rectangles in this quadrant
        query_as_rect = Rect(
            range_rect.x - range_rect.width/2,
            range_rect.y - range_rect.height/2,
            range_rect.width,
            range_rect.height
        )
        
        for rect in self.rectangles:
            if rect.intersects(query_as_rect):
                found.append(rect)
        
        # Recursively search children if divided
        if self.divided:
            self.northwest.query_rects(range_rect, found)
            self.northeast.query_rects(range_rect, found)
            self.southwest.query_rects(range_rect, found)
            self.southeast.query_rects(range_rect, found)
        
        return found
    
    def count_nodes(self):
        """Count total number of nodes (for visualization)."""
        count = 1
        if self.divided:
            count += self.northwest.count_nodes()
            count += self.northeast.count_nodes()
            count += self.southwest.count_nodes()
            count += self.southeast.count_nodes()
        return count
    
    def get_all_boundaries(self):
        """Get all quadrant boundaries for visualization."""
        boundaries = [self.boundary]
        if self.divided:
            boundaries.extend(self.northwest.get_all_boundaries())
            boundaries.extend(self.northeast.get_all_boundaries())
            boundaries.extend(self.southwest.get_all_boundaries())
            boundaries.extend(self.southeast.get_all_boundaries())
        return boundaries


 def visualize_quadtree_rects(quadtree, rects, query_rect=None, found_rects=None,
                            filename="quadtree_rects", title="Quadtree with Rectangles"):
    """Visualize quadtree with rectangle objects (circuit components)."""
    fig, ax = plt.subplots(figsize=(12, 12))
    
    # Draw all quadtree boundaries
    boundaries = quadtree.get_all_boundaries()
    for boundary in boundaries:
        x = boundary.x - boundary.width/2
        y = boundary.y - boundary.height/2
        rect = patches.Rectangle((x, y), boundary.width, boundary.height,
                                 linewidth=1, edgecolor='gray', 
                                 facecolor='none', alpha=0.5)
        ax.add_patch(rect)
    
    # Draw all component rectangles
    for rect in rects:
        is_found = found_rects and rect in found_rects
        color = 'red' if is_found else 'blue'
        alpha = 0.6 if is_found else 0.3
        linewidth = 2 if is_found else 1
        
        rect_patch = patches.Rectangle((rect.x, rect.y), rect.width, rect.height,
                                       linewidth=linewidth, edgecolor=color,
                                       facecolor=color, alpha=alpha)
        ax.add_patch(rect_patch)
        
        # Draw center point
        center = rect.center
        ax.plot(center.x, center.y, 'ko', markersize=3, alpha=0.5)
    
    # Draw query range if provided
    if query_rect:
        x = query_rect.x - query_rect.width/2
        y = query_rect.y - query_rect.height/2
        query_patch = patches.Rectangle((x, y), query_rect.width, query_rect.height,
                                       linewidth=3, edgecolor='green',
                                       facecolor='green', alpha=0.1,
                                       linestyle='--')
        ax.add_patch(query_patch)
    
    # Set bounds
    boundary = quadtree.boundary
    margin = boundary.width * 0.05
    ax.set_xlim(boundary.x - boundary.width/2 - margin,
                boundary.x + boundary.width/2 + margin)
    ax.set_ylim(boundary.y - boundary.height/2 - margin,
                boundary.y + boundary.height/2 + margin)
    
    ax.set_aspect('equal')
    ax.set_title(title, fontsize=16, fontweight='bold')
    ax.set_xlabel('X (nm)', fontsize=12)
    ax.set_ylabel('Y (nm)', fontsize=12)
    ax.grid(True, alpha=0.3)
    
    # Add info
    info_text = f"Components: {len(rects)}\nQuadrants: {quadtree.count_nodes()}"
    if found_rects:
        info_text += f"\nIntersecting: {len(found_rects)}"
    ax.text(0.02, 0.98, info_text, transform=ax.transAxes,
            verticalalignment='top', bbox=dict(boxstyle='round',
            facecolor='wheat', alpha=0.5), fontsize=10)
    
    # Legend
    blue_patch = patches.Patch(color='blue', alpha=0.3, label='Components')
    if found_rects:
        red_patch = patches.Patch(color='red', alpha=0.6, label='Found (intersecting)')
        green_patch = patches.Patch(color='green', alpha=0.1, label='Query region')
        ax.legend(handles=[blue_patch, red_patch, green_patch], loc='upper right')
    else:
        ax.legend(handles=[blue_patch], loc='upper right')
    
    plt.tight_layout()
    filepath = os.path.join(OUTPUT_DIR, f"{filename}.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    return filepath


 def example_1_basic_quadtree():
    """Example 1: Basic quadtree construction and visualization."""
    print("="*70)
    print("EXAMPLE 1: Basic Quadtree Construction")
    print("="*70)
    
    # Create a quadtree covering 0-100 in both x and y
    boundary = Rectangle(50, 50, 100, 100)
    qt = Quadtree(boundary, capacity=4)
    
    # Insert some points
    print("\nInserting points...")
    random.seed(42)
    points = []
    for i in range(50):
        x = random.uniform(0, 100)
        y = random.uniform(0, 100)
        p = Point(x, y, data=f"point_{i}")
        points.append(p)
        qt.insert(p)
    
    print(f"Inserted {len(points)} points")
    print(f"Quadtree has {qt.count_nodes()} nodes (quadrants)")
    
    # Visualize
    filepath = visualize_quadtree(qt, points, 
                                  filename="1_basic_quadtree",
                                  title="Basic Quadtree (capacity=4, 50 points)")
    print(f"✓ Saved: {filepath}")
    
    print("\nHow it works:")
    print("  1. Start with one large quadrant covering entire space")
    print("  2. Insert points until capacity (4) is reached")
    print("  3. Subdivide into 4 child quadrants (NW, NE, SW, SE)")
    print("  4. Recursively insert remaining points into children")
    print("  5. Dense areas have more subdivisions (adaptive)")


 def example_2_range_query():
    """Example 2: Range query - the killer feature of quadtrees."""
    print("\n" + "="*70)
    print("EXAMPLE 2: Range Query (Fast Spatial Search)")
    print("="*70)
    
    # Create quadtree with many points
    boundary = Rectangle(50, 50, 100, 100)
    qt = Quadtree(boundary, capacity=4)
    
    random.seed(42)
    points = []
    print("\nInserting 500 points...")
    for i in range(500):
        x = random.uniform(0, 100)
        y = random.uniform(0, 100)
        p = Point(x, y, data=f"point_{i}")
        points.append(p)
        qt.insert(p)
    
    print(f"Quadtree has {qt.count_nodes()} nodes")
    
    # Define query range
    query_rect = Rectangle(30, 40, 20, 20)
    
    # Perform query with timing
    start = time.time()
    found = qt.query(query_rect)
    query_time = time.time() - start
    
    print(f"\nRange query: Rectangle centered at (30, 40), size 20×20")
    print(f"Found {len(found)} points in {query_time*1000:.3f} ms")
    
    # Compare with brute force
    start = time.time()
    brute_force = [p for p in points if query_rect.contains(p)]
    brute_time = time.time() - start
    
    print(f"Brute force: {len(brute_force)} points in {brute_time*1000:.3f} ms")
    print(f"Speedup: {brute_time/query_time:.1f}x faster with quadtree")
    
    # Visualize
    filepath = visualize_quadtree(qt, points, query_rect, found,
                                  filename="2_range_query",
                                  title="Range Query: Red box = query, Red dots = found points")
    print(f"✓ Saved: {filepath}")
    
    print("\nWhy quadtrees are fast:")
    print("  • Brute force: Check ALL 500 points = O(n)")
    print("  • Quadtree: Only check relevant quadrants = O(log n)")
    print("  • Key insight: Skip entire quadrants that don't intersect query")


 def example_3_circuit_design():
    """Example 3: Circuit design application - component placement."""
    print("\n" + "="*70)
    print("EXAMPLE 3: Circuit Component Placement")
    print("="*70)
    
    print("\nScenario: Finding components near a selected region")
    print("Use case: Design Rule Checking (DRC), proximity analysis")
    
    # Create quadtree for circuit board (1000×1000 units)
    boundary = Rectangle(500, 500, 1000, 1000)
    qt = Quadtree(boundary, capacity=8)
    
    # Simulate circuit components
    random.seed(100)
    components = []
    
    # Add clustered components (realistic circuit layout)
    clusters = [
        (200, 200, 50),  # Cluster center and radius
        (400, 600, 60),
        (700, 300, 40),
        (800, 800, 55)
    ]
    
    component_id = 0
    for cx, cy, radius in clusters:
        for _ in range(30):
            x = cx + random.gauss(0, radius)
            y = cy + random.gauss(0, radius)
            x = max(0, min(1000, x))
            y = max(0, min(1000, y))
            p = Point(x, y, data=f"IC_{component_id}")
            components.append(p)
            qt.insert(p)
            component_id += 1
    
    print(f"Placed {len(components)} components in {len(clusters)} clusters")
    print(f"Quadtree structure: {qt.count_nodes()} nodes")
    
    # Query: Find components near center for routing
    query_rect = Rectangle(400, 600, 150, 150)
    found = qt.query(query_rect)
    
    print(f"\nQuery: Components near (400, 600)")
    print(f"Found {len(found)} components in proximity")
    print(f"Application: Check spacing rules, route connections")
    
    filepath = visualize_quadtree(qt, components, query_rect, found,
                                  filename="3_circuit_components",
                                  title="Circuit Component Placement - DRC proximity check")
    print(f"✓ Saved: {filepath}")
    
    print("\nCircuit design applications:")
    print("  • Design Rule Checking (DRC): Find nearby components")
    print("  • Collision detection: Prevent component overlap")
    print("  • Routing: Find components to connect")
    print("  • Proximity analysis: Identify interference risks")


 def example_4_performance_comparison():
    """Example 4: Performance scaling comparison."""
    print("\n" + "="*70)
    print("EXAMPLE 4: Performance Scaling Analysis")
    print("="*70)
    
    print("\nComparing quadtree vs brute force for different data sizes...")
    
    sizes = [100, 500, 1000, 2000, 5000]
    qt_times = []
    bf_times = []
    
    for n in sizes:
        # Build quadtree
        boundary = Rectangle(500, 500, 1000, 1000)
        qt = Quadtree(boundary, capacity=8)
        
        random.seed(42)
        points = []
        for i in range(n):
            x = random.uniform(0, 1000)
            y = random.uniform(0, 1000)
            p = Point(x, y)
            points.append(p)
            qt.insert(p)
        
        # Query range
        query_rect = Rectangle(500, 500, 200, 200)
        
        # Time quadtree query
        start = time.time()
        for _ in range(100):  # Average over 100 queries
            found_qt = qt.query(query_rect)
        qt_time = (time.time() - start) / 100
        qt_times.append(qt_time * 1000)  # Convert to ms
        
        # Time brute force
        start = time.time()
        for _ in range(100):
            found_bf = [p for p in points if query_rect.contains(p)]
        bf_time = (time.time() - start) / 100
        bf_times.append(bf_time * 1000)
        
        speedup = bf_time / qt_time
        print(f"  n={n:>5}: Quadtree={qt_time*1000:>6.3f}ms, "
              f"BruteForce={bf_time*1000:>6.3f}ms, Speedup={speedup:>5.1f}x")
    
    # Plot results
    fig, ax = plt.subplots(figsize=(10, 6))
    ax.plot(sizes, qt_times, 'b-o', label='Quadtree', linewidth=2, markersize=8)
    ax.plot(sizes, bf_times, 'r-s', label='Brute Force', linewidth=2, markersize=8)
    ax.set_xlabel('Number of Points', fontsize=12, fontweight='bold')
    ax.set_ylabel('Query Time (ms)', fontsize=12, fontweight='bold')
    ax.set_title('Quadtree vs Brute Force Performance', fontsize=14, fontweight='bold')
    ax.legend(fontsize=11)
    ax.grid(True, alpha=0.3)
    ax.set_yscale('log')
    
    filepath = os.path.join(OUTPUT_DIR, "4_performance_comparison.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    print(f"\n✓ Saved: {filepath}")
    
    print("\nKey insights:")
    print("  • Quadtree: O(log n) - scales logarithmically")
    print("  • Brute force: O(n) - scales linearly")
    print("  • Speedup increases with data size")
    print("  • Critical for real-time applications with millions of points")


 def example_5_adaptive_subdivision():
    """Example 5: Demonstrate adaptive subdivision."""
    print("\n" + "="*70)
    print("EXAMPLE 5: Adaptive Subdivision")
    print("="*70)
    
    print("\nDemonstrating how quadtrees adapt to data distribution...")
    
    # Create two datasets: uniform and clustered
    boundary = Rectangle(50, 50, 100, 100)
    
    # Dataset 1: Uniform distribution
    qt_uniform = Quadtree(boundary, capacity=4)
    random.seed(42)
    uniform_points = []
    for i in range(100):
        x = random.uniform(0, 100)
        y = random.uniform(0, 100)
        p = Point(x, y)
        uniform_points.append(p)
        qt_uniform.insert(p)
    
    filepath1 = visualize_quadtree(qt_uniform, uniform_points,
                                   filename="5a_uniform_distribution",
                                   title="Uniform Distribution - Even subdivision")
    print(f"✓ Uniform: {qt_uniform.count_nodes()} nodes")
    print(f"  Saved: {filepath1}")
    
    # Dataset 2: Clustered distribution
    qt_clustered = Quadtree(boundary, capacity=4)
    clustered_points = []
    # Dense cluster in one corner
    for i in range(80):
        x = random.gauss(25, 8)
        y = random.gauss(25, 8)
        x = max(0, min(100, x))
        y = max(0, min(100, y))
        p = Point(x, y)
        clustered_points.append(p)
        qt_clustered.insert(p)
    # Sparse elsewhere
    for i in range(20):
        x = random.uniform(50, 100)
        y = random.uniform(50, 100)
        p = Point(x, y)
        clustered_points.append(p)
        qt_clustered.insert(p)
    
    filepath2 = visualize_quadtree(qt_clustered, clustered_points,
                                   filename="5b_clustered_distribution",
                                   title="Clustered Distribution - Adaptive subdivision")
    print(f"✓ Clustered: {qt_clustered.count_nodes()} nodes")
    print(f"  Saved: {filepath2}")
    
    print("\nAdaptive subdivision benefits:")
    print("  • Dense regions get more subdivision (finer granularity)")
    print("  • Sparse regions stay coarse (less overhead)")
    print("  • Automatic load balancing based on data distribution")
    print("  • Critical for real-world circuits (non-uniform layouts)")


 def main():
    """Run all examples."""
    print("\n" + "█"*70)
    print("QUADTREE DATA STRUCTURES FOR SPATIAL INDEXING")
    print("█"*70)
    
    print("\nWHAT IS A QUADTREE?")
    print("A hierarchical data structure that recursively partitions 2D space")
    print("into four quadrants (NW, NE, SW, SE). Each node can subdivide when")
    print("it reaches capacity, creating adaptive resolution.")
    
    print("\nKEY OPERATIONS:")
    print("  • Insert: Add point to appropriate quadrant - O(log n)")
    print("  • Query: Find all points in a rectangle - O(log n) average")
    print("  • Range search: Only check intersecting quadrants")
    
    print("\nAPPLICATIONS IN SEMICONDUCTOR DESIGN:")
    print("  • Design Rule Checking (DRC)")
    print("  • Collision detection in layout")
    print("  • Component proximity analysis")
    print("  • Spatial indexing for polygon operations")
    print("  • Fast nearest-neighbor search")
    
    print(f"\n✓ All visualizations will be saved to: {OUTPUT_DIR}/")
    print("="*70)
    
    # Run examples
    example_1_basic_quadtree()
    example_2_range_query()
    example_3_circuit_design()
    example_4_performance_comparison()
    example_5_adaptive_subdivision()
    example_6_rectangles_collision()
    example_7_polygon_operations()
    
    print("\n" + "="*70)
    print("INTERVIEW KEY POINTS")
    print("="*70)
    print("\nQuadtree vs Other Structures:")
    print("  • vs Array: O(log n) query vs O(n)")
    print("  • vs Grid: Adaptive resolution vs fixed")
    print("  • vs R-tree: Simpler, better for points; R-tree better for rectangles")
    print("  • vs K-d tree: Quadtree better for 2D, K-d tree for higher dimensions")
    
    print("\nWhen to use Quadtrees:")
    print("  ✓ 2D spatial queries (range, nearest neighbor)")
    print("  ✓ Dynamic data (frequent insertions)")
    print("  ✓ Non-uniform data distribution")
    print("  ✓ Real-time collision detection")
    
    print("\nLimitations:")
    print("  ✗ Higher memory overhead than arrays")
    print("  ✗ Worst-case still O(n) for pathological distributions")
    print("  ✗ Not ideal for 3D+ (use octrees or k-d trees)")
    
    print(f"\n✓ All visualizations saved to: {os.path.abspath(OUTPUT_DIR)}/")
    print("="*70)


 if __name__ == "__main__":
    main()
diff --git a/quad_r_comparison_ex.py b/quad_r_comparison_ex.py
 #!/usr/bin/python3.12
 """
 R-tree vs Quadtree: Algorithmic Comparison

 Understanding the fundamental differences between these spatial data structures
 is critical for semiconductor design applications.
 """

 import matplotlib.pyplot as plt
 import matplotlib.patches as patches
 import random
 import os

 OUTPUT_DIR = "rtree_vs_quadtree_comparison"
 if not os.path.exists(OUTPUT_DIR):
    os.makedirs(OUTPUT_DIR)


 def visualize_comparison():
    """Create side-by-side comparison of R-tree and Quadtree."""
    
    print("="*70)
    print("R-TREE VS QUADTREE: ALGORITHMIC DIFFERENCES")
    print("="*70)
    
    # Generate same set of rectangles for both
    random.seed(42)
    rectangles = []
    for i in range(12):
        x = random.uniform(10, 80)
        y = random.uniform(10, 80)
        w = random.uniform(5, 15)
        h = random.uniform(5, 15)
        rectangles.append((x, y, w, h, f"R{i}"))
    
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(18, 9))
    
    # LEFT: Quadtree approach
    ax1.set_title("QUADTREE\nSpace-driven partitioning", 
                  fontsize=14, fontweight='bold')
    ax1.set_xlim(0, 100)
    ax1.set_ylim(0, 100)
    ax1.set_aspect('equal')
    ax1.grid(True, alpha=0.3)
    
    # Draw quadtree divisions (fixed, space-based)
    ax1.axhline(50, color='red', linewidth=2, linestyle='-', alpha=0.7)
    ax1.axvline(50, color='red', linewidth=2, linestyle='-', alpha=0.7)
    ax1.axhline(25, xmax=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
    ax1.axvline(25, ymax=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
    ax1.axhline(75, xmin=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
    ax1.axvline(75, ymin=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
    
    # Label quadrants
    ax1.text(25, 75, 'NW', ha='center', va='center', fontsize=16, 
             bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
    ax1.text(75, 75, 'NE', ha='center', va='center', fontsize=16,
             bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
    ax1.text(25, 25, 'SW', ha='center', va='center', fontsize=16,
             bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
    ax1.text(75, 25, 'SE', ha='center', va='center', fontsize=16,
             bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
    
    # Draw rectangles on quadtree
    for x, y, w, h, label in rectangles:
        rect = patches.Rectangle((x, y), w, h, linewidth=2, 
                                edgecolor='blue', facecolor='lightblue', alpha=0.6)
        ax1.add_patch(rect)
        ax1.plot(x + w/2, y + h/2, 'ko', markersize=4)
    
    # RIGHT: R-tree approach
    ax2.set_title("R-TREE\nData-driven bounding boxes", 
                  fontsize=14, fontweight='bold')
    ax2.set_xlim(0, 100)
    ax2.set_ylim(0, 100)
    ax2.set_aspect('equal')
    ax2.grid(True, alpha=0.3)
    
    # Manually group rectangles into R-tree bounding boxes (simulated)
    # Group 1: bottom-left cluster
    group1_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles if x < 40 and y < 40]
    if group1_rects:
        min_x = min(r[0] for r in group1_rects)
        min_y = min(r[1] for r in group1_rects)
        max_x = max(r[0] + r[2] for r in group1_rects)
        max_y = max(r[1] + r[3] for r in group1_rects)
        bbox1 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
                                  linewidth=3, edgecolor='red', facecolor='none',
                                  linestyle='--', alpha=0.8)
        ax2.add_patch(bbox1)
        ax2.text((min_x+max_x)/2, max_y+5, 'MBR 1', ha='center', fontsize=12,
                fontweight='bold', color='red')
    
    # Group 2: top cluster
    group2_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles if y > 50]
    if group2_rects:
        min_x = min(r[0] for r in group2_rects)
        min_y = min(r[1] for r in group2_rects)
        max_x = max(r[0] + r[2] for r in group2_rects)
        max_y = max(r[1] + r[3] for r in group2_rects)
        bbox2 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
                                  linewidth=3, edgecolor='green', facecolor='none',
                                  linestyle='--', alpha=0.8)
        ax2.add_patch(bbox2)
        ax2.text((min_x+max_x)/2, max_y+5, 'MBR 2', ha='center', fontsize=12,
                fontweight='bold', color='green')
    
    # Group 3: remaining
    group3_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles 
                   if not (x < 40 and y < 40) and not (y > 50)]
    if group3_rects:
        min_x = min(r[0] for r in group3_rects)
        min_y = min(r[1] for r in group3_rects)
        max_x = max(r[0] + r[2] for r in group3_rects)
        max_y = max(r[1] + r[3] for r in group3_rects)
        bbox3 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
                                  linewidth=3, edgecolor='purple', facecolor='none',
                                  linestyle='--', alpha=0.8)
        ax2.add_patch(bbox3)
        ax2.text((min_x+max_x)/2, min_y-5, 'MBR 3', ha='center', fontsize=12,
                fontweight='bold', color='purple')
    
    # Draw rectangles on R-tree
    for x, y, w, h, label in rectangles:
        rect = patches.Rectangle((x, y), w, h, linewidth=2,
                                edgecolor='blue', facecolor='lightblue', alpha=0.6)
        ax2.add_patch(rect)
    
    plt.tight_layout()
    filepath = os.path.join(OUTPUT_DIR, "1_visual_comparison.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    print(f"\n✓ Saved: {filepath}")
    
    return filepath


 def create_detailed_comparison():
    """Create detailed algorithmic comparison diagram."""
    
    fig = plt.figure(figsize=(16, 12))
    
    # Title
    fig.suptitle("Algorithmic Differences: R-tree vs Quadtree", 
                fontsize=18, fontweight='bold', y=0.98)
    
    # Create grid for comparison
    gs = fig.add_gridspec(4, 2, hspace=0.4, wspace=0.3)
    
    # PARTITIONING STRATEGY
    ax1 = fig.add_subplot(gs[0, 0])
    ax1.set_title("Quadtree: Fixed Space Division", fontweight='bold')
    ax1.set_xlim(0, 100)
    ax1.set_ylim(0, 100)
    ax1.set_aspect('equal')
    ax1.axhline(50, color='red', linewidth=2)
    ax1.axvline(50, color='red', linewidth=2)
    ax1.text(50, 95, "Always divides space\ninto 4 equal quadrants", 
            ha='center', fontsize=10, bbox=dict(boxstyle='round', facecolor='wheat'))
    ax1.axis('off')
    
    ax2 = fig.add_subplot(gs[0, 1])
    ax2.set_title("R-tree: Data-driven Grouping", fontweight='bold')
    ax2.set_xlim(0, 100)
    ax2.set_ylim(0, 100)
    ax2.set_aspect('equal')
    # Draw overlapping bounding boxes
    rect1 = patches.Rectangle((10, 10), 40, 40, linewidth=2, 
                              edgecolor='red', facecolor='red', alpha=0.2)
    rect2 = patches.Rectangle((35, 35), 50, 50, linewidth=2,
                              edgecolor='blue', facecolor='blue', alpha=0.2)
    ax2.add_patch(rect1)
    ax2.add_patch(rect2)
    ax2.text(50, 95, "Groups objects by proximity\n(can overlap!)", 
            ha='center', fontsize=10, bbox=dict(boxstyle='round', facecolor='wheat'))
    ax2.axis('off')
    
    # NODE STRUCTURE
    ax3 = fig.add_subplot(gs[1, 0])
    ax3.text(0.5, 0.9, "Quadtree Node Structure", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax3.transAxes)
    structure_text = """
 • Fixed: Always 4 children (NW, NE, SW, SE)
 • Boundary: Center point + width/height
 • Split criterion: Count > capacity
 • Empty quadrants: Still exist in tree
 • Example:
  Node {
    boundary: (50, 50, 100×100)
    children: [NW, NE, SW, SE]
    points: [...]
  }
 """
    ax3.text(0.1, 0.75, structure_text, ha='left', va='top', 
            fontsize=9, family='monospace', transform=ax3.transAxes)
    ax3.axis('off')
    
    ax4 = fig.add_subplot(gs[1, 1])
    ax4.text(0.5, 0.9, "R-tree Node Structure", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax4.transAxes)
    structure_text = """
 • Variable: m to M children (e.g., 2-8)
 • MBR: Minimum Bounding Rectangle
 • Split criterion: Overflow + minimize area
 • No empty nodes
 • Example:
  Node {
    mbr: (x1, y1, x2, y2)
    children: [MBR1, MBR2, ..., MBRn]
    entries: [...]
  }
 """
    ax4.text(0.1, 0.75, structure_text, ha='left', va='top',
            fontsize=9, family='monospace', transform=ax4.transAxes)
    ax4.axis('off')
    
    # INSERTION ALGORITHM
    ax5 = fig.add_subplot(gs[2, 0])
    ax5.text(0.5, 0.95, "Quadtree Insertion", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax5.transAxes)
    algo_text = """
 1. Check if point in boundary
 2. If capacity not full: add here
 3. Else: subdivide into 4 quadrants
 4. Recursively insert into children
 5. Based on spatial position only

 Key: Deterministic - same point
     always goes to same quadrant
 """
    ax5.text(0.05, 0.8, algo_text, ha='left', va='top',
            fontsize=9, transform=ax5.transAxes)
    ax5.axis('off')
    
    ax6 = fig.add_subplot(gs[2, 1])
    ax6.text(0.5, 0.95, "R-tree Insertion", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax6.transAxes)
    algo_text = """
 1. Choose subtree (minimize area increase)
 2. If node full: split node
 3. Choose split: minimize overlap & area
 4. Adjust MBRs up the tree
 5. Based on grouping heuristics

 Key: Non-deterministic - depends on
     insertion order and split strategy
 """
    ax6.text(0.05, 0.8, algo_text, ha='left', va='top',
            fontsize=9, transform=ax6.transAxes)
    ax6.axis('off')
    
    # QUERY ALGORITHM
    ax7 = fig.add_subplot(gs[3, 0])
    ax7.text(0.5, 0.95, "Quadtree Query", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax7.transAxes)
    query_text = """
 Query: Find all objects in range R

 1. If boundary doesn't intersect R: STOP
 2. Check all objects in this node
 3. If subdivided:
   - Recursively query NW
   - Recursively query NE
   - Recursively query SW
   - Recursively query SE

 Prunes: Entire quadrants
 """
    ax7.text(0.05, 0.8, query_text, ha='left', va='top',
            fontsize=9, transform=ax7.transAxes)
    ax7.axis('off')
    
    ax8 = fig.add_subplot(gs[3, 1])
    ax8.text(0.5, 0.95, "R-tree Query", ha='center', va='top',
            fontsize=12, fontweight='bold', transform=ax8.transAxes)
    query_text = """
 Query: Find all objects in range R

 1. If MBR doesn't intersect R: STOP
 2. If leaf: check all entries
 3. If internal:
   - For each child MBR:
     - If intersects R: recurse

 Prunes: Minimum bounding rectangles
       (can be more/less efficient
        depending on data)
 """
    ax8.text(0.05, 0.8, query_text, ha='left', va='top',
            fontsize=9, transform=ax8.transAxes)
    ax8.axis('off')
    
    filepath = os.path.join(OUTPUT_DIR, "2_algorithmic_details.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    print(f"✓ Saved: {filepath}")


 def create_use_case_comparison():
    """Create use-case comparison chart."""
    
    fig, ax = plt.subplots(figsize=(14, 10))
    ax.axis('off')
    
    # Title
    ax.text(0.5, 0.95, "When to Use: R-tree vs Quadtree", 
           ha='center', fontsize=18, fontweight='bold', transform=ax.transAxes)
    
    # Create comparison table
    categories = [
        ("Data Type", "Points", "Rectangles/Polygons"),
        ("Dimensionality", "2D only", "2D, 3D, N-D"),
        ("Distribution", "Any (adaptive)", "Clustered data (optimal)"),
        ("Overlap", "No overlap in structure", "MBRs can overlap"),
        ("Memory", "Higher (empty nodes)", "Lower (no empty nodes)"),
        ("Balancing", "Automatic (space-based)", "Requires rebalancing"),
        ("Query Speed", "Fast for uniform data", "Fast for clustered data"),
        ("Insert Complexity", "O(log n)", "O(log n) avg, O(n) worst"),
        ("Implementation", "Simpler", "More complex"),
    ]
    
    y_start = 0.85
    y_step = 0.08
    
    # Header
    ax.text(0.25, y_start + 0.02, "QUADTREE", ha='center', fontsize=14, 
           fontweight='bold', color='blue', transform=ax.transAxes)
    ax.text(0.50, y_start + 0.02, "Aspect", ha='center', fontsize=14,
           fontweight='bold', transform=ax.transAxes)
    ax.text(0.75, y_start + 0.02, "R-TREE", ha='center', fontsize=14,
           fontweight='bold', color='red', transform=ax.transAxes)
    
    # Draw rows
    for i, (category, quad, rtree) in enumerate(categories):
        y = y_start - (i + 1) * y_step
        
        # Background
        if i % 2 == 0:
            rect = patches.Rectangle((0.05, y - 0.025), 0.9, y_step * 0.9,
                                    facecolor='lightgray', alpha=0.3,
                                    transform=ax.transAxes)
            ax.add_patch(rect)
        
        # Category
        ax.text(0.50, y, category, ha='center', fontsize=11, fontweight='bold',
               transform=ax.transAxes)
        
        # Quadtree
        ax.text(0.25, y, quad, ha='center', fontsize=10, color='blue',
               transform=ax.transAxes)
        
        # R-tree
        ax.text(0.75, y, rtree, ha='center', fontsize=10, color='red',
               transform=ax.transAxes)
    
    # Use case recommendations
    y_bottom = y_start - len(categories) * y_step - 0.08
    
    ax.text(0.5, y_bottom, "SEMICONDUCTOR DESIGN RECOMMENDATIONS", 
           ha='center', fontsize=14, fontweight='bold', 
           bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.5),
           transform=ax.transAxes)
    
    quad_cases = """
 QUADTREE:
 ✓ Point data (component centers, vias)
 ✓ Uniform grid layouts
 ✓ 2D chip designs
 ✓ Fast prototyping (simpler code)
 ✓ Teaching/learning spatial structures
 ✓ Memory is not critical
 """
    
    rtree_cases = """
 R-TREE:
 ✓ Rectangle/polygon data (masks, traces)
 ✓ Clustered layouts (realistic circuits)
 ✓ 3D structures (multi-layer routing)
 ✓ Production systems (optimized)
 ✓ Large-scale polygon operations
 ✓ Minimize memory footprint
 """
    
    ax.text(0.25, y_bottom - 0.15, quad_cases, ha='center', va='top', fontsize=10,
           family='monospace', bbox=dict(boxstyle='round', facecolor='lightblue', alpha=0.5),
           transform=ax.transAxes)
    
    ax.text(0.75, y_bottom - 0.15, rtree_cases, ha='center', va='top', fontsize=10,
           family='monospace', bbox=dict(boxstyle='round', facecolor='lightcoral', alpha=0.5),
           transform=ax.transAxes)
    
    filepath = os.path.join(OUTPUT_DIR, "3_use_case_comparison.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    print(f"✓ Saved: {filepath}")


 def main():
    """Generate all comparison visualizations."""
    
    print("\n" + "█"*70)
    print("R-TREE VS QUADTREE: COMPLETE ALGORITHMIC COMPARISON")
    print("█"*70)
    
    print("\n" + "="*70)
    print("KEY ALGORITHMIC DIFFERENCES")
    print("="*70)
    
    print("\n1. PARTITIONING STRATEGY")
    print("   Quadtree: SPACE-DRIVEN")
    print("     • Divides space into 4 equal quadrants")
    print("     • Fixed, regular subdivision")
    print("     • Based on spatial coordinates")
    
    print("\n   R-tree: DATA-DRIVEN")
    print("     • Groups objects into Minimum Bounding Rectangles (MBRs)")
    print("     • Variable number of children per node (m to M)")
    print("     • Based on object proximity and clustering")
    
    print("\n2. NODE STRUCTURE")
    print("   Quadtree: Always 4 children (or leaf)")
    print("     • Fixed branching factor = 4")
    print("     • Empty quadrants still exist")
    print("     • Boundary defined by center + size")
    
    print("\n   R-tree: Variable children (e.g., 2-8)")
    print("     • Branching factor: m ≤ children ≤ M")
    print("     • No empty nodes")
    print("     • Each node stores its MBR")
    
    print("\n3. OVERLAP")
    print("   Quadtree: NO OVERLAP")
    print("     • Quadrants never overlap")
    print("     • Each point belongs to exactly one quadrant")
    
    print("\n   R-tree: CAN OVERLAP")
    print("     • MBRs can overlap (inevitable with rectangles)")
    print("     • Objects may be checked multiple times in queries")
    
    print("\n4. INSERTION")
    print("   Quadtree:")
    print("     • Find quadrant containing point")
    print("     • If full, subdivide into 4")
    print("     • Deterministic (same point → same location)")
    
    print("\n   R-tree:")
    print("     • Choose subtree that needs least enlargement")
    print("     • If full, split node (complex heuristics)")
    print("     • Non-deterministic (depends on insert order)")
    
    print("\n5. COMPLEXITY")
    print("   Quadtree:")
    print("     • Insert: O(log₄ n) = O(log n)")
    print("     • Query: O(log n) average, O(n) worst-case")
    print("     • Simple to implement")
    
    print("\n   R-tree:")
    print("     • Insert: O(log_M n) average, O(n) worst-case")
    print("     • Query: O(log n) average for good data")
    print("     • Complex splitting algorithms")
    
    print("\n" + "="*70)
    print("GENERATING VISUALIZATIONS...")
    print("="*70)
    
    visualize_comparison()
    create_detailed_comparison()
    create_use_case_comparison()
    
    print("\n" + "="*70)
    print("INTERVIEW KEY POINTS")
    print("="*70)
    
    print("\nQuadtree:")
    print("  ✓ Pro: Simpler, faster for points, good for uniform data")
    print("  ✓ Pro: Adaptive subdivision, guaranteed O(log n) depth")
    print("  ✗ Con: Only 2D, wastes space on empty quadrants")
    print("  ✗ Con: Poor for rectangles (stores by center point)")
    
    print("\nR-tree:")
    print("  ✓ Pro: Optimal for rectangles/polygons, works in N dimensions")
    print("  ✓ Pro: No wasted space, better for clustered data")
    print("  ✗ Con: More complex, can have overlap, may need rebalancing")
    print("  ✗ Con: Insert order affects structure quality")
    
    print("\nFor Semiconductor EDA:")
    print("  • Use Quadtree for: Component placement, via locations, DRC (points)")
    print("  • Use R-tree for: Polygon masks, routing layers, large designs")
    print("  • Hybrid: Quadtree for quick prototyping, R-tree for production")
    
    print(f"\n✓ All visualizations saved to: {os.path.abspath(OUTPUT_DIR)}/")
    print("="*70)


 if __name__ == "__main__":
    main()
diff --git a/quads_ex.py b/quads_ex.py
 #!/usr/bin/python3.12
 from quads import QuadTree, Point, visualize, BoundingBox 


 points = [ Point(50, 50),   Point(200, 70),
           Point(100, 180), Point(220, 220),
           Point(30, 150) ]

 width, height = 512, 512
 tree = QuadTree((0, 0), width, height)
 [tree.insert(p) for p in points]
 visualize(tree)

 # You can also perform queries, e.g., finding points within a region
 bb = BoundingBox(min_x=40, min_y=40, max_x=120, max_y=120)
 found_points = tree.within_bb(bb)
 print(f"\nPoints found in region {bb}:")
 for p in found_points:
    print(f"  {p.x}, {p.y}")
diff --git a/scanline.py b/scanline.py
 #!/usr/bin/python3.12
 """
 Scanline Algorithm for Rectangle Overlap Detection

 The scanline algorithm is a sweep-line technique that efficiently finds
 overlapping rectangles in O(n log n) time, much better than the naive O(n²).

 Critical for semiconductor design:
 - Design Rule Checking (DRC)
 - Mask layer validation
 - Component overlap detection
 """

 import matplotlib.pyplot as plt
 import matplotlib.patches as patches
 from dataclasses import dataclass
 from typing import List, Set, Tuple
 import random
 import os

 OUTPUT_DIR = "scanline_results"
 if not os.path.exists(OUTPUT_DIR):
    os.makedirs(OUTPUT_DIR)


 @dataclass
 class Rectangle:
    """Rectangle representation."""
    id: int
    x1: float  # Left
    y1: float  # Bottom
    x2: float  # Right
    y2: float  # Top
    name: str = ""
    
    def __post_init__(self):
        if not self.name:
            self.name = f"R{self.id}"
    
    def overlaps(self, other: 'Rectangle') -> bool:
        """Check if two rectangles overlap."""
        return not (self.x2 <= other.x1 or  # self is completely to the left
                   self.x1 >= other.x2 or  # self is completely to the right
                   self.y2 <= other.y1 or  # self is completely below
                   self.y1 >= other.y2)    # self is completely above
    
    def __repr__(self):
        return f"{self.name}[({self.x1},{self.y1})-({self.x2},{self.y2})]"


 @dataclass
 class Event:
    """Sweep line event."""
    x: float          # X-coordinate of event
    rect_id: int      # Rectangle ID
    is_start: bool    # True if entering rectangle, False if leaving
    y1: float         # Bottom y
    y2: float         # Top y
    
    def __lt__(self, other):
        """For sorting events by x-coordinate."""
        if self.x != other.x:
            return self.x < other.x
        # If same x, process end events before start events
        # This prevents false positives for touching rectangles
        return not self.is_start and other.is_start


 class IntervalTree:
    """
    Simple interval tree for 1D overlap detection.
    Used to find overlapping y-intervals when scanline is at position x.
    """
    
    def __init__(self):
        self.intervals = []  # List of (y1, y2, rect_id)
    
    def insert(self, y1: float, y2: float, rect_id: int):
        """Insert a y-interval."""
        self.intervals.append((y1, y2, rect_id))
    
    def remove(self, rect_id: int):
        """Remove all intervals for a rectangle."""
        self.intervals = [(y1, y2, rid) for y1, y2, rid in self.intervals 
                         if rid != rect_id]
    
    def find_overlaps(self, y1: float, y2: float, rect_id: int) -> List[int]:
        """Find all intervals that overlap with [y1, y2]."""
        overlaps = []
        for interval_y1, interval_y2, interval_id in self.intervals:
            if interval_id != rect_id:  # Don't compare with self
                # Check if intervals overlap
                if not (y2 <= interval_y1 or y1 >= interval_y2):
                    overlaps.append(interval_id)
        return overlaps


 def scanline_find_overlaps(rectangles: List[Rectangle]) -> Set[Tuple[int, int]]:
    """
    Use scanline algorithm to find all overlapping rectangle pairs.
    
    Algorithm:
    1. Create events for each rectangle (start and end)
    2. Sort events by x-coordinate
    3. Sweep from left to right:
       - When entering a rectangle: check y-overlap with active rectangles
       - Add rectangle to active set
       - When leaving: remove from active set
    
    Returns:
        Set of overlapping pairs (id1, id2) where id1 < id2
    """
    print("\n" + "="*70)
    print("SCANLINE ALGORITHM: Finding Overlapping Rectangles")
    print("="*70)
    
    # Step 1: Create events
    events = []
    for rect in rectangles:
        # Start event (entering rectangle)
        events.append(Event(rect.x1, rect.id, True, rect.y1, rect.y2))
        # End event (leaving rectangle)
        events.append(Event(rect.x2, rect.id, False, rect.y1, rect.y2))
    
    # Step 2: Sort events by x-coordinate
    events.sort()
    
    print(f"\nProcessing {len(rectangles)} rectangles...")
    print(f"Created {len(events)} events (2 per rectangle)")
    
    # Step 3: Sweep through events
    active_intervals = IntervalTree()  # Currently active rectangles
    overlaps = set()  # Store overlapping pairs
    
    print("\nSweeping left to right:")
    current_x = None
    event_count = 0
    
    for event in events:
        if current_x is None or event.x != current_x:
            if current_x is not None:
                event_count += 1
            current_x = event.x
        
        if event.is_start:
            # Entering a rectangle: check for y-overlaps with active rectangles
            overlapping_ids = active_intervals.find_overlaps(
                event.y1, event.y2, event.rect_id
            )
            
            # Record overlaps
            for other_id in overlapping_ids:
                pair = tuple(sorted([event.rect_id, other_id]))
                overlaps.add(pair)
                if len(overlaps) <= 5:  # Print first few
                    rect1 = rectangles[event.rect_id]
                    rect2 = rectangles[other_id]
                    print(f"  Overlap found: {rect1.name} ↔ {rect2.name}")
            
            # Add to active set
            active_intervals.insert(event.y1, event.y2, event.rect_id)
        else:
            # Leaving a rectangle: remove from active set
            active_intervals.remove(event.rect_id)
    
    if len(overlaps) > 5:
        print(f"  ... and {len(overlaps) - 5} more overlaps")
    
    print(f"\n✓ Found {len(overlaps)} overlapping pairs")
    print(f"✓ Processed {event_count} distinct x-coordinates")
    
    return overlaps


 def visualize_results(rectangles: List[Rectangle], 
                     overlapping_pairs: Set[Tuple[int, int]],
                     filename: str = "scanline_overlap_detection",
                     title: str = "Scanline Overlap Detection"):
    """Visualize rectangles with overlaps highlighted in red."""
    
    # Determine which rectangles are involved in overlaps
    overlapping_ids = set()
    for id1, id2 in overlapping_pairs:
        overlapping_ids.add(id1)
        overlapping_ids.add(id2)
    
    fig, ax = plt.subplots(figsize=(14, 12))
    
    # Draw all rectangles
    for rect in rectangles:
        is_overlapping = rect.id in overlapping_ids
        color = 'red' if is_overlapping else 'blue'
        alpha = 0.5 if is_overlapping else 0.3
        linewidth = 2 if is_overlapping else 1
        
        rect_patch = patches.Rectangle(
            (rect.x1, rect.y1),
            rect.x2 - rect.x1,
            rect.y2 - rect.y1,
            linewidth=linewidth,
            edgecolor=color,
            facecolor=color,
            alpha=alpha,
            label=rect.name if is_overlapping else None
        )
        ax.add_patch(rect_patch)
        
        # Add label
        center_x = (rect.x1 + rect.x2) / 2
        center_y = (rect.y1 + rect.y2) / 2
        ax.text(center_x, center_y, rect.name,
               ha='center', va='center',
               fontsize=8, fontweight='bold',
               color='white' if is_overlapping else 'black')
    
    # Set plot properties
    all_x = [r.x1 for r in rectangles] + [r.x2 for r in rectangles]
    all_y = [r.y1 for r in rectangles] + [r.y2 for r in rectangles]
    margin_x = (max(all_x) - min(all_x)) * 0.1
    margin_y = (max(all_y) - min(all_y)) * 0.1
    
    ax.set_xlim(min(all_x) - margin_x, max(all_x) + margin_x)
    ax.set_ylim(min(all_y) - margin_y, max(all_y) + margin_y)
    ax.set_aspect('equal')
    ax.grid(True, alpha=0.3)
    ax.set_xlabel('X (nm)', fontsize=12, fontweight='bold')
    ax.set_ylabel('Y (nm)', fontsize=12, fontweight='bold')
    ax.set_title(title, fontsize=16, fontweight='bold', pad=20)
    
    # Add legend
    blue_patch = patches.Patch(color='blue', alpha=0.3, label='No overlap')
    red_patch = patches.Patch(color='red', alpha=0.5, label='Overlapping')
    ax.legend(handles=[blue_patch, red_patch], loc='upper right', fontsize=11)
    
    # Add statistics box
    stats_text = f"Total rectangles: {len(rectangles)}\n"
    stats_text += f"Overlapping: {len(overlapping_ids)}\n"
    stats_text += f"Overlap pairs: {len(overlapping_pairs)}\n"
    stats_text += f"Algorithm: O(n log n)"
    
    ax.text(0.02, 0.98, stats_text, transform=ax.transAxes,
           verticalalignment='top',
           bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.8),
           fontsize=10, family='monospace')
    
    plt.tight_layout()
    filepath = os.path.join(OUTPUT_DIR, f"{filename}.png")
    plt.savefig(filepath, dpi=150, bbox_inches='tight')
    plt.close()
    
    print(f"\n✓ Visualization saved: {filepath}")
    return filepath


 def example_1_simple_case():
    """Example 1: Simple case with obvious overlaps."""
    print("\n" + "="*70)
    print("EXAMPLE 1: Simple Case")
    print("="*70)
    
    rectangles = [
        Rectangle(0, 10, 10, 40, 30, "A"),  # id, x1, y1, x2, y2, name
        Rectangle(1, 20, 20, 50, 40, "B"),  # Overlaps with A
        Rectangle(2, 45, 15, 70, 35, "C"),  # Overlaps with B
        Rectangle(3, 80, 10, 100, 30, "D"), # No overlap
        Rectangle(4, 15, 50, 35, 70, "E"),  # No overlap
        Rectangle(5, 55, 50, 75, 70, "F"),  # No overlap
    ]
    
    print("\nRectangles:")
    for rect in rectangles:
        print(f"  {rect}")
    
    overlaps = scanline_find_overlaps(rectangles)
    
    print("\nOverlapping pairs:")
    for id1, id2 in sorted(overlaps):
        print(f"  {rectangles[id1].name} ↔ {rectangles[id2].name}")
    
    visualize_results(rectangles, overlaps,
                     "1_simple_case",
                     "Example 1: Simple Overlap Detection")


 def example_2_circuit_components():
    """Example 2: Realistic circuit component layout."""
    print("\n" + "="*70)
    print("EXAMPLE 2: Circuit Component Layout")
    print("="*70)
    
    print("\nScenario: Detecting overlapping components in PCB layout")
    
    random.seed(42)
    rectangles = []
    
    # Create realistic component layout
    component_types = [
        ("IC", 40, 40),
        ("Resistor", 20, 8),
        ("Capacitor", 15, 15),
        ("Connector", 30, 10),
    ]
    
    for i in range(30):
        comp_type, w, h = random.choice(component_types)
        x1 = random.uniform(0, 400)
        y1 = random.uniform(0, 300)
        
        rectangles.append(Rectangle(i, x1, y1, x1 + w, y1 + h, f"{comp_type}{i}"))
    
    print(f"\nGenerated {len(rectangles)} components")
    
    overlaps = scanline_find_overlaps(rectangles)
    
    if overlaps:
        print(f"\n⚠️  WARNING: {len(overlaps)} overlapping pairs detected!")
        print("These would cause manufacturing issues:")
        for id1, id2 in list(overlaps)[:5]:
            print(f"  • {rectangles[id1].name} overlaps {rectangles[id2].name}")
        if len(overlaps) > 5:
            print(f"  ... and {len(overlaps) - 5} more")
    else:
        print("\n✓ No overlaps detected - layout is valid")
    
    visualize_results(rectangles, overlaps,
                     "2_circuit_layout",
                     "Example 2: Circuit Component Overlap Detection (DRC)")


 def example_3_semiconductor_masks():
    """Example 3: Semiconductor mask layer validation."""
    print("\n" + "="*70)
    print("EXAMPLE 3: Semiconductor Mask Layer Validation")
    print("="*70)
    
    print("\nScenario: Validating metal trace layer for short circuits")
    
    rectangles = []
    
    # Metal traces (horizontal and vertical)
    # Horizontal traces
    rectangles.append(Rectangle(0, 10, 100, 200, 110, "Trace_H1"))
    rectangles.append(Rectangle(1, 50, 150, 250, 160, "Trace_H2"))
    rectangles.append(Rectangle(2, 100, 200, 300, 210, "Trace_H3"))
    
    # Vertical traces
    rectangles.append(Rectangle(3, 150, 50, 160, 250, "Trace_V1"))
    rectangles.append(Rectangle(4, 220, 80, 230, 220, "Trace_V2"))
    
    # Contact pads
    rectangles.append(Rectangle(5, 140, 90, 170, 120, "Pad1"))  # Overlaps V1
    rectangles.append(Rectangle(6, 210, 140, 240, 170, "Pad2"))  # Overlaps H2 and V2
    rectangles.append(Rectangle(7, 280, 190, 310, 220, "Pad3"))  # Overlaps H3
    
    # Vias
    rectangles.append(Rectangle(8, 155, 105, 160, 110, "Via1"))  # Inside Pad1
    rectangles.append(Rectangle(9, 225, 155, 230, 160, "Via2"))  # Inside Pad2
    
    print(f"\nMask layer contains:")
    print(f"  - {len([r for r in rectangles if 'Trace' in r.name])} traces")
    print(f"  - {len([r for r in rectangles if 'Pad' in r.name])} contact pads")
    print(f"  - {len([r for r in rectangles if 'Via' in r.name])} vias")
    
    overlaps = scanline_find_overlaps(rectangles)
    
    print(f"\nValidation results:")
    if overlaps:
        print(f"  ⚠️  Found {len(overlaps)} potential issues:")
        
        # Categorize overlaps
        intentional = 0
        issues = 0
        
        for id1, id2 in overlaps:
            r1, r2 = rectangles[id1], rectangles[id2]
            # Pad-Via overlaps are intentional (connections)
            if ('Pad' in r1.name and 'Via' in r2.name) or \
               ('Via' in r1.name and 'Pad' in r2.name):
                intentional += 1
            else:
                issues += 1
                print(f"    ✗ SHORT CIRCUIT: {r1.name} ↔ {r2.name}")
        
        if intentional > 0:
            print(f"    ✓ {intentional} intentional overlaps (pad-via connections)")
        
        if issues > 0:
            print(f"\n  ❌ MASK INVALID: {issues} unintended overlaps detected")
        else:
            print(f"\n  ✓ MASK VALID: All overlaps are intentional connections")
    else:
        print("  ⚠️  No overlaps found - check if connections are missing!")
    
    visualize_results(rectangles, overlaps,
                     "3_semiconductor_masks",
                     "Example 3: Semiconductor Mask Validation")


 def example_4_performance_benchmark():
    """Example 4: Performance comparison with naive algorithm."""
    print("\n" + "="*70)
    print("EXAMPLE 4: Performance Benchmark")
    print("="*70)
    
    import time
    
    print("\nComparing Scanline O(n log n) vs Naive O(n²)")
    
    sizes = [50, 100, 200, 500]
    
    print(f"\n{'N':<8} {'Scanline':<15} {'Naive':<15} {'Speedup':<10}")
    print("-" * 50)
    
    for n in sizes:
        # Generate random rectangles
        random.seed(42)
        rectangles = []
        for i in range(n):
            x1 = random.uniform(0, 1000)
            y1 = random.uniform(0, 1000)
            w = random.uniform(10, 50)
            h = random.uniform(10, 50)
            rectangles.append(Rectangle(i, x1, y1, x1 + w, y1 + h))
        
        # Time scanline algorithm
        start = time.time()
        overlaps_scanline = scanline_find_overlaps(rectangles)
        scanline_time = time.time() - start
        
        # Time naive algorithm (only for small n)
        if n <= 200:
            start = time.time()
            overlaps_naive = set()
            for i, r1 in enumerate(rectangles):
                for j, r2 in enumerate(rectangles[i+1:], i+1):
                    if r1.overlaps(r2):
                        overlaps_naive.add((i, j))
            naive_time = time.time() - start
            speedup = naive_time / scanline_time
        else:
            naive_time = None
            speedup = "N/A (too slow)"
        
        print(f"{n:<8} {scanline_time*1000:<14.2f}ms ", end="")
        if naive_time:
            print(f"{naive_time*1000:<14.2f}ms {speedup:<10.1f}x")
        else:
            print(f"{'(skipped)':<14} {speedup}")
    
    print("\n✓ Scanline algorithm scales to large datasets efficiently")
    print("  For 500 rectangles: Scanline remains fast, Naive would take ~seconds")


 def main():
    """Run all examples."""
    print("\n" + "="*70)
    print("SCANLINE ALGORITHM FOR RECTANGLE OVERLAP DETECTION")
    print("="*70)
    
    print("\nALGORITHM OVERVIEW:")
    print("━" * 70)
    print("The scanline (sweep-line) algorithm is a computational geometry")
    print("technique that efficiently finds overlapping rectangles.")
    print()
    print("How it works:")
    print("  1. Create start/end events for each rectangle's left/right edges")
    print("  2. Sort events by x-coordinate")
    print("  3. Sweep a vertical line from left to right:")
    print("     • When entering rectangle: check y-overlap with active rectangles")
    print("     • Add to active set")
    print("     • When leaving: remove from active set")
    print()
    print("Complexity: O(n log n) - much better than naive O(n²)")
    print()
    print("Applications in Semiconductor Design:")
    print("  • Design Rule Checking (DRC)")
    print("  • Mask layer validation")
    print("  • Short circuit detection")
    print("  • Component placement verification")
    print("━" * 70)
    
    # Run examples
    example_1_simple_case()
    example_2_circuit_components()
    example_3_semiconductor_masks()
    example_4_performance_benchmark()
    
    print("\n" + "="*70)
    print("SUMMARY")
    print("="*70)
    print("\n✓ Scanline algorithm efficiently detects all overlapping rectangles")
    print("✓ Red rectangles in visualizations indicate overlaps")
    print("✓ Critical for validating semiconductor mask layers")
    print("✓ O(n log n) complexity enables real-time checking on large designs")
    
    print(f"\n✓ All results saved to: {os.path.abspath(OUTPUT_DIR)}/")
    print("="*70)


 if __name__ == "__main__":
    main()
	#!/usr/bin/python3.12
	"""
	R-tree vs Quadtree: Algorithmic Comparison

	Understanding the fundamental differences between these spatial data structures
	is critical for semiconductor design applications.
	"""

	import matplotlib.pyplot as plt
	import matplotlib.patches as patches
	import random
	import os

	OUTPUT_DIR = "rtree_vs_quadtree_comparison"
	if not os.path.exists(OUTPUT_DIR):
	os.makedirs(OUTPUT_DIR)


	def visualize_comparison():
	"""Create side-by-side comparison of R-tree and Quadtree."""

	print("="*70)
	print("R-TREE VS QUADTREE: ALGORITHMIC DIFFERENCES")
	print("="*70)

	# Generate same set of rectangles for both
	random.seed(42)
	rectangles = []
	for i in range(12):
	x = random.uniform(10, 80)
	y = random.uniform(10, 80)
	w = random.uniform(5, 15)
	h = random.uniform(5, 15)
	rectangles.append((x, y, w, h, f"R{i}"))

	fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(18, 9))

	# LEFT: Quadtree approach
	ax1.set_title("QUADTREE\nSpace-driven partitioning",
	fontsize=14, fontweight='bold')
	ax1.set_xlim(0, 100)
	ax1.set_ylim(0, 100)
	ax1.set_aspect('equal')
	ax1.grid(True, alpha=0.3)

	# Draw quadtree divisions (fixed, space-based)
	ax1.axhline(50, color='red', linewidth=2, linestyle='-', alpha=0.7)
	ax1.axvline(50, color='red', linewidth=2, linestyle='-', alpha=0.7)
	ax1.axhline(25, xmax=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
	ax1.axvline(25, ymax=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
	ax1.axhline(75, xmin=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)
	ax1.axvline(75, ymin=0.5, color='orange', linewidth=1.5, linestyle='-', alpha=0.6)

	# Label quadrants
	ax1.text(25, 75, 'NW', ha='center', va='center', fontsize=16,
	bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
	ax1.text(75, 75, 'NE', ha='center', va='center', fontsize=16,
	bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
	ax1.text(25, 25, 'SW', ha='center', va='center', fontsize=16,
	bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))
	ax1.text(75, 25, 'SE', ha='center', va='center', fontsize=16,
	bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.3))

	# Draw rectangles on quadtree
	for x, y, w, h, label in rectangles:
	rect = patches.Rectangle((x, y), w, h, linewidth=2,
	edgecolor='blue', facecolor='lightblue', alpha=0.6)
	ax1.add_patch(rect)
	ax1.plot(x + w/2, y + h/2, 'ko', markersize=4)

	# RIGHT: R-tree approach
	ax2.set_title("R-TREE\nData-driven bounding boxes",
	fontsize=14, fontweight='bold')
	ax2.set_xlim(0, 100)
	ax2.set_ylim(0, 100)
	ax2.set_aspect('equal')
	ax2.grid(True, alpha=0.3)

	# Manually group rectangles into R-tree bounding boxes (simulated)
	# Group 1: bottom-left cluster
	group1_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles if x < 40 and y < 40]
	if group1_rects:
	min_x = min(r[0] for r in group1_rects)
	min_y = min(r[1] for r in group1_rects)
	max_x = max(r[0] + r[2] for r in group1_rects)
	max_y = max(r[1] + r[3] for r in group1_rects)
	bbox1 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
	linewidth=3, edgecolor='red', facecolor='none',
	linestyle='--', alpha=0.8)
	ax2.add_patch(bbox1)
	ax2.text((min_x+max_x)/2, max_y+5, 'MBR 1', ha='center', fontsize=12,
	fontweight='bold', color='red')

	# Group 2: top cluster
	group2_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles if y > 50]
	if group2_rects:
	min_x = min(r[0] for r in group2_rects)
	min_y = min(r[1] for r in group2_rects)
	max_x = max(r[0] + r[2] for r in group2_rects)
	max_y = max(r[1] + r[3] for r in group2_rects)
	bbox2 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
	linewidth=3, edgecolor='green', facecolor='none',
	linestyle='--', alpha=0.8)
	ax2.add_patch(bbox2)
	ax2.text((min_x+max_x)/2, max_y+5, 'MBR 2', ha='center', fontsize=12,
	fontweight='bold', color='green')

	# Group 3: remaining
	group3_rects = [(x, y, w, h, l) for x, y, w, h, l in rectangles
	if not (x < 40 and y < 40) and not (y > 50)]
	if group3_rects:
	min_x = min(r[0] for r in group3_rects)
	min_y = min(r[1] for r in group3_rects)
	max_x = max(r[0] + r[2] for r in group3_rects)
	max_y = max(r[1] + r[3] for r in group3_rects)
	bbox3 = patches.Rectangle((min_x-2, min_y-2), max_x-min_x+4, max_y-min_y+4,
	linewidth=3, edgecolor='purple', facecolor='none',
	linestyle='--', alpha=0.8)
	ax2.add_patch(bbox3)
	ax2.text((min_x+max_x)/2, min_y-5, 'MBR 3', ha='center', fontsize=12,
	fontweight='bold', color='purple')

	# Draw rectangles on R-tree
	for x, y, w, h, label in rectangles:
	rect = patches.Rectangle((x, y), w, h, linewidth=2,
	edgecolor='blue', facecolor='lightblue', alpha=0.6)
	ax2.add_patch(rect)

	plt.tight_layout()
	filepath = os.path.join(OUTPUT_DIR, "1_visual_comparison.png")
	plt.savefig(filepath, dpi=150, bbox_inches='tight')
	plt.close()

	print(f"\n✓ Saved: {filepath}")

	return filepath


	def create_detailed_comparison():
	"""Create detailed algorithmic comparison diagram."""

	fig = plt.figure(figsize=(16, 12))

	# Title
	fig.suptitle("Algorithmic Differences: R-tree vs Quadtree",
	fontsize=18, fontweight='bold', y=0.98)

	# Create grid for comparison
	gs = fig.add_gridspec(4, 2, hspace=0.4, wspace=0.3)

	# PARTITIONING STRATEGY
	ax1 = fig.add_subplot(gs[0, 0])
	ax1.set_title("Quadtree: Fixed Space Division", fontweight='bold')
	ax1.set_xlim(0, 100)
	ax1.set_ylim(0, 100)
	ax1.set_aspect('equal')
	ax1.axhline(50, color='red', linewidth=2)
	ax1.axvline(50, color='red', linewidth=2)
	ax1.text(50, 95, "Always divides space\ninto 4 equal quadrants",
	ha='center', fontsize=10, bbox=dict(boxstyle='round', facecolor='wheat'))
	ax1.axis('off')

	ax2 = fig.add_subplot(gs[0, 1])
	ax2.set_title("R-tree: Data-driven Grouping", fontweight='bold')
	ax2.set_xlim(0, 100)
	ax2.set_ylim(0, 100)
	ax2.set_aspect('equal')
	# Draw overlapping bounding boxes
	rect1 = patches.Rectangle((10, 10), 40, 40, linewidth=2,
	edgecolor='red', facecolor='red', alpha=0.2)
	rect2 = patches.Rectangle((35, 35), 50, 50, linewidth=2,
	edgecolor='blue', facecolor='blue', alpha=0.2)
	ax2.add_patch(rect1)
	ax2.add_patch(rect2)
	ax2.text(50, 95, "Groups objects by proximity\n(can overlap!)",
	ha='center', fontsize=10, bbox=dict(boxstyle='round', facecolor='wheat'))
	ax2.axis('off')

	# NODE STRUCTURE
	ax3 = fig.add_subplot(gs[1, 0])
	ax3.text(0.5, 0.9, "Quadtree Node Structure", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax3.transAxes)
	structure_text = """
	• Fixed: Always 4 children (NW, NE, SW, SE)
	• Boundary: Center point + width/height
	• Split criterion: Count > capacity
	• Empty quadrants: Still exist in tree
	• Example:
	Node {
	boundary: (50, 50, 100×100)
	children: [NW, NE, SW, SE]
	points: [...]
	}
	"""
	ax3.text(0.1, 0.75, structure_text, ha='left', va='top',
	fontsize=9, family='monospace', transform=ax3.transAxes)
	ax3.axis('off')

	ax4 = fig.add_subplot(gs[1, 1])
	ax4.text(0.5, 0.9, "R-tree Node Structure", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax4.transAxes)
	structure_text = """
	• Variable: m to M children (e.g., 2-8)
	• MBR: Minimum Bounding Rectangle
	• Split criterion: Overflow + minimize area
	• No empty nodes
	• Example:
	Node {
	mbr: (x1, y1, x2, y2)
	children: [MBR1, MBR2, ..., MBRn]
	entries: [...]
	}
	"""
	ax4.text(0.1, 0.75, structure_text, ha='left', va='top',
	fontsize=9, family='monospace', transform=ax4.transAxes)
	ax4.axis('off')

	# INSERTION ALGORITHM
	ax5 = fig.add_subplot(gs[2, 0])
	ax5.text(0.5, 0.95, "Quadtree Insertion", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax5.transAxes)
	algo_text = """
	1. Check if point in boundary
	2. If capacity not full: add here
	3. Else: subdivide into 4 quadrants
	4. Recursively insert into children
	5. Based on spatial position only

	Key: Deterministic - same point
	always goes to same quadrant
	"""
	ax5.text(0.05, 0.8, algo_text, ha='left', va='top',
	fontsize=9, transform=ax5.transAxes)
	ax5.axis('off')

	ax6 = fig.add_subplot(gs[2, 1])
	ax6.text(0.5, 0.95, "R-tree Insertion", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax6.transAxes)
	algo_text = """
	1. Choose subtree (minimize area increase)
	2. If node full: split node
	3. Choose split: minimize overlap & area
	4. Adjust MBRs up the tree
	5. Based on grouping heuristics

	Key: Non-deterministic - depends on
	insertion order and split strategy
	"""
	ax6.text(0.05, 0.8, algo_text, ha='left', va='top',
	fontsize=9, transform=ax6.transAxes)
	ax6.axis('off')

	# QUERY ALGORITHM
	ax7 = fig.add_subplot(gs[3, 0])
	ax7.text(0.5, 0.95, "Quadtree Query", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax7.transAxes)
	query_text = """
	Query: Find all objects in range R

	1. If boundary doesn't intersect R: STOP
	2. Check all objects in this node
	3. If subdivided:
	- Recursively query NW
	- Recursively query NE
	- Recursively query SW
	- Recursively query SE

	Prunes: Entire quadrants
	"""
	ax7.text(0.05, 0.8, query_text, ha='left', va='top',
	fontsize=9, transform=ax7.transAxes)
	ax7.axis('off')

	ax8 = fig.add_subplot(gs[3, 1])
	ax8.text(0.5, 0.95, "R-tree Query", ha='center', va='top',
	fontsize=12, fontweight='bold', transform=ax8.transAxes)
	query_text = """
	Query: Find all objects in range R

	1. If MBR doesn't intersect R: STOP
	2. If leaf: check all entries
	3. If internal:
	- For each child MBR:
	- If intersects R: recurse

	Prunes: Minimum bounding rectangles
	(can be more/less efficient
	depending on data)
	"""
	ax8.text(0.05, 0.8, query_text, ha='left', va='top',
	fontsize=9, transform=ax8.transAxes)
	ax8.axis('off')

	filepath = os.path.join(OUTPUT_DIR, "2_algorithmic_details.png")
	plt.savefig(filepath, dpi=150, bbox_inches='tight')
	plt.close()

	print(f"✓ Saved: {filepath}")


	def create_use_case_comparison():
	"""Create use-case comparison chart."""

	fig, ax = plt.subplots(figsize=(14, 10))
	ax.axis('off')

	# Title
	ax.text(0.5, 0.95, "When to Use: R-tree vs Quadtree",
	ha='center', fontsize=18, fontweight='bold', transform=ax.transAxes)

	# Create comparison table
	categories = [
	("Data Type", "Points", "Rectangles/Polygons"),
	("Dimensionality", "2D only", "2D, 3D, N-D"),
	("Distribution", "Any (adaptive)", "Clustered data (optimal)"),
	("Overlap", "No overlap in structure", "MBRs can overlap"),
	("Memory", "Higher (empty nodes)", "Lower (no empty nodes)"),
	("Balancing", "Automatic (space-based)", "Requires rebalancing"),
	("Query Speed", "Fast for uniform data", "Fast for clustered data"),
	("Insert Complexity", "O(log n)", "O(log n) avg, O(n) worst"),
	("Implementation", "Simpler", "More complex"),
	]

	y_start = 0.85
	y_step = 0.08

	# Header
	ax.text(0.25, y_start + 0.02, "QUADTREE", ha='center', fontsize=14,
	fontweight='bold', color='blue', transform=ax.transAxes)
	ax.text(0.50, y_start + 0.02, "Aspect", ha='center', fontsize=14,
	fontweight='bold', transform=ax.transAxes)
	ax.text(0.75, y_start + 0.02, "R-TREE", ha='center', fontsize=14,
	fontweight='bold', color='red', transform=ax.transAxes)

	# Draw rows
	for i, (category, quad, rtree) in enumerate(categories):
	y = y_start - (i + 1) * y_step

	# Background
	if i % 2 == 0:
	rect = patches.Rectangle((0.05, y - 0.025), 0.9, y_step * 0.9,
	facecolor='lightgray', alpha=0.3,
	transform=ax.transAxes)
	ax.add_patch(rect)

	# Category
	ax.text(0.50, y, category, ha='center', fontsize=11, fontweight='bold',
	transform=ax.transAxes)

	# Quadtree
	ax.text(0.25, y, quad, ha='center', fontsize=10, color='blue',
	transform=ax.transAxes)

	# R-tree
	ax.text(0.75, y, rtree, ha='center', fontsize=10, color='red',
	transform=ax.transAxes)

	# Use case recommendations
	y_bottom = y_start - len(categories) * y_step - 0.08

	ax.text(0.5, y_bottom, "SEMICONDUCTOR DESIGN RECOMMENDATIONS",
	ha='center', fontsize=14, fontweight='bold',
	bbox=dict(boxstyle='round', facecolor='yellow', alpha=0.5),
	transform=ax.transAxes)

	quad_cases = """
	QUADTREE:
	✓ Point data (component centers, vias)
	✓ Uniform grid layouts
	✓ 2D chip designs
	✓ Fast prototyping (simpler code)
	✓ Teaching/learning spatial structures
	✓ Memory is not critical
	"""

	rtree_cases = """
	R-TREE:
	✓ Rectangle/polygon data (masks, traces)
	✓ Clustered layouts (realistic circuits)
	✓ 3D structures (multi-layer routing)
	✓ Production systems (optimized)
	✓ Large-scale polygon operations
	✓ Minimize memory footprint
	"""

	ax.text(0.25, y_bottom - 0.15, quad_cases, ha='center', va='top', fontsize=10,
	family='monospace', bbox=dict(boxstyle='round', facecolor='lightblue', alpha=0.5),
	transform=ax.transAxes)

	ax.text(0.75, y_bottom - 0.15, rtree_cases, ha='center', va='top', fontsize=10,
	family='monospace', bbox=dict(boxstyle='round', facecolor='lightcoral', alpha=0.5),
	transform=ax.transAxes)

	filepath = os.path.join(OUTPUT_DIR, "3_use_case_comparison.png")
	plt.savefig(filepath, dpi=150, bbox_inches='tight')
	plt.close()

	print(f"✓ Saved: {filepath}")


	def main():
	"""Generate all comparison visualizations."""

	print("\n" + "█"*70)
	print("R-TREE VS QUADTREE: COMPLETE ALGORITHMIC COMPARISON")
	print("█"*70)

	print("\n" + "="*70)
	print("KEY ALGORITHMIC DIFFERENCES")
	print("="*70)

	print("\n1. PARTITIONING STRATEGY")
	print(" Quadtree: SPACE-DRIVEN")
	print(" • Divides space into 4 equal quadrants")
	print(" • Fixed, regular subdivision")
	print(" • Based on spatial coordinates")

	print("\n R-tree: DATA-DRIVEN")
	print(" • Groups objects into Minimum Bounding Rectangles (MBRs)")
	print(" • Variable number of children per node (m to M)")
	print(" • Based on object proximity and clustering")

	print("\n2. NODE STRUCTURE")
	print(" Quadtree: Always 4 children (or leaf)")
	print(" • Fixed branching factor = 4")
	print(" • Empty quadrants still exist")
	print(" • Boundary defined by center + size")

	print("\n R-tree: Variable children (e.g., 2-8)")
	print(" • Branching factor: m ≤ children ≤ M")
	print(" • No empty nodes")
	print(" • Each node stores its MBR")

	print("\n3. OVERLAP")
	print(" Quadtree: NO OVERLAP")
	print(" • Quadrants never overlap")
	print(" • Each point belongs to exactly one quadrant")

	print("\n R-tree: CAN OVERLAP")
	print(" • MBRs can overlap (inevitable with rectangles)")
	print(" • Objects may be checked multiple times in queries")

	print("\n4. INSERTION")
	print(" Quadtree:")
	print(" • Find quadrant containing point")
	print(" • If full, subdivide into 4")
	print(" • Deterministic (same point → same location)")

	print("\n R-tree:")
	print(" • Choose subtree that needs least enlargement")
	print(" • If full, split node (complex heuristics)")
	print(" • Non-deterministic (depends on insert order)")

	print("\n5. COMPLEXITY")
	print(" Quadtree:")
	print(" • Insert: O(log₄ n) = O(log n)")
	print(" • Query: O(log n) average, O(n) worst-case")
	print(" • Simple to implement")

	print("\n R-tree:")
	print(" • Insert: O(log_M n) average, O(n) worst-case")
	print(" • Query: O(log n) average for good data")
	print(" • Complex splitting algorithms")

	print("\n" + "="*70)
	print("GENERATING VISUALIZATIONS...")
	print("="*70)

	visualize_comparison()
	create_detailed_comparison()
	create_use_case_comparison()

	print("\n" + "="*70)
	print("INTERVIEW KEY POINTS")
	print("="*70)

	print("\nQuadtree:")
	print(" ✓ Pro: Simpler, faster for points, good for uniform data")
	print(" ✓ Pro: Adaptive subdivision, guaranteed O(log n) depth")
	print(" ✗ Con: Only 2D, wastes space on empty quadrants")
	print(" ✗ Con: Poor for rectangles (stores by center point)")

	print("\nR-tree:")
	print(" ✓ Pro: Optimal for rectangles/polygons, works in N dimensions")
	print(" ✓ Pro: No wasted space, better for clustered data")
	print(" ✗ Con: More complex, can have overlap, may need rebalancing")
	print(" ✗ Con: Insert order affects structure quality")

	print("\nFor Semiconductor EDA:")
	print(" • Use Quadtree for: Component placement, via locations, DRC (points)")
	print(" • Use R-tree for: Polygon masks, routing layers, large designs")
	print(" • Hybrid: Quadtree for quick prototyping, R-tree for production")

	print(f"\n✓ All visualizations saved to: {os.path.abspath(OUTPUT_DIR)}/")
	print("="*70)


	if __name__ == "__main__":
	main()
	#!/usr/bin/python3.12
	from quads import QuadTree, Point, visualize, BoundingBox


	points = [ Point(50, 50), Point(200, 70),
	Point(100, 180), Point(220, 220),
	Point(30, 150) ]

	width, height = 512, 512
	tree = QuadTree((0, 0), width, height)
	[tree.insert(p) for p in points]
	visualize(tree)

	# You can also perform queries, e.g., finding points within a region
	bb = BoundingBox(min_x=40, min_y=40, max_x=120, max_y=120)
	found_points = tree.within_bb(bb)
	print(f"\nPoints found in region {bb}:")
	for p in found_points:
	print(f" {p.x}, {p.y}")
	#!/usr/bin/python3.12
	"""
	Scanline Algorithm for Rectangle Overlap Detection

	The scanline algorithm is a sweep-line technique that efficiently finds
	overlapping rectangles in O(n log n) time, much better than the naive O(n²).

	Critical for semiconductor design:
	- Design Rule Checking (DRC)
	- Mask layer validation
	- Component overlap detection
	"""

	import matplotlib.pyplot as plt
	import matplotlib.patches as patches
	from dataclasses import dataclass
	from typing import List, Set, Tuple
	import random
	import os

	OUTPUT_DIR = "scanline_results"
	if not os.path.exists(OUTPUT_DIR):
	os.makedirs(OUTPUT_DIR)


	@dataclass
	class Rectangle:
	"""Rectangle representation."""
	id: int
	x1: float # Left
	y1: float # Bottom
	x2: float # Right
	y2: float # Top
	name: str = ""

	def __post_init__(self):
	if not self.name:
	self.name = f"R{self.id}"

	def overlaps(self, other: 'Rectangle') -> bool:
	"""Check if two rectangles overlap."""
	return not (self.x2 <= other.x1 or # self is completely to the left
	self.x1 >= other.x2 or # self is completely to the right
	self.y2 <= other.y1 or # self is completely below
	self.y1 >= other.y2) # self is completely above

	def __repr__(self):
	return f"{self.name}[({self.x1},{self.y1})-({self.x2},{self.y2})]"


	@dataclass
	class Event:
	"""Sweep line event."""
	x: float # X-coordinate of event
	rect_id: int # Rectangle ID
	is_start: bool # True if entering rectangle, False if leaving
	y1: float # Bottom y
	y2: float # Top y

	def __lt__(self, other):
	"""For sorting events by x-coordinate."""
	if self.x != other.x:
	return self.x < other.x
	# If same x, process end events before start events
	# This prevents false positives for touching rectangles
	return not self.is_start and other.is_start


	class IntervalTree:
	"""
	Simple interval tree for 1D overlap detection.
	Used to find overlapping y-intervals when scanline is at position x.
	"""

	def __init__(self):
	self.intervals = [] # List of (y1, y2, rect_id)

	def insert(self, y1: float, y2: float, rect_id: int):
	"""Insert a y-interval."""
	self.intervals.append((y1, y2, rect_id))

	def remove(self, rect_id: int):
	"""Remove all intervals for a rectangle."""
	self.intervals = [(y1, y2, rid) for y1, y2, rid in self.intervals
	if rid != rect_id]

	def find_overlaps(self, y1: float, y2: float, rect_id: int) -> List[int]:
	"""Find all intervals that overlap with [y1, y2]."""
	overlaps = []
	for interval_y1, interval_y2, interval_id in self.intervals:
	if interval_id != rect_id: # Don't compare with self
	# Check if intervals overlap
	if not (y2 <= interval_y1 or y1 >= interval_y2):
	overlaps.append(interval_id)
	return overlaps


	def scanline_find_overlaps(rectangles: List[Rectangle]) -> Set[Tuple[int, int]]:
	"""
	Use scanline algorithm to find all overlapping rectangle pairs.

	Algorithm:
	1. Create events for each rectangle (start and end)
	2. Sort events by x-coordinate
	3. Sweep from left to right:
	- When entering a rectangle: check y-overlap with active rectangles
	- Add rectangle to active set
	- When leaving: remove from active set

	Returns:
	Set of overlapping pairs (id1, id2) where id1 < id2
	"""
	print("\n" + "="*70)
	print("SCANLINE ALGORITHM: Finding Overlapping Rectangles")
	print("="*70)

	# Step 1: Create events
	events = []
	for rect in rectangles:
	# Start event (entering rectangle)
	events.append(Event(rect.x1, rect.id, True, rect.y1, rect.y2))
	# End event (leaving rectangle)
	events.append(Event(rect.x2, rect.id, False, rect.y1, rect.y2))

	# Step 2: Sort events by x-coordinate
	events.sort()

	print(f"\nProcessing {len(rectangles)} rectangles...")
	print(f"Created {len(events)} events (2 per rectangle)")

	# Step 3: Sweep through events
	active_intervals = IntervalTree() # Currently active rectangles
	overlaps = set() # Store overlapping pairs

	print("\nSweeping left to right:")
	current_x = None
	event_count = 0

	for event in events:
	if current_x is None or event.x != current_x:
	if current_x is not None:
	event_count += 1
	current_x = event.x

	if event.is_start:
	# Entering a rectangle: check for y-overlaps with active rectangles
	overlapping_ids = active_intervals.find_overlaps(
	event.y1, event.y2, event.rect_id
	)

	# Record overlaps
	for other_id in overlapping_ids:
	pair = tuple(sorted([event.rect_id, other_id]))
	overlaps.add(pair)
	if len(overlaps) <= 5: # Print first few
	rect1 = rectangles[event.rect_id]
	rect2 = rectangles[other_id]
	print(f" Overlap found: {rect1.name} ↔ {rect2.name}")

	# Add to active set
	active_intervals.insert(event.y1, event.y2, event.rect_id)
	else:
	# Leaving a rectangle: remove from active set
	active_intervals.remove(event.rect_id)

	if len(overlaps) > 5:
	print(f" ... and {len(overlaps) - 5} more overlaps")

	print(f"\n✓ Found {len(overlaps)} overlapping pairs")
	print(f"✓ Processed {event_count} distinct x-coordinates")

	return overlaps


	def visualize_results(rectangles: List[Rectangle],
	overlapping_pairs: Set[Tuple[int, int]],
	filename: str = "scanline_overlap_detection",
	title: str = "Scanline Overlap Detection"):
	"""Visualize rectangles with overlaps highlighted in red."""

	# Determine which rectangles are involved in overlaps
	overlapping_ids = set()
	for id1, id2 in overlapping_pairs:
	overlapping_ids.add(id1)
	overlapping_ids.add(id2)

	fig, ax = plt.subplots(figsize=(14, 12))

	# Draw all rectangles
	for rect in rectangles:
	is_overlapping = rect.id in overlapping_ids
	color = 'red' if is_overlapping else 'blue'
	alpha = 0.5 if is_overlapping else 0.3
	linewidth = 2 if is_overlapping else 1

	rect_patch = patches.Rectangle(
	(rect.x1, rect.y1),
	rect.x2 - rect.x1,
	rect.y2 - rect.y1,
	linewidth=linewidth,
	edgecolor=color,
	facecolor=color,
	alpha=alpha,
	label=rect.name if is_overlapping else None
	)
	ax.add_patch(rect_patch)

	# Add label
	center_x = (rect.x1 + rect.x2) / 2
	center_y = (rect.y1 + rect.y2) / 2
	ax.text(center_x, center_y, rect.name,
	ha='center', va='center',
	fontsize=8, fontweight='bold',
	color='white' if is_overlapping else 'black')

	# Set plot properties
	all_x = [r.x1 for r in rectangles] + [r.x2 for r in rectangles]
	all_y = [r.y1 for r in rectangles] + [r.y2 for r in rectangles]
	margin_x = (max(all_x) - min(all_x)) * 0.1
	margin_y = (max(all_y) - min(all_y)) * 0.1

	ax.set_xlim(min(all_x) - margin_x, max(all_x) + margin_x)
	ax.set_ylim(min(all_y) - margin_y, max(all_y) + margin_y)
	ax.set_aspect('equal')
	ax.grid(True, alpha=0.3)
	ax.set_xlabel('X (nm)', fontsize=12, fontweight='bold')
	ax.set_ylabel('Y (nm)', fontsize=12, fontweight='bold')
	ax.set_title(title, fontsize=16, fontweight='bold', pad=20)

	# Add legend
	blue_patch = patches.Patch(color='blue', alpha=0.3, label='No overlap')
	red_patch = patches.Patch(color='red', alpha=0.5, label='Overlapping')
	ax.legend(handles=[blue_patch, red_patch], loc='upper right', fontsize=11)

	# Add statistics box
	stats_text = f"Total rectangles: {len(rectangles)}\n"
	stats_text += f"Overlapping: {len(overlapping_ids)}\n"
	stats_text += f"Overlap pairs: {len(overlapping_pairs)}\n"
	stats_text += f"Algorithm: O(n log n)"

	ax.text(0.02, 0.98, stats_text, transform=ax.transAxes,
	verticalalignment='top',
	bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.8),
	fontsize=10, family='monospace')

	plt.tight_layout()
	filepath = os.path.join(OUTPUT_DIR, f"{filename}.png")
	plt.savefig(filepath, dpi=150, bbox_inches='tight')
	plt.close()

	print(f"\n✓ Visualization saved: {filepath}")
	return filepath


	def example_1_simple_case():
	"""Example 1: Simple case with obvious overlaps."""
	print("\n" + "="*70)
	print("EXAMPLE 1: Simple Case")
	print("="*70)

	rectangles = [
	Rectangle(0, 10, 10, 40, 30, "A"), # id, x1, y1, x2, y2, name
	Rectangle(1, 20, 20, 50, 40, "B"), # Overlaps with A
	Rectangle(2, 45, 15, 70, 35, "C"), # Overlaps with B
	Rectangle(3, 80, 10, 100, 30, "D"), # No overlap
	Rectangle(4, 15, 50, 35, 70, "E"), # No overlap
	Rectangle(5, 55, 50, 75, 70, "F"), # No overlap
	]

	print("\nRectangles:")
	for rect in rectangles:
	print(f" {rect}")

	overlaps = scanline_find_overlaps(rectangles)

	print("\nOverlapping pairs:")
	for id1, id2 in sorted(overlaps):
	print(f" {rectangles[id1].name} ↔ {rectangles[id2].name}")

	visualize_results(rectangles, overlaps,
	"1_simple_case",
	"Example 1: Simple Overlap Detection")


	def example_2_circuit_components():
	"""Example 2: Realistic circuit component layout."""
	print("\n" + "="*70)
	print("EXAMPLE 2: Circuit Component Layout")
	print("="*70)

	print("\nScenario: Detecting overlapping components in PCB layout")

	random.seed(42)
	rectangles = []

	# Create realistic component layout
	component_types = [
	("IC", 40, 40),
	("Resistor", 20, 8),
	("Capacitor", 15, 15),
	("Connector", 30, 10),
	]

	for i in range(30):
	comp_type, w, h = random.choice(component_types)
	x1 = random.uniform(0, 400)
	y1 = random.uniform(0, 300)

	rectangles.append(Rectangle(i, x1, y1, x1 + w, y1 + h, f"{comp_type}{i}"))

	print(f"\nGenerated {len(rectangles)} components")

	overlaps = scanline_find_overlaps(rectangles)

	if overlaps:
	print(f"\n⚠️ WARNING: {len(overlaps)} overlapping pairs detected!")
	print("These would cause manufacturing issues:")
	for id1, id2 in list(overlaps)[:5]:
	print(f" • {rectangles[id1].name} overlaps {rectangles[id2].name}")
	if len(overlaps) > 5:
	print(f" ... and {len(overlaps) - 5} more")
	else:
	print("\n✓ No overlaps detected - layout is valid")

	visualize_results(rectangles, overlaps,
	"2_circuit_layout",
	"Example 2: Circuit Component Overlap Detection (DRC)")


	def example_3_semiconductor_masks():
	"""Example 3: Semiconductor mask layer validation."""
	print("\n" + "="*70)
	print("EXAMPLE 3: Semiconductor Mask Layer Validation")
	print("="*70)

	print("\nScenario: Validating metal trace layer for short circuits")

	rectangles = []

	# Metal traces (horizontal and vertical)
	# Horizontal traces
	rectangles.append(Rectangle(0, 10, 100, 200, 110, "Trace_H1"))
	rectangles.append(Rectangle(1, 50, 150, 250, 160, "Trace_H2"))
	rectangles.append(Rectangle(2, 100, 200, 300, 210, "Trace_H3"))

	# Vertical traces
	rectangles.append(Rectangle(3, 150, 50, 160, 250, "Trace_V1"))
	rectangles.append(Rectangle(4, 220, 80, 230, 220, "Trace_V2"))

	# Contact pads
	rectangles.append(Rectangle(5, 140, 90, 170, 120, "Pad1")) # Overlaps V1
	rectangles.append(Rectangle(6, 210, 140, 240, 170, "Pad2")) # Overlaps H2 and V2
	rectangles.append(Rectangle(7, 280, 190, 310, 220, "Pad3")) # Overlaps H3

	# Vias
	rectangles.append(Rectangle(8, 155, 105, 160, 110, "Via1")) # Inside Pad1
	rectangles.append(Rectangle(9, 225, 155, 230, 160, "Via2")) # Inside Pad2

	print(f"\nMask layer contains:")
	print(f" - {len([r for r in rectangles if 'Trace' in r.name])} traces")
	print(f" - {len([r for r in rectangles if 'Pad' in r.name])} contact pads")
	print(f" - {len([r for r in rectangles if 'Via' in r.name])} vias")

	overlaps = scanline_find_overlaps(rectangles)

	print(f"\nValidation results:")
	if overlaps:
	print(f" ⚠️ Found {len(overlaps)} potential issues:")

	# Categorize overlaps
	intentional = 0
	issues = 0

	for id1, id2 in overlaps:
	r1, r2 = rectangles[id1], rectangles[id2]
	# Pad-Via overlaps are intentional (connections)
	if ('Pad' in r1.name and 'Via' in r2.name) or \
	('Via' in r1.name and 'Pad' in r2.name):
	intentional += 1
	else:
	issues += 1
	print(f" ✗ SHORT CIRCUIT: {r1.name} ↔ {r2.name}")

	if intentional > 0:
	print(f" ✓ {intentional} intentional overlaps (pad-via connections)")

	if issues > 0:
	print(f"\n ❌ MASK INVALID: {issues} unintended overlaps detected")
	else:
	print(f"\n ✓ MASK VALID: All overlaps are intentional connections")
	else:
	print(" ⚠️ No overlaps found - check if connections are missing!")

	visualize_results(rectangles, overlaps,
	"3_semiconductor_masks",
	"Example 3: Semiconductor Mask Validation")


	def example_4_performance_benchmark():
	"""Example 4: Performance comparison with naive algorithm."""
	print("\n" + "="*70)
	print("EXAMPLE 4: Performance Benchmark")
	print("="*70)

	import time

	print("\nComparing Scanline O(n log n) vs Naive O(n²)")

	sizes = [50, 100, 200, 500]

	print(f"\n{'N':<8} {'Scanline':<15} {'Naive':<15} {'Speedup':<10}")
	print("-" * 50)

	for n in sizes:
	# Generate random rectangles
	random.seed(42)
	rectangles = []
	for i in range(n):
	x1 = random.uniform(0, 1000)
	y1 = random.uniform(0, 1000)
	w = random.uniform(10, 50)
	h = random.uniform(10, 50)
	rectangles.append(Rectangle(i, x1, y1, x1 + w, y1 + h))

	# Time scanline algorithm
	start = time.time()
	overlaps_scanline = scanline_find_overlaps(rectangles)
	scanline_time = time.time() - start

	# Time naive algorithm (only for small n)
	if n <= 200:
	start = time.time()
	overlaps_naive = set()
	for i, r1 in enumerate(rectangles):
	for j, r2 in enumerate(rectangles[i+1:], i+1):
	if r1.overlaps(r2):
	overlaps_naive.add((i, j))
	naive_time = time.time() - start
	speedup = naive_time / scanline_time
	else:
	naive_time = None
	speedup = "N/A (too slow)"

	print(f"{n:<8} {scanline_time*1000:<14.2f}ms ", end="")
	if naive_time:
	print(f"{naive_time*1000:<14.2f}ms {speedup:<10.1f}x")
	else:
	print(f"{'(skipped)':<14} {speedup}")

	print("\n✓ Scanline algorithm scales to large datasets efficiently")
	print(" For 500 rectangles: Scanline remains fast, Naive would take ~seconds")


	def main():
	"""Run all examples."""
	print("\n" + "="*70)
	print("SCANLINE ALGORITHM FOR RECTANGLE OVERLAP DETECTION")
	print("="*70)

	print("\nALGORITHM OVERVIEW:")
	print("━" * 70)
	print("The scanline (sweep-line) algorithm is a computational geometry")
	print("technique that efficiently finds overlapping rectangles.")
	print()
	print("How it works:")
	print(" 1. Create start/end events for each rectangle's left/right edges")
	print(" 2. Sort events by x-coordinate")
	print(" 3. Sweep a vertical line from left to right:")
	print(" • When entering rectangle: check y-overlap with active rectangles")
	print(" • Add to active set")
	print(" • When leaving: remove from active set")
	print()
	print("Complexity: O(n log n) - much better than naive O(n²)")
	print()
	print("Applications in Semiconductor Design:")
	print(" • Design Rule Checking (DRC)")
	print(" • Mask layer validation")
	print(" • Short circuit detection")
	print(" • Component placement verification")
	print("━" * 70)

	# Run examples
	example_1_simple_case()
	example_2_circuit_components()
	example_3_semiconductor_masks()
	example_4_performance_benchmark()

	print("\n" + "="*70)
	print("SUMMARY")
	print("="*70)
	print("\n✓ Scanline algorithm efficiently detects all overlapping rectangles")
	print("✓ Red rectangles in visualizations indicate overlaps")
	print("✓ Critical for validating semiconductor mask layers")
	print("✓ O(n log n) complexity enables real-time checking on large designs")

	print(f"\n✓ All results saved to: {os.path.abspath(OUTPUT_DIR)}/")
	print("="*70)


	if __name__ == "__main__":
	main()