Java 8 + Swing: How to Draw Flush Polygons

Question

(Sorry for the long post... at least it has pictures?)

I have written an algorithm that creates a mosaic from an image by statistically generating N convex polygons that cover the image with no overlap. These polygons have anywhere between 3-8 sides, and each side has an angle that is a multiple of 45 degrees. These polygons are stored internally as a rectangle with displacements for each corner. Below is an image that explains how this works:

getRight() returns x + width - 1, and getBottom() returns y + height - 1. The class is designed to maintain a tight bounding box around filled pixels so the coordinates shown in this image are correct. Note that width >= ul + ur + 1, width >= ll + lr + 1, height >= ul + ll + 1, and height >= ur + ul + 1, or there would be empty pixels on a side. Note also that it is possible for a corner's displacement to be 0, thus indicating all pixels are filled in that corner. This enables this representation to store 3-8 sided convex polygons, each of whose sides are at least one pixel in length.

While it's nice to mathematically represent these regions, I want to draw them so I can see them. Using a simple lambda and a method that iterates over each pixel in the polygon, I can render the image perfectly. As an example, below is Claude Monet's Woman with a Parasol using 99 polygons allowing all split directions.

The code that renders this image looks like this:

public void drawOnto(Graphics graphics) {
    graphics.setColor(getColor());
    forEach(
        (i, j) -> {
            graphics.fillRect(x + i, y + j, 1, 1);
        }
    );
}

private void forEach(PerPixel algorithm) {
    for (int j = 0; j < height; ++j) {
        int nj = height - 1 - j;

        int minX;
        if (j < ul) {
            minX = ul - j;
        } else if (nj < ll) {
            minX = ll - nj;
        } else {
            minX = 0;
        }

        int maxX = width;
        if (j < ur) {
            maxX -= ur - j;
        } else if (nj < lr) {
            maxX -= lr - nj;
        }

        for (int i = minX; i < maxX; ++i) {
            algorithm.perform(i, j);
        }
    }
}

