CODEWITHSUNDEEP
algorithmhtml5-canvasgeometrycomputational-geometry
Smarth Behl
Smarth Behl

Reputation: 123

Drawing Geometrical and Mathematical Algorithm

I have a certain requirement which becomes an interesting Mathematical problem.

Given a number n and fixed distance d and Point p(x,y) inside rectangle R of fixed width and height (which is screen). I want to draw n squares inside rectangle with maximum size possible (all squares same size) and squares not intersect each other and are separate from each other by minimum distance d (Distance from perimeter of square).

These squares should also be at least at distance d from a given point P (which is basically mouse's last recorded position).

Please let me know if there is a solution to this.

Solution should give size of square and coordinates for all squares.

The reverse interesting problem could be given size of square how many such squares can be drawn.

Upvotes: 0

Views: 143

Answers (2)

kuroi neko
kuroi neko

Reputation: 8641

You've asked for it, you've got it

I've got a fiddle here that probably does a near-optimal tiling.
It's godawful ugly, though.

It reminds me of some customers of mine insisting on dabbling in detailed specifications instead of remaining at functional requirement level :).

The heart of the algorithm is here:

compute: function ()
{
    function try_size (x1, x2, y1, y2, w, h, y)
    {
        var d = Math.sqrt((this.w+this.h)/this.n);
        var delta = 10*d;
        var n = 0;
        while ((delta > 1e-12) || (n < this.n))
        {
            var res = {};
            if (y < (d/2-this.d))
            {
                res.x1 = res.x2 = res.y1 = 0;
                res.y2 = Math.floor ((h-y-this.d)/d);
                res.c1 = true;
            }
            else if (y > (h-d+2*this.d))
            {
                res.x1 = res.x2 = res.y2 = 0;
                res.y1 = Math.floor ((y-this.d)/d);
                res.c2 = true;
            }
            else
            {
                res.y1 = Math.floor((y1-d/2)/d);
                res.y2 = Math.floor((y2-d/2)/d);
                res.x1 = Math.floor ((x1-this.d/2)/d);
                res.x2 = Math.floor ((x2-this.d/2)/d);
            }
            res.w = Math.floor ((w+this.d)/d);
            n = res.x1+res.x2+res.w*(res.y1+res.y2);
              
            d += n > this.n ? delta : -delta;
            if (delta > 1e-12) delta /=2;
        }
        res.d = d;
        res.s = d-2*this.d;
        return res;
    }

The idea is to tile the rectangle regularily, except for the band around the center point. Horizontal and vertical variants of this band are tried to retain the highest square size.

I guess an optimal solution would not center the band around the center point, but given the awful looks of the result, I don't think it's worth the effort :)

A better-looking but less optimal solution:

(just a proof of concept; some edge cases are handled wrongly).

    compute: function ()
    {
        var d = Math.sqrt((this.w+this.h)/this.n);
        var delta = 100*d;
        while ((delta > 1e-12) || (res.n < this.n))
        {
            var res = {};
            res.x = Math.floor ((this.w-this.x%d)/d);
            res.y = Math.floor ((this.h-this.y%d)/d);
            res.n = res.x * res.y;
              
            d += res.n > this.n ? delta : -delta;
            if (delta > 1e-12) delta /=2;
        }
        res.d = d;
        res.s = d-2*this.d;
        res.a = 0;
        this.res = res;
    },

Moving the reference point still causes the square size to wobble.
Might be fun as a graphic effect, though.

Upvotes: 0

MBo
MBo

Reputation: 80187

Simple (probably not optimal) approach: with binary search find maximal value of a that

Floor((Width + d) / a) * Floor((Height + d) / a) >= n+1

and make regular grid of n squares with edge (a - d), excluding place with point

Upvotes: 1

Related Questions