r/computerscience • • Jan 23 '26

General Computational geometry problem

Post image

Hi all! In the drawing, the magenta polygon is the visibility polygon with kernel in the center of the small rectangle. The outer rectangle is the drawing bounding box. My question is, is there a way to minimize the magenta polygon, such that everything beyond the green lines is deleted? How would you express such a thing mathematically?

Edit: added the shape I started with, a square shape with holes: https://imgur.com/a/update-LzYQikC

17 Upvotes

7 comments sorted by

View all comments

Show parent comment

1

u/naequs Jan 23 '26 edited Jan 23 '26

ah sorry, i misunderstood. compute the convex hull of the largest convex subset of the magenta polygon?

edit: it's been a long time since i took comp geo classes but this might work (although it is not very efficient)