How to Transform Each Side of a Shape Separately

How to transform each side of a shape separately in Java?

I've created a complete algorithm. It's fairly long. The Quadrilateral.java file is included below. The last method, paint(Graphics, BufferedImage) modifies the image and paints it onto the graphics with its own shape:

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.Polygon;
import java.awt.image.BufferedImage;
import java.util.ArrayList;

public final class Quadrilateral extends Polygon {
    private static final long serialVersionUID = 794866732073166739L;
    public final Point p1, p2, p3, p4;
    public final Line l12, l23, l34, l41;

    public Quadrilateral(Point p1, Point p2, Point p3, Point p4) {
        super(new int[] { p1.x, p2.x, p3.x, p4.x }, new int[] { p1.y, p2.y,
                p3.y, p4.y }, 4);
        this.p1 = p1;
        this.p2 = p2;
        this.p3 = p3;
        this.p4 = p4;
        this.l12 = Quadrilateral.getLine(p1, p2);
        this.l23 = Quadrilateral.getLine(p2, p3);
        this.l34 = Quadrilateral.getLine(p3, p4);
        this.l41 = Quadrilateral.getLine(p4, p1);
    }

    public static Quadrilateral formatted(Quadrilateral quadrilateral, int w,
            int h) {
        return new Quadrilateral(Format.format(quadrilateral.p1, w, h),
                Format.format(quadrilateral.p2, w, h), Format.format(
                        quadrilateral.p3, w, h), Format.format(
                        quadrilateral.p4, w, h));
    }

    public Quadrilateral[][] grid(int x, int y) {
        Point[][] points = new Point[x + 1][y + 1];
        for (int ix = 0; ix <= x; ix++) {
            for (int iy = 0; iy <= y; iy++) {
                points[ix][iy] = this.getPointAt(x, y, ix, iy);
            }
        }
        Quadrilateral[][] qs = new Quadrilateral[x][y];
        for (int ix = 0; ix < x; ix++) {
            for (int iy = 0; iy < y; iy++) {
                qs[ix][iy] = new Quadrilateral(points[ix][iy],
                        points[ix + 1][iy], points[ix + 1][iy + 1],
                        points[ix][iy + 1]);
            }
        }
        return qs;
    }

    public ArrayList<ArrayList<Quadrilateral>> gridList(int x, int y) {
        Point[][] points = new Point[x + 1][y + 1];
        for (int ix = 0; ix <= x; ix++) {
            for (int iy = 0; iy <= y; iy++) {
                points[ix][iy] = this.getPointAt(x, y, ix, iy);
            }
        }
        ArrayList<ArrayList<Quadrilateral>> qs = new ArrayList<>(0);
        for (int ix = 0; ix < x; ix++) {
            qs.add(new ArrayList<>(y));
            for (int iy = 0; iy < y; iy++) {
                qs.get(ix).add(
                        new Quadrilateral(points[ix][iy], points[ix + 1][iy],
                                points[ix + 1][iy + 1], points[ix][iy + 1]));
            }
        }
        return qs;
    }

    public Point getPointAt(int xdiv, int ydiv, int xiter, int yiter) {
        Point n1 = this.getTopPointAt(xdiv, xiter);
        Point n2 = this.getRightPointAt(ydiv, yiter);
        Point n3 = this.getBottomPointAt(xdiv, xiter);
        Point n4 = this.getLeftPointAt(ydiv, yiter);
        Line h = Quadrilateral.getLine(n4, n2);
        Line v = Quadrilateral.getLine(n1, n3);
        return h.intersect(v, n2.x, n1.x);
    }

    public Point getTopPointAt(int div, int iter) {
        Point start = this.p1;
        Point end = this.p2;
        int xdiff = end.x - start.x;
        int ydiff = end.y - start.y;
        int xadd = (int) ((double) xdiff / (double) div) * iter;
        int yadd = (int) ((double) ydiff / (double) div) * iter;
        int x = start.x + xadd;
        int y = start.y + yadd;
        return new Point(x, y);
    }

    public Point getBottomPointAt(int div, int iter) {
        Point start = this.p4;
        Point end = this.p3;
        int xdiff = end.x - start.x;
        int ydiff = end.y - start.y;
        int xadd = (int) ((double) xdiff / (double) div) * iter;
        int yadd = (int) ((double) ydiff / (double) div) * iter;
        int x = start.x + xadd;
        int y = start.y + yadd;
        return new Point(x, y);
    }

    public Point getLeftPointAt(int div, int iter) {
        Point start = this.p4;
        Point end = this.p1;
        int xdiff = end.x - start.x;
        int ydiff = end.y - start.y;
        int xadd = (int) ((double) xdiff / (double) div) * iter;
        int yadd = (int) ((double) ydiff / (double) div) * iter;
        int x = start.x + xadd;
        int y = start.y + yadd;
        return new Point(x, y);
    }

    public Point getRightPointAt(int div, int iter) {
        Point start = this.p3;
        Point end = this.p2;
        int xdiff = end.x - start.x;
        int ydiff = end.y - start.y;
        int xadd = (int) ((double) xdiff / (double) div) * iter;
        int yadd = (int) ((double) ydiff / (double) div) * iter;
        int x = start.x + xadd;
        int y = start.y + yadd;
        return new Point(x, y);
    }

