6
\$\begingroup\$

Here is my problem statement:

There is a matrix of octagons, for example, 4 octagons in a row and 3 such rows. So 4 columns and 3 rows of octagons. But they are not arranged in a perfect rectangle form.

Case1:

Matrix of Octagons

The first Octagon, O(0,0) has coordinates(0,0), while the one at its right and the one at bottom are at a bit offset. So O(0,1) has coordinates (15,50) and O(1,0) has coordinates (30,15). This information is enough to define the whole array of octagons. Now next requirement is to find how much is the net visible area of these octagons. In the first example, as the coordinates are far away, there would be no overlapping and total visible area is simply...

Total_Visible_Area = Area_of_Single_Octagon * No_Of_Rows * No_Of_Columns

But when the coordinates are bit complex, for example, Case 2: enter image description here Here, the the distance between the adjacent octagons is less than their width and hence they are overlapping. Coordinates also are negative (which does not matter much actually, just something to note). Now to determine visible area for this I wrote the following function.

//Inputs of the function:
//S = Side of the octagon/2, 5*Accuracy_Factor for both of the case
//G = Total Width of the octagon/2, 5*2.41*Accuracy_Factor for both of the case
//NSX = X distance of the octagon O(1,0), 8.09*Accuracy_Factor in Case 2
//NSY = Y distance of the octagon O(1,0), -20.98*Accuracy_Factor in Case 2
//EWX = X distance of the octagon O(0,1), 17.37*Accuracy_Factor in Case 2
//EWY = Y distance of the octagon O(0,1), 12*Accuracy_Factor in Case 2
//NSCount = Total no of rows, 4 in this example
//EWCount = Total no of columns, 3 in this example

//The following function initializes a big 2D array. Each pixel of the octagon is one
//element of the array. Program calculates coordinates of all octagons. Picking the 
//octagons one by one, it forms an octagon around that coordinate in the 
//2D array by allotting 1 to the array. At the end I find a total number 
//of 1s ant that's my total visible area.

double OverlapArea(double S, double G, double NSX, double NSY, double EWX, double EWY, int NSCount, int EWCount)
{
    int count = 0, i, j, x, y, ArrayColSize, ArrayRowSize, TotalArea;
    double XMax = 0, XMin = 0, YMax = 0, YMin = 0, DishX[3], DishY[3], A, B, Ai, Bi;
    std::vector<std::vector<int>> Area;

    //Next few line, until the next comment, are written to find the
    //size of the 2D array that will be required.
    DishX[0] = EWX * (EWCount - 1);
    DishX[1] = NSX * (NSCount - 1);
    DishX[2] = EWX * (EWCount - 1) + NSX * (NSCount - 1);

    DishY[0] = EWY * (EWCount - 1);
    DishY[1] = NSY * (NSCount - 1);
    DishY[2] = EWY * (EWCount - 1) + NSY * (NSCount - 1);

    for (i = 0; i < 3; i++)
    {
        if (DishX[i] < XMin)
            XMin = DishX[i];
        if (DishX[i] > XMax)
            XMax = DishX[i];
        if (DishY[i] < YMin)
            YMin = DishY[i];
        if (DishY[i] > YMax)
            YMax = DishY[i];
    }

    A = Ai = G - XMin;
    B = Bi = G - YMin;
    ArrayRowSize = (int)ceil(XMax - XMin + 2 * G);
    ArrayColSize = (int)ceil(YMax - YMin + 2 * G);

    Area.resize(ArrayRowSize+5, std::vector<int>(ArrayColSize+5, 0));
    //Array is resized in the above line, not the loop that forms the octagons
    for (i = 0; i < NSCount; i++)
    {
        for (j = 0; j < EWCount; j++)
        {
            for (x = A - G; x < A + G; x++)
            {
                for (y = B - G; y < B + G; y++)
                {
                    if ((x - y >= A - B - S - G) && (y <= B + G) && (x + y <= A + B + S + G) && (x <= A + G) && (x - y <= A + G - B + S) && (y >= B - G) && (x + y >= A + B - S - G) && (x >= A - G))
                    {
                        Area[x][y] = 1;
                    }
                }
            }
            A = Ai + EWX * (j+1);
            B = Bi + EWY * (j+1);
            count++;
        }
        A = Ai + NSX;
        B = Bi + NSY;
        Ai = A;
        Bi = B;
    }

    TotalArea = 0;

    for (i = 0; i < ArrayRowSize; i++)
    {
        for (j = 0; j < ArrayColSize; j++)
        {
            TotalArea = TotalArea + Area[i][j];
            std::cout << Area[i][j]<<',';
        }
        std::cout <<std::endl;
    }

    return (double)TotalArea;
}

