Return to Answer

improved integration and delivered a better solution

Source Link

edited Jul 10, 2021 at 17:37

As the search for a solution is numerical and not exact anyway, just as well to calculate the area of the union numerically, too. And this can be done, in R, by function integral2quad2d from package pracma, which does double integrals. Integrating the logical 'OR' of all the conditions $(x-x_i)^2+(y-y_i)^2 \le r^2$ overintersected with the domain defined byof the big lawn circle of radius R is equivalent to measuring the area of lawn 'covered' by the sprinklers. At that point it is sufficient to find the positions such that this area is as close as possible to $\pi \cdot R^2$.

To do this, I started from 23 randomlycircularly placed sprinklers, with some added small error:

After 50001947 iterations of the solver, this is what came up:

It is clearly still 'not there', butAlthough it is going in the right directionsays 100%, which makes me think that perhaps I amthe coverage is not using a good solverexactly 100%, or I would needas also shown by the picture; this is due to use better parameters for it. The documentation does mention that SA strongly depends on the parameterssmall error from quad2d.

Still,Overall I think this is an interesting approach.
Perhaps if one could introduce some constraints, it would perform even better.

Here are the coordinates:

structure(c(-0.0192124302696741, 1.69210228374458, 1.12207220007407, -0.458898282169877, -1.68459206671881, -1.70572906611192, -0.318261987390775, 1.21913074028621, 3.47057522438769, 2.88566291913126, 2.35704067670984, 0.876234839830577, -0.347322720559182, -1.7670113219972, -2.72089899862811, -3.27982525875973, -3.37521750345377, -2.78059651594498, -1.73354422501726, -0.649925560795611, 0.881358800028353, 2.4205497798494, 3.05182438644101, 0.0849395846722759, 0.0381557538473754, 1.57068493479492, 1.79759347364571, 0.936034350433627, -0.572036690983195, -1.64730572005061, -1.37720408225443, 0.291592074635348, 1.50768382825572, 3.03140145000842, 3.18999836840338, 3.65852384689267, 2.82264267884141, 2.01624557285127, 0.659227568775992, -0.590041349219451, -2.07085783149175, -2.5464904659875, -3.45043043487102, -3.10716258638463, -2.7191961236181, -1.23602359917925), .Dim = c(23L, 2L), .Dimnames = list(NULL, c("x", "y")))

As the search for a solution is numerical and not exact anyway, just as well to calculate the area of the union numerically, too. And this can be done, in R, by function integral2 from package pracma, which does double integrals. Integrating the logical 'OR' of all the conditions $(x-x_i)^2+(y-y_i)^2 \le r^2$ over the domain defined by the big lawn circle of radius R is equivalent to measuring the area of lawn 'covered' by the sprinklers. At that point it is sufficient to find the positions such that this area is as close as possible to $\pi \cdot R^2$.

To do this, I started from 23 randomly placed sprinklers:

After 5000 iterations of the solver, this is what came up:

It is clearly still 'not there', but it is going in the right direction, which makes me think that perhaps I am not using a good solver, or I would need to use better parameters for it. The documentation does mention that SA strongly depends on the parameters.

Still, I think this is an interesting approach.

As the search for a solution is numerical and not exact anyway, just as well to calculate the area of the union numerically, too. And this can be done, in R, by function quad2d from package pracma, which does double integrals. Integrating the logical 'OR' of all the conditions $(x-x_i)^2+(y-y_i)^2 \le r^2$ intersected with the domain of the big lawn circle of radius R is equivalent to measuring the area of lawn 'covered' by the sprinklers. At that point it is sufficient to find the positions such that this area is as close as possible to $\pi \cdot R^2$.

To do this, I started from 23 circularly placed sprinklers, with some added small error:

After 1947 iterations of the solver, this is what came up:

Although it says 100%, the coverage is not exactly 100%, as also shown by the picture; this is due to the small error from quad2d.

Overall I think this is an interesting approach.
Perhaps if one could introduce some constraints, it would perform even better.

Here are the coordinates:

structure(c(-0.0192124302696741, 1.69210228374458, 1.12207220007407, -0.458898282169877, -1.68459206671881, -1.70572906611192, -0.318261987390775, 1.21913074028621, 3.47057522438769, 2.88566291913126, 2.35704067670984, 0.876234839830577, -0.347322720559182, -1.7670113219972, -2.72089899862811, -3.27982525875973, -3.37521750345377, -2.78059651594498, -1.73354422501726, -0.649925560795611, 0.881358800028353, 2.4205497798494, 3.05182438644101, 0.0849395846722759, 0.0381557538473754, 1.57068493479492, 1.79759347364571, 0.936034350433627, -0.572036690983195, -1.64730572005061, -1.37720408225443, 0.291592074635348, 1.50768382825572, 3.03140145000842, 3.18999836840338, 3.65852384689267, 2.82264267884141, 2.01624557285127, 0.659227568775992, -0.590041349219451, -2.07085783149175, -2.5464904659875, -3.45043043487102, -3.10716258638463, -2.7191961236181, -1.23602359917925), .Dim = c(23L, 2L), .Dimnames = list(NULL, c("x", "y")))

Source Link

created Jul 7, 2021 at 19:49

user6376297

I was pointed to this very interesting post by RobPratt, who helped me with a related problem.

After implementing a similar solution to his, using a random scatter of points and looking for a solution by set cover binary linear programming (which works quite well indeed), I thought I'd give a try to a more 'geometry-based' solution.

[BTW, I am using hidden sections because I take it this is the idea in this particular SE site, but please feel free to advise me otherwise.]

In essence we want to find the location of the sprinklers such that the union of the areas spanned by their circles of radius 1, intersected with the big lawn circle of radius 4, is as close as possible to the full circle of radius 4.

However, calculating that exactly from the positions of the sprinklers is prohibitively complex (at least for me). There might be a way, as I hinted to in the linked post, but probably very hard to code.

Here's the intuition:

As the search for a solution is numerical and not exact anyway, just as well to calculate the area of the union numerically, too. And this can be done, in R, by function integral2 from package pracma, which does double integrals. Integrating the logical 'OR' of all the conditions $(x-x_i)^2+(y-y_i)^2 \le r^2$ over the domain defined by the big lawn circle of radius R is equivalent to measuring the area of lawn 'covered' by the sprinklers. At that point it is sufficient to find the positions such that this area is as close as possible to $\pi \cdot R^2$.

To do this, I started from 23 randomly placed sprinklers:

After 5000 iterations of the solver, this is what came up:

Still, I think this is an interesting approach.