Created
March 13, 2026 15:44
-
-
Save chadbrewbaker/523f4608ba182120f7f172c8530671e8 to your computer and use it in GitHub Desktop.
Contiguous art gallery problem with epsilon overlap
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # vibe code of https://arxiv.org/pdf/2511.02960 via Google Gemeni 3 flash preview | |
| import numpy as np | |
| class EpsilonRobustGallerySolver: | |
| def __init__(self, vertices, epsilon=0.1): | |
| self.vertices = [np.array(v, dtype=float) for v in vertices] | |
| self.n = len(vertices) | |
| self.epsilon = epsilon | |
| self.edges = [(self.vertices[i], self.vertices[(i+1)%self.n]) for i in range(self.n)] | |
| self.lengths = [np.linalg.norm(e[1]-e[0]) for e in self.edges] | |
| self.total_L = sum(self.lengths) | |
| def get_pt(self, d): | |
| d %= self.total_L | |
| acc = 0 | |
| for i, length in enumerate(self.lengths): | |
| if acc <= d <= acc + length + 1e-7: | |
| t = (d - acc) / length if length > 0 else 0 | |
| return self.vertices[i] + t * (self.vertices[(i+1)%self.n] - self.vertices[i]) | |
| acc += length | |
| return self.vertices[0] | |
| def is_visible(self, guard, p): | |
| """Checks if guard can see point p without hitting an edge.""" | |
| for e1, e2 in self.edges: | |
| # Standard segment intersection | |
| if self._intersect(guard, p, e1, e2): | |
| # Ignore endpoint grazing | |
| if min(np.linalg.norm(p-e1), np.linalg.norm(p-e2), | |
| np.linalg.norm(guard-e1), np.linalg.norm(guard-e2)) > 1e-4: | |
| return False | |
| return True | |
| def _intersect(self, p1, p2, p3, p4): | |
| def ccw(A, B, C): | |
| return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0]) | |
| return ccw(p1,p3,p4) != ccw(p2,p3,p4) and ccw(p1,p2,p3) != ccw(p1,p2,p4) | |
| def find_f(self, start_d, max_jump): | |
| """Finds furthest point v visible from a single guard point.""" | |
| # Candidates include vertices and the centroid | |
| guards = self.vertices + [np.mean(self.vertices, axis=0)] | |
| low, high, best = 0, max_jump, 0 | |
| for _ in range(12): | |
| mid = (low + high) / 2 | |
| possible = False | |
| for g in guards: | |
| # To ensure the WHOLE segment is visible, we sample | |
| if all(self.is_visible(g, self.get_pt(start_d + s)) for s in np.linspace(0, mid, 8)): | |
| possible = True | |
| break | |
| if possible: | |
| best = mid | |
| low = mid | |
| else: | |
| high = mid | |
| return best | |
| def solve(self): | |
| best_partition = [] | |
| min_guards = float('inf') | |
| # Try starting the greedy process from different points (the X set) | |
| for i in range(self.n): | |
| start_pos = sum(self.lengths[:i]) | |
| current_d = start_pos | |
| segments = [] | |
| covered_dist = 0 | |
| # We need to cover the total length plus the overlaps | |
| while covered_dist < self.total_L: | |
| jump = self.find_f(current_d, self.total_L) | |
| # If we can't even jump past the epsilon, the polygon is too tight | |
| if jump <= self.epsilon: | |
| break | |
| end_d = current_d + jump | |
| segments.append((current_d % self.total_L, end_d % self.total_L)) | |
| # MOVE FORWARD, but pull back by epsilon for the next start | |
| current_d = end_d - self.epsilon | |
| covered_dist += (jump - self.epsilon) | |
| if covered_dist >= self.total_L - self.epsilon and len(segments) < min_guards: | |
| min_guards = len(segments) | |
| best_partition = segments | |
| return best_partition | |
| # --- Testing the Epsilon Solver --- | |
| snake = [(0,0), (10,0), (10,2), (2,2), (2,4), (10,4), (10,6), (0,6), (0,4), (8,4), (8,2), (0,2)] | |
| solver = EpsilonRobustGallerySolver(snake, epsilon=0.5) | |
| result = solver.solve() | |
| print(f"--- Robust Contiguous Partition (Epsilon = 0.5) ---") | |
| print(f"Number of Guards: {len(result)}") | |
| for i, (s, e) in enumerate(result): | |
| overlap_str = f" [Next starts at {e-0.5:.2f}]" if i < len(result)-1 else " [Final Overlap]" | |
| print(f" Guard {i+1}: {s:5.2f} to {e:5.2f} {overlap_str}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment