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. UPDATE: solutions can be submitted here: http://poj.org/problem?id=2863, if you solve it, please let me know which strategy you used :D
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 :(
First lets remove the points which are fully inside of a circle. This can be easily done in O((number of points)*(number of curcles)).
In O(1) you can find the intersection of two circles. Now let's fix every two circles and create a vertex (in terms of graph theory) for every intersection point. The edges of our graph will be between two consecutive intersection points of each circle. By this I mean that if the vertices laying on a circle are V0, V1, ..., Vk - 1, sorted in clockwise order based on the circle's center, we will have an edge between Vi and
for each i.
Now for each connected component, we can find the largest polygon — start from the point with lowest Y and go in counter clockwise direction. After you have found the polygon, just go through the points and find the set of those, that are inside of it.
PS: As the graph is planar, we can also just find all the faces and then find the points in each of them. This will be easier to implement but will be slower (although it will pass for the given constraints — the number of vertices in the graph is at most M * (M - 1) which is ~900).
"Now for each connected component, we can find the largest polygon — start from the point with lowest Y and go in counter clockwise direction" How do you exactly do that? A connected component could be a tree (think of a tree of circles tangentially touching each other) or it could contain nodes which are not part of a cycle. Maybe the point with lowest Y is not part of a cycle. Or actually there could be many cycles. For instance, imagine a cycle of circles at the left, a cycle of circles at the right and a horizontal bridge of circles connecting the 2 cycles in between. How do you handle those tricky cases?
"As the graph is planar, we can also just find all the faces and then find the points in each of them" I think the graph is not necessarily planar. Imagine a huge circle intersecting many other circles. That would create edges that would cross each other, right? So the corresponding graph in that case would not be planar, am I correct?
I agree with the first part (although I'm pretty sure with some corner cases it will be doable), but I disagree with the fact that the graph might not be planar.
In the sample you mentioned the graph clearly is planar (we will have ~2*M vertices — on each small circle we will have two of them and thr graph will look like a convex polygon with ~2*M vertices). Some of the connections might be the same (if two vertices are consequtive in two or more circles), but this isn't an intersection — we will simply keep these edges only once.
Hi, I'm back to this problem again. I'm trying to understand your approach, but I'm not sure if I understood the graph construction correctly. In the figure below, is the graph drawn correctly?
The graph indeed looks planar. In order to find the maximal cycles, how would you deal with bridges connecting 2 or more maximal cycles?
Another approach to exclude all informers that are outside the range of any radar, but are unreachable because they are located inside an area surrounded by overlapping and/or tangent radar areas, is to draw a line segment between the location of each two radars whose ranges are tangent or overlapping circles. If this procedure creates any polygon, then any informer located inside such polygon is unreachable. The advantage of this approach is that it only requires testing that a pair of circles Ci and Cj are tangent or overlapping in terms of the location of their centers (Xi, Yi) and (Xj, Yj) and their radii Ri and Rj without computing their tangent point or their two intersection points.
Circles Ci and Cj are tangent or overlapping if and only if
(Xj - Xi)2 + (Yj - Yi)2 ≤ (Ri + Rj)2
In this case, a line segment is drawn between (Xi, Yi) and (Xj, Xj).
Note that as all numbers in this relational expression are integers, the test can be performed without using floating-point numbers.
Such a graph would not be planar though (some edges might cross each other), which might cause some trouble when you try to find maximal cycles in the graph, right?
It's right that the graph may not be planner if two line segments intersect. But the suggested approach should be still valid. If an intersection point of two line segments exists, it should not create a new vertex in the graph.
But ok, let's say we build a graph using your approach. How would you then find maximal cycles in such a graph?
Depth-first search may be used, provided that:
maximal cycles can share at most one node
their edges do not intersect, and
each edge either belongs to at most one maximal cycle or does not belong to any maximal cycle, i.e. two maximal cycles cannot share an edge.
Hope that helps.
Wait, I think it can be done even easier than that. There is no need to find "maximal" cycles. Just finding many redundant cycles should be fine. For each connected component you run DFS, and every time you find a back-edge, the nodes at the top of the stack form a cycle, and therefore a polygon. No, wait again. What if the polygon just found is not simple (i.e. edges cross each other)? Checking if a point is inside a non-simple polygon might have different answers depending on whether you use nonzero rule or even-odd rule :S
In the figure shown your blog, if two chains of circles overlap, then it should be possible to merge them into one chain, i.e. they should actually belong to the same connected component.
RE: if the polygon is not simple
DFS the present connected component should consider the second condition, the new edge added to the path does not intersect with any edge that already exists in the partial solution.
I think it would be easier to understand what you say if you explain how you would deal with this tricky case:
In the figure above the DFS could generate a complex polygon (following the red edges). If your DFS happens to generate such polygon, how would you deal with it?
Can you share the centers and the radii of the circles used to generate this tricky case as static integer arrays in an empty C++ program?
I would like to check this data further if possible.
You may use ideone.com to store such program and share it is a public link.
I have three quick observations about this figure:
Firstly, it contains at least one node which is not located at the center of any circle.
Secondly, it contains at least one pair of overlapping circle for which no edge exists between their centers.
Thirdly, the number of radars is larger than 30. In the problem statement, it is mentioned that the number of radars M should be between 1 and 30.
Note that one simple polygon passing through a subset of the locations of the radars, and surrounding all the yellow-colored areas, should be sufficient to exclude any unreachable informer that may exist inside such areas.
Sorry, the figure above had some errors. Check this new figure out:
Let's say you run DFS and DFS follows the red edges, and when the first back-edge in the DFS is encountered, the resulting polygon is the complex polygon highlighted by the red edges in the figure. How would you deal with such complex polygon?
Again, the number of circles in this modified figure is larger than 30.
It is possible to augment each edge with a boolean flag to make sure that DFS can visit any edge at most once in each cycle.
On the other hand, it may be more efficient than DFS to adopt a modified version of Graham's scan convex-hull algorithm. In particular, start at the unchecked radar with the left-most (least X) down-most (least Y) coordinates. Then, choose the next neighbor overlapping radar according to a particular ordering criterion until the first radar is reached again. Iterate through unchecked radars in case that other chains exist.
Note that unlike the original Graham's can algorithm, the polygon generated by this modified algorithm does not have to be convex.
You are right, I used too many circles in the last figure. Hopefully this figure should be alright:
For simplicity I just drew the red edges that would form the complex polygon, and I omitted the other edges. If I counted correctly, there are only 28 circles in the figure.
With respect to your modified version of graham scan, I think it would work correctly if the graph is planar, as in the graph construction proposed by @radoslav11 (read first comment). But if the graph has crossing edges as in the figure above, then I think your algorithm could fail taking the wrong directions.
I think the best solution would be to build a planar graph using @radoslav11 approach, and then use DFS with no worries for crossing edges.
It seems that you omitted the second rule again.
By definition, edges of a simple polygon DO NOT intersect, i.e. a new edge should NOT be added to the present path if it intersects with an edge that already exists in such path.
If this rule is applied, then the generated polygon should always be a simple polygon.
I see 2 issues with this: 1) how would you implement this DFS? 2) it could happen that your DFS run out of options at a certain node, i.e., you get to a node in which any remaining edge connected to it would violate your second rule with respect to the path traveled so far.
If you don't mind, I think it would be great if you implement your solution to the problem and upload the code. You can submit solutions to the problem here: http://poj.org/problem?id=2863