Divide Polygon Shape Java

Question

I have a simple 2D polygon with 4 points.

    int[] x = {38, 100, 80, 18};
    int[] y = {50, 50, 100, 100};
    
    Polygon poly = new Polygon(x, y, 4);

The above polygon is just an example. The polygon above could really be anything as long as the polygon is always convex, always has 4 points, and is a parallelogram. I need to split it into any number of even parts, all proportional to the bigger polygon, as long as the number is a square number. Is there any simple way I can do this? I am using Graphics on a Jframe if that's important at all.

Answer 1

The code below works for any convex 4-sided polygon. When the initial polygon is a parallelogram, the resultant sub-polygons are by nature all parallelograms too, all with the same size, i.e. they are even-sized.

Since the desired number of parts must be a square number, it means we can simply split the 4-sided polygon horizontally and vertically into partsPerSide = sqrt(parts).

When we split a 4-sided polygon into multiple parts, we may end up with coordinates that are not exact integers. We can simply round the value to an integer, but then the pieces wouldn't be exactly even in size. Whether that is acceptable is a matter of choice. Visually, the rounding can be noticed, since the lines won't be 100% straight.

In the code below, we assume that rounding is not acceptable, i.e. we want exact even sizes. If rounding is ok, simply comment out the if (rounded != delta) throw new ArithmeticException() code at the end, then call splitFourSided() with the desired number of partsPerSide.

Enough talk, here is the code:

private static Polygon[][] splitFourSided(Polygon poly, int partsPerSide) {
    if (poly.npoints != 4)
        throw new IllegalArgumentException("Polygon must be 4-sided");
    if (partsPerSide <= 0)
        throw new IllegalArgumentException("There must be a positive number of parts per side");
    int[][] x = splitFourSided(poly.xpoints, partsPerSide);
    int[][] y = splitFourSided(poly.ypoints, partsPerSide);
    Polygon[][] pieces = new Polygon[partsPerSide][partsPerSide];
    for (int row = 0; row < partsPerSide; row++) {
        for (int col = 0; col < partsPerSide; col++) {
            pieces[row][col] = new Polygon(
                    new int[] { x[row][col], x[row][col+1], x[row+1][col+1], x[row+1][col] },
                    new int[] { y[row][col], y[row][col+1], y[row+1][col+1], y[row+1][col] },
                    4);
        }
    }
    return pieces;
}

private static int[][] splitFourSided(int[] xy, int parts) {
    // To visualize, assume values are [topLeft, topRight, bottomRight, bottomLeft].
    // The 'xy' array is either the x-coordinates or the y-coordinates.
    // First we split left and right sides, e.g. for 3 parts:
    //   From: ┌     To: ┐
    //         ├         ┤
    //         ├         ┤
    //         └         ┘
    // Then we split between those:
    //   ┌─┬─┬─┐
    //   ├─┼─┼─┤
    //   ├─┼─┼─┤
    //   └─┴─┴─┘
    int[] from = splitRange(xy[0], xy[3], parts);
    int[] to = splitRange(xy[1], xy[2], parts);
    int[][] grid = new int[parts + 1][];
    for (int i = 0; i <= parts; i++)
        grid[i] = splitRange(from[i], to[i], parts);
    return grid;
}

private static int[] splitRange(int from, int to, int parts) {
    int[] prorated = new int[parts + 1];
    for (int i = 0; i <= parts; i++)
        prorated[i] = prorate(from, to, i, parts);
    return prorated;
}

private static int prorate(int from, int to, int index, int parts) {
    if (index == 0)
        return from;
    if (index == parts)
        return to;
    double delta = (to - (double) from) * index / parts;
    int rounded = (int) Math.round(delta);
    if (rounded != delta)
        throw new ArithmeticException("Cannot prorate to integer value");
    return from + rounded;
}

Test

int[] x = {38, 100, 80, 18};
int[] y = {50, 50, 100, 100};
Polygon poly = new Polygon(x, y, 4);
splitAndDrawFourSided(g, poly, 2);

private static void splitAndDrawFourSided(Graphics g, Polygon poly, int partsPerSide) {
    Polygon[][] pieces = splitFourSided(poly, partsPerSide);
    for (int row = 0; row < partsPerSide; row++)
        for (int col = 0; col < partsPerSide; col++)
            g.drawPolygon(pieces[row][col]);
    Graphics gMain = g.create();
    try {
        gMain.setColor(Color.RED);
        gMain.drawPolygon(poly);
    } finally {
        gMain.dispose();
    }
}

Result

---

To search for a valid number of parts, we can add a search loop, and change the coordinates so they are only divisible by 7.

int[] x = {37, 100, 79, 16};
int[] y = {50, 50, 99, 99};
Polygon poly = new Polygon(x, y, 4);
for (int partsPerSide : new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }) {
    try {
        splitAndDrawFourSided(g, poly, partsPerSide);
        break; // stop when successful
    } catch (@SuppressWarnings("unused") ArithmeticException ignored) {
        continue; // try next number of parts
    }
}

Result

---

If we remove the rounding check, that code will of course always just split by 2 parts per side, i.e. into 4 parts. This shows the effect of rounding, e.g. in this case the center row coordinates ended up a bit to the right, causing the black and red lines to not match up. Even without the red line depicting the input parallelogram, the rounding can be noticed. Anti-aliasing helps, but it can still be noticed that the vertical lines aren't 100% straight.