Now the problem with this method:

  1. The Accuracy factor that I set in the main function determines how accurate this method is. Higher the accuracy is, more the time to calculate. It's as simple as increasing resolution.
  2. I can only use the shapes that I can define with equations (rectangle, circle, triangle octagon etc...) If it's an irregular shape, I'll have a tough time defining which pixel to count and which to not.

I'd like to know other methods I can calculate visible area. One thing I can think of is inputting the shape as an image, overlapping it, and then calculate the pixels at the end. But not sure if there is a more simple way.

Edit: The main function is going to calculate 8000+ cases, out of which approx 3000 cases will require to go through this function. The Accuracy Factor needs to be an odd multiple of 7 (7,21,35,49...Found this via experimenting. 7 has more accuracy than 20.). With Accuracy factor = 21, the program took around 1 hour for its first 2000 calculations, after which I terminated it cause I had the idea that it's working good. But this time is unacceptable.

\$\endgroup\$
2
  • \$\begingroup\$ Is your input an image? Or a bunch of shapes, i.e., equations that determine what you see? In your test all shapes are arranged on a grid, but will it actually be the case? \$\endgroup\$ Commented Oct 12, 2019 at 2:41
  • \$\begingroup\$ @ALX23z As of now, input are just parameters. Coordinates of the center & side length are enough to form the octagon in a 2D array. But for irregular shapes, this method won't work & I may not be able to formulate an equation to define the shape's boundary conditions. Hence when it comes to inputting the shape, inputting it via image is the only thing that comes to my mind. If anyone can suggest something more efficient, I'm open to it. I've no exp with images in C++. Grid will always be regular & won't have non-linear pattern. Eg: i.imgur.com/0PrHOG8.png grid with irregular shape. \$\endgroup\$ Commented Oct 12, 2019 at 3:31

1 Answer 1

Reset to default
3
\$\begingroup\$

There are two general approaches.

The first is to use image, and modify as you see fit.

Pros:

  1. Simple to use.
  2. Can be easily applied to all shapes.
  3. Reliable.
  4. There might already be a free suitable implementation you can use.

Cons:

  1. Fixed limited accuracy.
  2. You might need to implement a GPU or SIMD based code to achieve required performance.
  3. Requires too much resources for trivial cases.

Second approach: use polygons.

There is a simple formula to compute area of a polygon.

Say, you have a polygon {(x_1, y_1)...(x_n, y_n)} then its area is the sum

(x_2-x_1)*(y_1+y_2)/2 + ... + (x_1-x_n)*(y_n+y_1)/2
// technically, it equals to either area or -area depending on orientation of the polygon

The problem is that union/intersection of polygons is not, in general, a polygon - instead, it can be expressed as a union of non-intersecting polygons. But then after repeated use number of polygons might blow up depending on input... so utilizing this method requires care and attention, though in your case it might be quite simple.

It is harder to apply this method for all shapes: you ought to approximate the shape via a polygon.

Note: suitable for both approaches. Since your grid is regular, under a mild additional assumption, computation of Total Area can be to simplified to computation of area of a few pieces of it.

  1. Area in a cell of the grid. (A)
  2. 4 types of areas that lie on the sides of the grid. (B1,B2,B3,B4)
  3. Remaining corner area - 4 regions at the corners. (C = C1+C2+C3+C4, it is the area of the base shape).

See https://i.sstatic.net/IThLo.jpg for clarification. In the image I showed only two types of side areas and one corner area - there are also two types of side area on the other side of the grid.

Total Area is C + (B1+B3)*(Rows-1) + (B2+B4)*(Cols-1) + A*(Rows-1)*(Cols-1)

Though, this simplification works only if the base shape is fully contained its four neighbor cells... if it is not the case the formula becomes more complicated.

\$\endgroup\$
2
  • \$\begingroup\$ I was really convinced that I may have to get into image manipulation for better accuracy, but the section method that you pointed out is really amazing and may save me the trouble getting into images. This algorithm may save me much of calculation time. I'm thinking of defining a 3x3 grid with very high accuracy factor, get all the section areas, and just use that info to calculate area for a larger grid of, let's say 25x30 grid. I'll start working on this and see how much it is viable. Thank You very much. \$\endgroup\$ Commented Oct 12, 2019 at 4:56
  • \$\begingroup\$ @AdityaSoni Glad to help! As a side note, there are simple ways to improve accuracy for image based computation: in the image data you can store greyscale or float instead of binary, with the extra info you try to approximate how much of the pixel is filled. Usually, you don't lose performance when you switch from boolean image to greyscale - unless you use optimized boolean images. \$\endgroup\$ Commented Oct 12, 2019 at 6:12

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.