複合長方形を長方形で分割

どうも、一ヶ月ぶりです。月に一度の更新は目指していますが、書く内容がない（もしくは、書くのが面倒すぎる）という状況だったので放置してました。いや、JavaFX2.0(beta)でiTunesとかmacとかで画像を表示するときみたいな画像ビューアを作ったのをネタにしようかなと思った日もあったけど、思った以上にしょぼか(ry



ちょうど書くのにちょうど良いぐらいの内容を行ったので、書き留めておきます。

いくつかの矩形を結合した図形を、再び重複しない矩形に分割する、という事をします。こんな物どこで必要になるんだ？図形処理をしていると必要になるんです。（コンピューター上では矩形が図形の基本単位として扱いやすいのです。）


図で示すとこうなります。右が結合する矩形、真ん中がその結果、左が分割した結果です。

今回は大附 辰夫らによる手法*1を利用しました。

手順は

1. 長方形の結合
2. 垂直線、水平線を取り出し、垂直線をx座標が小さい順に、水平線をy座標が大きい順に並び替える。
3. 論文の図6のルールに従って長方形を作っていく。

一番しんどいのは１の長方形の結合ですが、ここはJavaの資産java.awt.geom.Areaを使わせて貰いましょう。嬉しいことに、Areaを使って結合した図形は、大附 辰夫らによる手法を適用するためのパスの構成が左回りという条件をクリアしてくれていました。


Areaからパスを取り出すにはPathIteratorを取得することで可能です。PathIteratorの扱い方は私の記事のマウスをShape（PathIterator）の形にドラッグ（移動）させよう,GeneralPathとPathIteratorの諸注意を参考にしてください。



３について、詳しくは論文を読んでください。
水平線は以下の図の様な8つの状態に分けることができます。（適当に手書きで作ったので、非常に見にくいですが、気合いで見てください。）青い線が注目している水平線です。矢印は時計回りの方向を示しています。

まずは垂直線を格納するための空のリストを用意しておきます。
各水平線おける操作は以下の様になります。

1. 緑の垂直線があれば、それをリストから抜き取ります。
2. 赤斜線部があれば、その長方形を取り出します。長方形を得るのに必要な黒い垂直線は必ずリストの中にあります。その後、垂直線の長方形の一部になった部分を削除します。
3. 紫色の垂直線があれば、それをリストに追加します。

実際にソースコードに起こした結果はこうなりました。全体で370行弱。そんなに難しくないですね。

import java.awt.Rectangle;
import java.awt.geom.Area;
import java.awt.geom.PathIterator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class UnionRectangle {
	private Area area = new Area();

	public void add(Rectangle r){
		if(r.isEmpty())return;
		area.add(new Area(r));
	}

	public void add(Rectangle... r){
		for(Rectangle rect:r){
			add(rect);
		}
	}

	public Rectangle[] divide(){
		XLine[] xlines;
		YLines ylines;
		{
			ArrayList<XLine> x = new ArrayList<XLine>();
			ArrayList<YLine> y = new ArrayList<YLine>();
			toLine(x, y);
			xlines = x.toArray(new XLine[x.size()]);
			Arrays.sort(xlines);
			ylines = new YLines(y.size());
		}

		ArrayList<Rectangle> rect = new ArrayList<Rectangle>();
		for(XLine x:xlines){
			YLine joinstart=x.getJoinStart(),joinend=x.getJoinEnd();

			if(x.increase){

				if(joinstart.increase){
					if(joinend.increase){

						YLine nright = nearestYLine_fromRight(x, ylines);
						int w = nright.x-x.end;
						int h = nright.start-x.y;
						rect.add(new Rectangle(x.end,x.y,w,h));
						nright.setStart(x.y);
						ylines.add(joinstart);
						ylines.remove(joinend);
					}else{
						ylines.add(joinstart);
						ylines.add(joinend);
					}
				}else{
					if(joinend.increase){

						YLine nleft = nearestYLine_fromLeft(x, ylines);
						int w=x.start-nleft.x;
						int h = nleft.end-x.y;
						rect.add(new Rectangle(nleft.x,x.y,w,h));
						nleft.setEnd(x.y);

						YLine nright = nearestYLine_fromRight(x, ylines);
						w = nright.x-x.end;
						h = nright.start-x.y;
						rect.add(new Rectangle(x.end,x.y,w,h));
						nright.setStart(x.y);
						ylines.remove(joinstart);
						ylines.remove(joinend);


					}else{
						YLine nleft = nearestYLine_fromLeft(x, ylines);
						int w=x.start-nleft.x;
						int h = nleft.end-x.y;
						rect.add(new Rectangle(nleft.x,x.y,w,h));
						nleft.setEnd(x.y);
						ylines.remove(joinstart);
						ylines.add(joinend);
					}
				}


			}else{
				if(joinstart.increase){
					if(joinend.increase){
						YLine nright = nearestYLine_fromRight(x, ylines);
						int w = nright.x-x.end;
						int h = nright.start-x.y;
						rect.add(new Rectangle(x.end,x.y,w,h));
						nright.setStart(x.y);
						ylines.remove(joinend);
						ylines.add(joinstart);
					}else{
						YLine nright = nearestYLine_fromRight(x, ylines),nleft = nearestYLine_fromLeft(x, ylines);
						int w = nright.x-nleft.x;
						int h = nright.start-x.y;
						rect.add(new Rectangle(nleft.x,x.y,w,h));
						nright.setStart(x.y);
						nleft.setEnd(x.y);
						ylines.add(joinstart);
						ylines.add(joinend);
					}
				}else{
					if(joinend.increase){
						rect.add(new Rectangle(joinend.x,x.y, x.start-x.end, joinend.end-joinend.start));
						ylines.remove(joinstart);
						ylines.remove(joinend);
					}else{
						YLine nleft = nearestYLine_fromLeft(x, ylines);
						int w = x.start-nleft.x;
						int h = nleft.end-x.y;
						rect.add(new Rectangle(nleft.x,x.y,w,h));
						nleft.setEnd(x.y);
						ylines.remove(joinstart);
						ylines.add(joinend);
					}
				}
			}
		}
		return rect.toArray(new Rectangle[rect.size()]);
	}


	private YLine nearestYLine_fromLeft(XLine x,YLines ys){
		int leftx;
		if(x.increase)leftx = x.start;
		else leftx = x.end;

		YLine l =null;
		for(YLine y:ys){
			if(y.x >= leftx)break;
			if(y.isIncluded(x.y)){
				l=y;
			}
		}
		return l;
	}

	private YLine nearestYLine_fromRight(XLine x,YLines ys){
		int rightx;
		if(x.increase)rightx = x.end;
		else rightx = x.start;

		YLine l =null;
		for(YLine y:ys){
			if(y.x <= rightx)continue;
			if(y.isIncluded(x.y)){
				l=y;
				break;
			}
		}
		return l;
	}

	private void toLine(ArrayList<XLine> xs,ArrayList<YLine> ys){
		int[] before = new int[2];
		double[] c = new double[6];
		int[] lastmove = new int[2];
		PathIterator p = area.getPathIterator(null);
		Line beforel = null,moveline = null;
		while(!p.isDone()){
			int x,y;
			Line l;
			switch(p.currentSegment(c)){
			case PathIterator.SEG_MOVETO:
				x = (int)c[0];
				y = (int)c[1];
				before[0] =x;
				before[1] = y;
				lastmove[0] = x;
				lastmove[1] = y;
				break;
			case PathIterator.SEG_LINETO:
				x = (int)c[0];
				y = (int)c[1];
				if(before[0]==x){
					YLine yl = new YLine(before[1], y, x);
					l = yl;
					ys.add(yl);
				}else{
					XLine xl = new XLine(before[0],x,y);
					l = xl;
					xs.add(xl);
				}
				before[0] =x;
				before[1] = y;
				if(beforel==null){
					moveline=l;
					beforel = l;
				}
				else {
					if(beforel.isHorizon() == l.isHorizon()){
						if(beforel.isHorizon()){
							beforel.setEnd(x);
							xs.remove(l);
						}else{
							beforel.setEnd(y);
							ys.remove(l);
						}
					}else{
						beforel.setJoinEnd(l);
						l.setJoinStart(beforel);
						beforel = l;
					}
				}
				break;
			case PathIterator.SEG_CLOSE:
				x = lastmove[0];
				y = lastmove[1];
				if(before[0]==x){
					YLine yl = new YLine(before[1], y, x);
					l = yl;
					ys.add(yl);
				}else{
					XLine xl = new XLine(before[0],x,y);
					l = xl;
					xs.add(xl);
				}
				if(beforel!=null){
					beforel.setJoinStart(l);
					l.setJoinStart(beforel);
				}
				if(moveline!=null){
					moveline.setJoinStart(l);
					l.setJoinEnd(moveline);
					moveline=null;
				}
				beforel = null;
				break;
			}
			p.next();
		}
	}

}

abstract class Line{

	int start,end;
	Line joinA,joinB;
	boolean increase;

	public Line(int s,int e) {
		start = s;
		end= e;
		increase = start<end;
	}

	public void setJoinStart(Line y){
		joinA = y;
	}

	public void setJoinEnd(Line y){
		joinB =y;
	}
	public Line getJoinStart() {
		return joinA;
	}
	public Line getJoinEnd() {
		return joinB;
	}

	public void setStart(int v){
		start = v;
		increase = start<end;
	}

	public void setEnd(int v){
		end = v;
		increase = start<end;
	}

	public boolean isIncluded(int v){
		double aa = (v-start)/(double)(end-start);
		return   (0<=aa&& aa<=1);
	}
	abstract public boolean isHorizon();
}

class XLine extends Line implements Comparable<XLine>{
	int y;
	public XLine(int x0,int x1,int y) {
		super(x0,x1);
		this.y = y;
	}

	@Override
	public int compareTo(XLine o) {
		return o.y-y;
	}

	@Override
	public void setJoinStart(Line y) {
		if(y.isHorizon())throw new Error();
		super.setJoinStart(y);
	}

	@Override
	public void setJoinEnd(Line y) {
		if(y.isHorizon())throw new Error();
		super.setJoinEnd(y);
	}

	@Override
	public YLine getJoinStart() {
		return (YLine)super.getJoinStart();
	}
	@Override
	public YLine getJoinEnd() {
		return (YLine)super.getJoinEnd();
	}

	@Override
	public boolean isHorizon() {
		return true;
	}
}

class YLine extends Line{
	int x;
	public YLine(int y0,int y1,int x) {
		super(y0,y1);
		this.x = x;
	}
	@Override
	public boolean isHorizon() {
		return false;
	}
	@Override
	public void setJoinStart(Line y) {
		if(!y.isHorizon())throw new Error();
		super.setJoinStart(y);
	}

	@Override
	public void setJoinEnd(Line y) {
		if(!y.isHorizon()){

			throw new Error(String.format("this :(%d->%d) x:%d,join :(%d->%d) x:%d",start,end,x,y.start,y.end,((YLine)y).x));
		}
		super.setJoinEnd(y);
	}
}

class YLines implements Iterable<YLine>{
	YLine[] array;
	int size=0;

	public YLines(int size) {
		array = new YLine[size];
	}

	public void add(YLine y){
		int x = y.x;
		YLine imp,imp2;
		int i=0;
		for(;i<size;i++){
			if(array[i].x > x){
				break;
			}
		}
		imp = array[i];
		array[i] = y;
		for(i++;i<size+1;i++){
			imp2 = array[i];
			array[i]=imp;
			imp=imp2;
		}
		size++;
	}

	public void remove(YLine y){
		int i;
		for(i=0;i<size;i++){
			if(array[i] == y){
				array[i] = null;
				break;
			}
		}
		for(i++;i<size;i++){
			array[i-1] = array[i];
		}
		size--;
	}

	@Override
	public Iterator<YLine> iterator() {
		return new Iterator<YLine>() {
			int i=0,s = size;
			public void remove() {}
			public YLine next() {return array[i++];}
			public boolean hasNext() {return i<s && array[i]!=null;}
		};
	}
}

*1:参考文献：大附 辰夫,佐藤 政生,橘 昌良,鳥居 司郎 複合長方形領域の最小分割 http://ci.nii.ac.jp/naid/110002723815/