circleProgressiveLayout() produces layouts with overlapping circles.

[JeffreyBLewis]

I have noticed that circleProgressiveLayout() does not ensure circles are not overlapping as the
following example demonstrates:

library(packcircles)
library(ggplot2)
areas <- c(656, 1, 41, 240, 366, 62, 259, 94, 315, 310, 140, 154, 83,
202, 211, 145, 83, 92, 284, 22, 105, 61, 17, 10, 85)
packing <- circleProgressiveLayout(areas)
dat.gg <- circleLayoutVertices(packing, npoints=50)
ggplot(data = dat.gg) + geom_polygon(aes(x, y, group = id), colour = "black",
fill = "grey90", alpha = 0.7, show.legend = FALSE) +
geom_text(data = packing, aes(x, y), label = 1:nrow(packing)) +
coord_equal() + theme_void()

Here is the result:

It is pretty clear what is happening, but I am not sure why. It is not a problem in @mbedward's port to R as the same layout is produced using @pmenzel's packCircles.

[mbedward]

Thank you for spotting this and for checking against @pmenzel's reference code. I haven't seen this behaviour and it hasn't been reported previously. I wonder what it is about the test data that provoke the bug? I'll look at it next week when I'm back at work.

(sorry - closed issue by mistake)

[JeffreyBLewis]

Thank you. The example is not particular. I am writing some code to choose the (almost) most efficient packing of a set of circles inside a larger circle as part of a project to make @mbostock -like nested packed circle plots of hierarchical data. I was drawing random sets of 50 areas from an exponential distribution for testing when I found this unexpected behavior. With overlapping circles, the packing efficiency can exceed 100 percent and my not-so-clever simulated annealing optimizer can find an ordering of the areas that produces greater than 100 percent efficiency in many of the simulated exponentially distributed area data sets.

[pmenzel]

Hi,

interesting find. It looks like the first three circles are alright and it goes down hill from the fourth.

Was it only that particular example or you found many more problems like this?

Did you check if the problem also occurs in the Circle Packing code in https://github.com/d3/d3 ?
Cause my code is based on the implementation in protovis library, which is the predecessor of D3..

[pmenzel]

I think, I found the reason: when the 4th circle is placed, one placement puts it right within the first circle and the function that checks for circle overlap does not detect that full containment. Will thiink about a fix..

[mbostock]

There have been substantial improvements and bug fixes to the implementation of circle packing in d3-hierarchy (both 1.0 and subsequent releases). If you are basing your code off my implementation I would recommend looking at the latest code in d3-hierarchy. See release notes and related issue threads:

https://github.com/d3/d3-hierarchy/releases

[JeffreyBLewis]

In Mike Bostock's d3, the areas given above do not generate overlaps:

(Note that in @mbostock's d3 examples the data are presorted from largest to smallest and so when exploring the order of placement in those examples that sort must be removed. Also. note that I had to change the 2nd circle to have area=2 rather than 1 to get it displayed (not sure why), but having the second area equal 2 creates overlaps in packCircles).

[JeffreyBLewis]

It appears that @mbostock addressed this problem in d3 about a year ago. The issue thread
d3/d3-hierarchy#74 works through the problem and the solution.

[mbedward]

Many thanks for the detective work Jeffrey. It looks like it should be straightforward to fix the R package following the changes for d3:

d3/d3-hierarchy@102024d

I won't get to it until next week. If you are in a hurry please submit a PR and I'll try to look at it sooner.

[JeffreyBLewis]

Michale, Thanks much.

…

On Tue, Jan 2, 2018 at 9:35 PM, Michael Bedward ***@***.***> wrote: Many thanks for the detective work Jeffrey. It looks like it should be straightforward to fix the R package following the changes for d3: ***@***.*** <d3/d3-hierarchy@102024d> I won't get to it until next week. If you are in a hurry please submit a PR and I'll try to look at it sooner. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEinZRqdxVMcykVWupQyk4fHdtnioQcJks5tGxG3gaJpZM4RQMUs> .

-- Jeffrey B. Lewis Professor, Department of Political Science Director, Center for American Politics and Public Policy University of California, Los Angeles BOX 951472, 4289A Bunche Hall Los Angeles, CA 90095-1472

[pmenzel]

Hi Michael and Jeffrey,

I changed the code in packCircles and hopefully fixed the issue.

Peter

[mbedward]

I just committed a fix based on Peter's code changes. circleProgressiveLayout now works correctly with Jeffrey's test data. If you have time, please install the fixed version (0.3.1) with devtools::install_github and let me know if there are any remaining problems. If all is well I'll submit the update to CRAN this week. Thanks everyone.

[JeffreyBLewis]

I can confirm that the new version does not the produce overlapping circles under the test conditions that had previously produced overlaps. Michael thank you for your quick attention. Much appreciated.

…

On Mon, Jan 8, 2018 at 4:39 PM, Michael Bedward ***@***.***> wrote: I just committed a fix based on Peter's code changes. circleProgressiveLayout now works correctly with Jeffrey's test data. If you have time, please install the fixed version (0.3.1) with devtools::install_github and let me know if there are any remaining problems. If all is well I'll submit the update to CRAN this week. Thanks everyone. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEinZSwe01SN-zFGziv3OpYH6CfeG1dVks5tIrVUgaJpZM4RQMUs> .

-- Jeffrey B. Lewis Professor, Department of Political Science Director, Center for American Politics and Public Policy University of California, Los Angeles BOX 951472, 4289A Bunche Hall Los Angeles, CA 90095-1472

[mbedward]

Great to hear - thanks very much for testing it Jeffrey. I'll close this now and submit the update to CRAN today.