However, this is not ideal for many reasons. First, the concept of graphically representing a polygon is now part of the class itself; it is better to allow other classes whose focus is to represent these polygons. Second, this entails many, many calls to fillRect() to draw a single pixel. Finally, I want to be able to develop other methods of rendering these polygons than drawing them as-is (for example, performing weighted interpolation over the Voronoi tessellation represented by the polygons' centers).

All of these point to generating a java.awt.Polygon that represents the vertices of the polygon (which I named Region to differentiate from the Polygon class). No problem; I wrote a method to generate a Polygon that has the corners above with no duplicates to handle the cases that a displacement is 0 or that a side has only one pixel on it:

public Polygon getPolygon() {
    int[] xes = {
        x + ul,
        getRight() - ur,
        getRight(),
        getRight(),
        getRight() - lr,
        x + ll,
        x,
        x
    };
    int[] yes = {
        y,
        y,
        y + ur,
        getBottom() - lr,
        getBottom(),
        getBottom(),
        getBottom() - ll,
        y + ul
    };

    int[] keptXes = new int[8];
    int[] keptYes = new int[8];
    int length = 0;
    for (int i = 0; i < 8; ++i) {
        if (
            length == 0 ||
            keptXes[length - 1] != xes[i] ||
            keptYes[length - 1] != yes[i]
        ) {
            keptXes[length] = xes[i];
            keptYes[length] = yes[i];
            length++;
        }
    }

    return new Polygon(keptXes, keptYes, length);
}

The problem is that, when I try to use such a Polygon with the Graphics.fillPolygon() method, it does not fill all of the pixels! Below is the same mosaic rendered with this different method:

So I have a few related questions about this behavior:

1. Why does the Polygon class not fill in all these pixels, even though the angles are simple multiples of 45 degrees?

2. How can I consistently code around this defect (as far as my application is concerned) in my renderers so that I can use my getPolygon() method as-is? I do not want to change the vertices it outputs because I need them to be precise for center-of-mass calculations.

---

MCE

If the above code snippets and pictures are not enough to help explain the problem, I have added a Minimal, Complete, and Verifiable Example that demonstrates the behavior I described above.

package com.sadakatsu.mce;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Polygon;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

public class Main {
    @FunctionalInterface
    private static interface PerPixel {
        void perform(int x, int y);
    }

    private static class Region {
        private int height;
        private int ll;
        private int lr;
        private int width;
        private int ul;
        private int ur;
        private int x;
        private int y;

        public Region(
            int x,
            int y,
            int width,
            int height,
            int ul,
            int ur,
            int ll,
            int lr
        ) {
            if (
                width < 0 || width <= ll + lr || width <= ul + ur ||
                height < 0 || height <= ul + ll || height <= ur + lr ||
                ul < 0 ||
                ur < 0 ||
                ll < 0 ||
                lr < 0
            ) {
                throw new IllegalArgumentException();
            }

            this.height = height;
            this.ll = ll;
            this.lr = lr;
            this.width = width;
            this.ul = ul;
            this.ur = ur;
            this.x = x;
            this.y = y;
        }

        public Color getColor() {
            return Color.BLACK;
        }

        public int getBottom() {
            return y + height - 1;
        }

        public int getRight() {
            return x + width - 1;
        }

        public Polygon getPolygon() {
            int[] xes = {
                x + ul,
                getRight() - ur,
                getRight(),
                getRight(),
                getRight() - lr,
                x + ll,
                x,
                x
            };
            int[] yes = {
                y,
                y,
                y + ur,
                getBottom() - lr,
                getBottom(),
                getBottom(),
                getBottom() - ll,
                y + ul
            };

            int[] keptXes = new int[8];
            int[] keptYes = new int[8];
            int length = 0;
            for (int i = 0; i < 8; ++i) {
                if (
                    length == 0 ||
                    keptXes[length - 1] != xes[i] ||
                    keptYes[length - 1] != yes[i]
                ) {
                    keptXes[length] = xes[i];
                    keptYes[length] = yes[i];
                    length++;
                }
            }

            return new Polygon(keptXes, keptYes, length);
        }

        public void drawOnto(Graphics graphics) {
            graphics.setColor(getColor());
            forEach(
                (i, j) -> {
                    graphics.fillRect(x + i, y + j, 1, 1);
                }
            );
        }

        private void forEach(PerPixel algorithm) {
            for (int j = 0; j < height; ++j) {
                int nj = height - 1 - j;

                int minX;
                if (j < ul) {
                    minX = ul - j;
                } else if (nj < ll) {
                    minX = ll - nj;
                } else {
                    minX = 0;
                }

                int maxX = width;
                if (j < ur) {
                    maxX -= ur - j;
                } else if (nj < lr) {
                    maxX -= lr - nj;
                }

                for (int i = minX; i < maxX; ++i) {
                    algorithm.perform(i, j);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        int width = 10;
        int height = 8;

        Region region = new Region(0, 0, 10, 8, 2, 3, 4, 1);

        BufferedImage image = new BufferedImage(
            width,
            height,
            BufferedImage.TYPE_3BYTE_BGR
        );
        Graphics graphics = image.getGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fillRect(0, 0, width, height);
        region.drawOnto(graphics);
        ImageIO.write(image, "PNG", new File("expected.png"));

        image = new BufferedImage(
            width,
            height,
            BufferedImage.TYPE_3BYTE_BGR
        );
        graphics = image.getGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fillRect(0, 0, width, height);
        graphics.setColor(Color.BLACK);
        graphics.fillPolygon(region.getPolygon());
        ImageIO.write(image, "PNG", new File("got.png"));
    }
}

Answer 1

I spent all day working on it, and I seem to have a fix for this. The clue was found in the documentation for the Shape class, which reads:

Definition of insideness: A point is considered to lie inside a Shape if and only if:

• it lies completely inside theShape boundary or

• it lies exactly on the Shape boundary and the space immediately adjacent to the point in the increasing X direction is entirely inside the boundary or

• it lies exactly on a horizontal boundary segment and the space immediately adjacent to the point in the increasing Y direction is inside the boundary.

Actually, this text is a bit misleading; the third case overrides second (i.e., even if a pixel in a horizontal boundary segment on the bottom of a Shape has a filled point to its right, it still will not be filled). Represented pictorially, the Polygon below will not draw the x'ed out pixels:

The red, green, and blue pixels are part of the Polygon; the rest are not. The blue pixels fall under the first case, the green pixels fall under the second case, and the red pixels fall under the third case. Note that all of the rightmost and lowest pixels along the convex hull are NOT drawn. To get them to be drawn, you have to move the vertices to the orange pixels as shown to make a new rightmost/bottom-most portion of the convex hull.

The easiest way to do this is to use camickr's method: use both fillPolygon() and drawPolygon(). At least in the case of my 45-degree-multiple-edged convex hulls, drawPolygon() draws the lines to the vertices exactly (and probably for other cases as well), and thus will fill the pixels that fillPolygon() misses. However, neither fillPolygon() nor drawPolygon() will draw a single-pixel Polygon, so one has to code a special case to handle that.

The actual solution I developed in trying to understand the insideness definition above was to create a different Polygon with the modified corners as shown in the picture. It has the benefit (?) of calling the drawing library only once and automatically handles the special case. It probably is not actually optimal, but here is the code I used for anyone's consideration:

package com.sadakatsu.mosaic.renderer;

import java.awt.Polygon;
import java.util.Arrays;

import com.sadakatsu.mosaic.Region;

public class RegionPolygon extends Polygon {
    public RegionPolygon(Region region) {
        int bottom = region.getBottom();
        int ll = region.getLL();
        int lr = region.getLR();
        int right = region.getRight();
        int ul = region.getUL();
        int ur = region.getUR();
        int x = region.getX();
        int y = region.getY();

        int[] xes = {
            x + ul,
            right - ur + 1,
            right + 1,
            right + 1,
            right - lr,
            x + ll + 1,
            x,
            x
        };

        int[] yes = {
            y,
            y,
            y + ur,
            bottom - lr,
            bottom + 1,
            bottom + 1,
            bottom - ll,
            y + ul
        };

        npoints = 0;
        xpoints = new int[xes.length];
        ypoints = new int[xes.length];
        for (int i = 0; i < xes.length; ++i) {
            if (
                i == 0 ||
                xpoints[npoints - 1] != xes[i] ||
                ypoints[npoints - 1] != yes[i]
            ) {
                addPoint(xes[i], yes[i]);
            }
        }
    }
}