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

Правка en2, от 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 :(

Теги #geometry, #circle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский pabloskimg 2018-10-13 22:15:15 137
en2 Английский pabloskimg 2018-10-12 00:43:10 9
en1 Английский pabloskimg 2018-09-29 20:27:31 1120 Initial revision (published)