四角形による平面充填

平面充填（へいめんじゅうてん）とは充填の一種で、平面内を多角形などで隙間なく敷き詰める操作である。
(略)
全ての合同な平行六辺形（3組の対辺が平行で等しい六角形）は平面敷き詰め可能である。また、平行四辺形以外の全ての四角形は、合同なものを二つ組み合わせることで平行六辺形となる。従って、全ての四角形は平面敷き詰め可能である。

平面充填 -- Wikipedia

というのをプログラムで作ってみた。

ソース

import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.geom.AffineTransform;
import java.util.Random;

import javax.swing.JComponent;
import javax.swing.JFrame;

public class Tessellation extends JComponent {
    // 基本となる四角形
    private Polygon shape;
    // 基本となる四角形を塗る色
    private Color mainColor;
    // 180度回転させた四角形を塗る色
    private Color subColor;
    // 境界線を描く色
    private Color lineColor;
    // 境界線のストローク
    private BasicStroke stroke;

    /**
     * メイン
     * @param args
     */
    public static void main(String[] args) {

        java.awt.EventQueue.invokeLater(new Runnable() {
            public void run() {
                JFrame f = new JFrame("平面充填");
                f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                f.getContentPane().add(new Tessellation());
                f.setSize(400, 300);
                // f.pack();
                f.setLocationRelativeTo(null);
                f.setVisible(true);
            }
        });
    }

    /** コンストラクタ */
    public Tessellation() {
        this.addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                // マウスクリックで図と色を変化
                reflesh();
                Tessellation.this.repaint();
            }
        });
        stroke = new BasicStroke(2.0f);
        reflesh();
    }

    /**
     * 新しい四角形を作る。
     * @return 四角形のPolygonオブジェクト
     */
    private Polygon createShape() {

        int size = 150;
        Random rand = new Random();
        int[] xIdx = new int[4];
        int[] yIdx = new int[4];
        double d = 0.5 * Math.PI * rand.nextDouble();
        double d1 = Math.PI * rand.nextDouble();
        double d2 = Math.PI - d1;
        for (int i = 0; i < 4; i++) {
            final double r = rand.nextDouble();
            xIdx[i] = (int) (Math.cos(d) * (5 + size * r));
            yIdx[i] = (int) (Math.sin(d) * (5 + size * r));

            d += (i % 2 == 0) ? d1 : d2;
        }

        return new Polygon(xIdx, yIdx, 4);
    }

    /** 平面充填の描画処理 */
    @Override
    protected void paintComponent(Graphics _g) {
        Graphics2D g = (Graphics2D) _g;
        g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);

        int w = getWidth();
        int h = getHeight();
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, w, h);
        g.translate(w / 2, h / 2);

        fillRepeate(g, shape);
    }

    /**
     * 図形を敷き詰める。
     * @param g
     * @param s
     */
    private void fillRepeate(Graphics2D g, Polygon s) {
        g.setStroke(stroke);

        int xd0 = s.xpoints[0] - s.xpoints[2];
        int yd0 = s.ypoints[0] - s.ypoints[2];
        int xd1 = s.xpoints[1] - s.xpoints[3];
        int yd1 = s.ypoints[1] - s.ypoints[3];

        // 180度回転
        Shape rev = AffineTransform.getQuadrantRotateInstance(2)
                .createTransformedShape(s);
        // 対応する辺が隣り合う位置へ平行移動
        rev = AffineTransform.getTranslateInstance(s.xpoints[0] + s.xpoints[1],
                s.ypoints[0] + s.ypoints[1]).createTransformedShape(rev);

        int ni = 1 + repeatCount(getWidth(), getHeight(), xd0, yd0) / 2;
        int nj = 1 + repeatCount(getWidth(), getHeight(), xd1, yd1) / 2;
        for (int i = -ni; i <= ni; i++) {
            for (int j = -nj; j <= nj; j++) {
                Shape ss = AffineTransform.getTranslateInstance(
                        xd0 * i + xd1 * j, yd0 * i + yd1 * j)
                        .createTransformedShape(s);
                Shape revSS = AffineTransform.getTranslateInstance(
                        xd0 * i + xd1 * j, yd0 * i + yd1 * j)
                        .createTransformedShape(rev);
                g.setColor(mainColor);
                g.fill(ss);
                g.setColor(subColor);
                g.fill(revSS);
                g.setColor(lineColor);
                g.draw(ss);
            }
        }
    }

    /**
     * 繰り返し回数を求める（適当に）
     */
    private int repeatCount(int w, int h, int xd, int yd) {
        return xd == 0 ? h / Math.abs(yd) : yd == 0 ? w / Math.abs(xd) : Math
                .max(w / Math.abs(xd), h / Math.abs(yd));
    }

    /**
     * 四角形と色をランダム再生成する。
     */
    private void reflesh() {
        shape = createShape();

        mainColor = new Color(Color.HSBtoRGB((float) Math.random(), 1.0f, 1.0f));
        subColor = new Color(Color.HSBtoRGB((float) Math.random(), 0.7f, 1.0f));
        lineColor = new Color(Color.HSBtoRGB((float) Math.random(),
                (float) Math.random(), (float) Math.random()));
    }
}

今、わからないこと

• ウィンドウの任意の場所をクリックして、その座標が並べた何番目の四角形に含まれるかの求め方。（総当り的じゃない方法で）