21
3
Given the coordinates of several points on a plane, and the radius of a circle surrounding each point, draw polygons representing the circles and the edges where the circles meet. Straight edges will always fall along circle-circle intersection lines, but might not follow the full length of these lines.
Per mbomb007's suggestion, imagine the behavior of 2D soap bubbles. That's technically wrong, because soap bubbles would always meet at 120° angles to minimize energy, while these circles may meet at any angle.
This is a Voronoi diagram, minus a defined area plane. Thanks Andreas. This is actually a generalization of a Voronoi diagram called a power diagram.
Examples
For example, given two points and two radii, the output might look like this:
Add another point and radius and the output might look like this:
Input
You can structure the input however you wish. Please post results with the following inputs.
Test 1
- x: 10, y: 10, r: 10
- x: 25, y: 12, r: 8
Test 2
- x: 8, y: 10, r: 6
- x: 20, y: 8, r: 4
- x: 18, y: 20, r: 12
Output
Output should be graphical and should include polygon borders, but nothing else is required. Points and intersections do not need to be represented like they are in the examples.
Constraints
- No point will exist within the radius of another circle.
- Standard codegolf rules.
- No answers with loopholes will be accepted, but feel free to have fun with it.
What do the edges in Fig. 2 radiate outwards from a point which is not a point of intersection? Shouldn't the edges be from intersection point to intersection point? My understanding is that the polygon in Fig. 2 should be a triangle. – DavidC – 2016-07-01T15:24:04.573
I was assuming he was using the Radical Center, which is the point of intersection of their pairwise radical lines.
– Neil – 2016-07-01T15:29:59.407I find my intentions difficult to articulate. Imagine that the circles are all slowly expanding from their points. A circle will stop this expansion on an edge when it encounters another circle. The circle's unencumbered edges will continue to expand until they reach their specified radius. I don't have a strong background in geometry or math, so I apologize for perhaps not speaking accurately. Please feel free to add clarification to the question if you get my meaning. – Rip Leeb – 2016-07-01T15:37:51.627
Nate, the algorithm in your last comment is not well-defined: we don't know what rate each circle is expanding at, so we don't know where the line is. If you do mean the radical center (see the links in @Neil 's comment), I suggest you [edit] the question to indicate as much.
– msh210 – 2016-07-01T15:44:48.423Nate, Finding the points of intersection of circles is clear. How do you define the point in Fig. 2 where the three line segments meet? How do you define (or at least describe) the line segments themselves? The line segment in Fig. 1 is simply the line segment between the two points of intersection. – DavidC – 2016-07-01T15:57:25.997
1You should change the title to mention bubbles. These look like 2D bubbles. – mbomb007 – 2016-07-01T16:44:10.113
I appreciate the input and I've added more detail at the top. I hope that the bit about circle-circle intersection lines will provide enough clarification. – Rip Leeb – 2016-07-01T17:03:27.760
Your test2 does not match the picture. – LLlAMnYP – 2016-07-01T17:06:00.427
3
You're asking for the Voronoi tessellation of a plane given a set of points: https://en.wikipedia.org/wiki/Voronoi_diagram
– Andreas – 2016-07-01T17:10:38.217@LLlAMnYP, nor does the first. They are not intended to match. – Rip Leeb – 2016-07-01T17:14:56.967
3In a Voronoi diagram, "for each seed [point] there is a corresponding region consisting of all points closer to that seed than to any other". That is clearly not the case for Figure 2. – DavidC – 2016-07-01T18:17:41.937
2@Andreas DavidC is right, this would be a Voronoi diagram only if all circles were of equal radius – LLlAMnYP – 2016-07-01T19:10:45.097
3
This problem is asking for a power diagram of the circles.
– Anders Kaseorg – 2016-07-01T23:26:18.467Is it possible that the three line segments in Fig. 2 intersect at the centroid of the polygon with the circle centers as vertices? – DavidC – 2016-07-01T23:35:47.490
@DavidC No, Neil is correct that they intersect at the radical center. – Anders Kaseorg – 2016-07-01T23:40:04.483
Anders, Ok, Now I understand. – DavidC – 2016-07-02T00:44:50.740
Is it acceptable to produce the areas in different colours, not the border lines? The lines would only be implied by a colour change – Luis Mendo – 2016-07-02T17:11:09.577