I'm working with 2D shapes represented by their boundary contours (as ordered x,y coordinates), and I want to check if a shape is star-convex. If it is, I'd like to find a star center — i.e., a point from which the entire shape is visible (meaning: every line segment to every boundary point lies entirely within the shape).? Is there an elaborate non heuristic way of doing so? If there is already a python code for this then it would be even better This is what I have tried so far: I implemented a heuristic approach based on a midpoint visibility test. The idea is: A point is a valid star center if, for every boundary point, the midpoint of the line segment between them lies inside the polygon. I sample candidate points starting from the centroid, perturb them randomly within the bounding box, and check if one satisfies the condition. but this doesn't really guarantee finding the star-center or checking if it star-convex. There's also no guarantee that random sampling will find the right region (kernel) in the first place. def is_star_convex_and_get_center(x, y, n_samples=500): coords = np.column_stack((x, y)) poly = Polygon(coords) if not poly.is_valid or poly.area == 0: print("Invalid shape.") return None # Try centroid first candidates = [np.mean(coords, axis=0)] # Add some random points around the centroid bbox = poly.bounds scale = max(bbox[2] - bbox[0], bbox[3] - bbox[1]) for _ in range(n_samples - 1): offset = (np.random.rand(2) - 0.5) * scale candidates.append(candidates[0] + offset) # Check visibility condition for each candidate for pt in candidates: visible = True for px, py in coords: mid = 0.5 * (pt + np.array([px, py])) if not poly.contains(Point(mid)): visible = False break if visible: return pt # pt is a valid star center # No valid star center found return None Continue reading...