    public static final Line getLine(Point p1, Point p2) {
        if (p1.x < p2.x) {
            return Quadrilateral.getLine(p2, p1);
        } else {
            int x1 = p1.x;
            int x2 = p2.x;
            int y1 = p1.y;
            int y2 = p2.y;
            int xdiff = x2 - x1;
            int ydiff = y2 - y1;
            double m = (double) ydiff / (double) xdiff;
            double b = y1 - m * x1;
            return new Line(m, b);
        }
    }

    public void paint(Graphics g, BufferedImage image) {
        int w = image.getWidth();
        int h = image.getHeight();
        Quadrilateral[][] grid = this.grid(w, h);
        for (int x = 0; x < w; x++) {
            for (int y = 0; y < h; y++) {
                g.setColor(new Color(image.getRGB(x, y), true));
                g.fillPolygon(grid[x][y]);
            }
        }
    }
}

Skewing both top and bottom of div

With some rotation and perspective you can do it:

.box {
  margin-left: auto;
  width: 200px;
  height: 450px;
  transform-origin: right;
  transform: perspective(100px) rotateY(-10deg);
  border-radius: 40px 0 0 40px;
  overflow: hidden;
}

.box::before {
  content: "";
  position: absolute;
  top: 0;
  left: 0;
  right: 0;
  bottom: 0;
  background: url(https://picsum.photos/id/1074/400/800) center/cover;
  transform-origin:inherit;
  transform: perspective(100px) rotateY(10deg);
}

body {
  margin: 0;
  background:#eee;
}

<div class="box"></div>

Creating a trapezium in CSS and/or HTML

you could do this "by hand"
html:

<canvas id="polygon" />

javascript

var polygon = document.getElementById('polygon').getContext('2d');
polygon.fillStyle = '#f00';
polygon.beginPath();
polygon.moveTo(0, 0);
polygon.lineTo(90,50);
polygon.lineTo(70, 70);
polygon.lineTo(0, 90);
polygon.closePath();
polygon.fill();

this doesn't make shure it's convex and it has no parallel lines. You have to put in the correct coordinates.

Fiddle: http://jsfiddle.net/8t4rZ/

Separate L shape into two lines

Scanlines !

See the (updated) walkthrough here in Python, with images to visualize my journey through your data :)

Skip to the end for the "Scanlines" solution

Lines
Vectors

Scanlines

Basics

Assumptions

I assume these constraints from your sample image

You have (several) L-shapes in your image.
You can easily segment them (no overlapping shapes, no continuation of one L into another ...)
You know the exact width of line strokes in your Ls

Label your binary image

You want to know first which pixels are part of which L, which is done by "labeling" the binary image.

Compute also the bounding box of each volume, like so:

Rotating your coordinate system

The real trick now is changing from the x/y orthogonal system into a "L-Shaped referential" for each shape.

Think of it as redefining the X axis as one branch of the L, and the Y axis as the other branch.
Once we compute the transformation vectors of one into the other, we're safe !

Let's consider the PCA way

The problem we now face ("estimate the biggest axis of variations in dataset") is a moment where eigenvectors of covariance can be used.

I won't get into it too deeply, but you can look at this intro to PCA posting to get the feel of it.

The problem is usually defined in higher dimensions ("given a 50 dimensional dataset, compute the 10-biggest axes of variation in it"), but can be stretched to your 2D point-cloud problem by considering each shape individually and stating that every pixel belonging to the L is a point in your 2D space.

It would be a waste of computing power though, because compared to the usual case of PCA, you already have constraints on your L-points location (they're on a line, not randomly scattered). The beast of linear algebra that this problem involves is overkill on this small problem

Hough Lines, to the rescue !

You just want to find the lines in your 2D image ?
Use the Hough transform for lines (also called "hough lines").
OpenCV has it.

Again a nice intro : OpenCV's python tutorial on Hough Lines

I used the skeleton of your binary image (so that each line is upvoted only once), and chose manually the parameters I give to OpenCV for the algorithm.
This is the reason that the lines sometimes don't seem to match exactly the specific image, it's because of the sampling rate and such =)

A New Hope

After you pointed out the need for computational speed, I thought of some more techniques using properties of your image to your advantage.

RANSAC

I thought of using a RANSAC variant over your data : after all, you want to fit lines into your point cloud.
The basic technique is as you probably know summed up with

(randomly) pick enough data to fit a model (line in your case)
evaluate the number of outliers (data points for which the model doesn't work)
reiterate and keep a tally of the highest-scoring model (and keep doing that a certain number of time, involving math)

A great intro to RANSAC is this song (oddly enough)

But I see complications :

Which Model? : do you use 4 points to define 2 lines, or do you do 2 points for a line and do it twice ?
No outliers : You don't really have proper outliers, so why use RANSAC over such a trivial problem ?
Computing power : You would really iterate potentially thousands of times for no reason because you're looking randomly through your points.

Needless to say, RANSAC can't just do the trick, but we can use it as inspiration

Scanlines !

Let's consider your Ls' bounding boxes.

If we slice it horizontally at Y=0, we will have a 1D array with a contiguous area defined to True

So what if we slice through the image like this at intervals to define the L's vectors ?

Setting a 5 percentile as baseline, we just find "which X-index is the center of the 1D array of Y=0 values", then do the same of Y = 0.05 * img_width.

We now have 2 2D points defining the first line through your image.

Repeat on the other side and you have your solution !

Computationally, you are simply finding 4 medians in img_width length arrays,
each of which is a contiguous chunk of memory from your image (Heeeeelllo L2-cache hits !).

Again, if it's a bit hard to imagine just now, see the end part of my code walkthrough

How to Transform Each Side of a Shape Separately