Given multiple 2D points and circles, find all points that are enclosed by a chain of circles?

Revision en2, by pabloskimg, 2018-10-12 00:43:10

Given a lot of points and circles, you have to find all points that are either inside a circle or surrounded by a closed loop of circles (a sequence of circles of some length N such that circle i intersects circle (i+1)%N). For example, in the picture below, all red points would be points satisfying the aforementioned condition:

I need to figure this out in order to solve this problem.

I guess I need to build a graph where circles are nodes and add edges between circles intersecting each other. Then I would have to find somehow maximal cycles in this graph, for each maximal cycle find the corresponding maximal polygon formed by connecting the centers of circles in the maximal cycle with segments in counter-clockwise order, and finally for each point check if it's contained by one of these maximal polygons. I've got no idea of how to do anything of this :(

Tags #geometry, #circle


  Rev. Lang. By When Δ Comment
en3 English pabloskimg 2018-10-13 22:15:15 137
en2 English pabloskimg 2018-10-12 00:43:10 9
en1 English pabloskimg 2018-09-29 20:27:31 1120 Initial revision (published)