package jp.sourceforge.qrcode.pattern;import jp.sourceforge.qrcode.QRCodeDecoder;import jp.sourceforge.qrcode.reader.*;import jp.sourceforge.qrcode.exception.FinderPatternNotFoundException;import jp.sourceforge.qrcode.exception.InvalidVersionInfoException;import jp.sourceforge.qrcode.exception.InvalidVersionException;import jp.sourceforge.qrcode.exception.VersionInformationException;import jp.sourceforge.qrcode.geom.*;import java.util.*;import jp.sourceforge.qrcode.util.*;public class FinderPattern {	public static final int UL = 0;	public static final int UR = 1;	public static final int DL = 2;		// this constant used for VersionInformation's error correction (BCC	static final int[] VersionInfoBit = {			0x07C94,0x085BC,0x09A99,0x0A4D3,0x0BBF6,0x0C762,0x0D847,			0x0E60D,0x0F928,0x10B78,0x1145D,0x12A17,0x13532,0x149A6,			0x15683,0x168C9,0x177EC,0x18EC4,0x191E1,0x1AFAB,0x1B08E,			0x1CC1A,0x1D33F,0x1ED75,0x1F250,0x209D5,0x216F0,0x228BA,			0x2379F,0x24B0B,0x2542E,0x26A64,0x27541,0x28C69	};		static DebugCanvas canvas = QRCodeDecoder.getCanvas();	Point[] center;	int version;	int[] sincos;	int[] width;	int[] moduleSize;		public static FinderPattern findFinderPattern(boolean[][] image)			throws FinderPatternNotFoundException,			VersionInformationException {		Line[] lineAcross = findLineAcross(image);		Line[] lineCross = findLineCross(lineAcross);		Point[] center = null;		try {			center = getCenter(lineCross);		} catch (FinderPatternNotFoundException e) {			throw e;		}		int[] sincos = getAngle(center);		center = sort(center, sincos);		int[] width = getWidth(image, center, sincos);		// moduleSize for version recognition		int[] moduleSize = {(width[UL] << QRCodeImageReader.DECIMAL_POINT) / 7,							(width[UR] << QRCodeImageReader.DECIMAL_POINT) / 7,							(width[DL] << QRCodeImageReader.DECIMAL_POINT) / 7};		int version = calcRoughVersion(center, width);		if (version > 6) {			try {				version = calcExactVersion(center, sincos, moduleSize, image);			} catch (VersionInformationException e) {				//use rough version data				// throw e;							}		}		return new FinderPattern (center, version, sincos, width, moduleSize);	}		FinderPattern (Point[] center, int version, int[] sincos, int[] width, int[] moduleSize) {		this.center = center;		this.version = version;		this.sincos = sincos;		this.width = width;		this.moduleSize = moduleSize;	}		public Point[] getCenter() {		return center;	}		public Point getCenter(int position) {		if (position >= UL && position <= DL)			return center[position];			else			return null;	}		public int getWidth(int position) {		return width[position];	}		public int[] getAngle() {		return sincos;	}		public int getVersion() {		return version;	}		public int getModuleSize() {		return moduleSize[UL];	}	public int getModuleSize(int place) {		return moduleSize[place];	}	public int getSqrtNumModules() {		return 17 + 4 * version;	}		/*	 * At first, to detect Finder Pattern, liner pattern (D:L:D:L:D)=(1:1:3:1:1) 	 * (D:dark point L:Light point) are extracted as line (both vertical and horizontal).	 * INFO: Although this method detects lines does not across Finder Patterns too, 	 *       these are ignored safely in after process (FinderPattern.findLineCross())	 */	static Line[] findLineAcross(boolean[][] image) {		final int READ_HORIZONTAL = 0;		final int READ_VERTICAL = 1;		int imageWidth = image.length;		int imageHeight = image[0].length;		//int currentX = 0, currentY = 0;		Point current = new Point();		Vector lineAcross = new Vector();				//buffer contains recent length of modules which has same brightness		int[] lengthBuffer = new int[5];		int  bufferPointer = 0;				int direction = READ_HORIZONTAL; //start to read horizontally		boolean lastElement = QRCodeImageReader.POINT_LIGHT;			while(true) {			//check points in image			boolean currentElement = image[current.getX()][current.getY()];			if (currentElement == lastElement) { //target point has same brightness with last point				lengthBuffer[bufferPointer]++;			}			else { //target point has different brightness with last point				if (currentElement == QRCodeImageReader.POINT_LIGHT) {					if (checkPattern(lengthBuffer, bufferPointer)) { //detected pattern						int x1, y1, x2, y2;						if (direction == READ_HORIZONTAL) {							//obtain X coordinates of both side of the detected horizontal pattern							x1 = current.getX(); 							for (int j = 0; j < 5; j++) {								x1 -= lengthBuffer[j];							}							x2 = current.getX() - 1; //right side is last X coordinate							y1 = y2 = current.getY();						}						else {							x1 = x2 = current.getX();							//obtain Y coordinates of both side of the detected vertical pattern							// upper side is sum of length of buffer							y1 = current.getY(); 							for (int j = 0; j < 5; j++) {								y1 -= lengthBuffer[j];							}							y2 = current.getY() - 1; // bottom side is last Y coordinate						}						lineAcross.addElement(new Line(x1, y1, x2, y2));					}				}				bufferPointer = (bufferPointer + 1) % 5; 				lengthBuffer[bufferPointer] = 1;				lastElement = !lastElement;			}						// determine if read next, change read direction or terminate this loop			if (direction == READ_HORIZONTAL) {				if (current.getX() < imageWidth - 1) {					current.translate(1, 0);				}				else if (current.getY() < imageHeight - 1) {					current.set(0, current.getY() + 1);					lengthBuffer =  new int[5];				}				else {					current.set(0, 0); //reset target point					lengthBuffer =  new int[5];					direction = READ_VERTICAL; //start to read vertically				}			}			else { //reading vertically				if (current.getY() < imageHeight - 1)					current.translate(0, 1);				else if (current.getX() < imageWidth - 1) {					current.set(current.getX() + 1, 0);					lengthBuffer = new int[5];				}				else {					break;				}			}		}				Line[] foundLines = new Line[lineAcross.size()];		for (int i = 0; i < foundLines.length; i++)			foundLines[i] = (Line) lineAcross.elementAt(i);				canvas.drawLines(foundLines,Color.LIGHTGREEN);		return foundLines;	}		static boolean checkPattern(int[] buffer, int pointer) {		final int[] modelRatio = {1, 1, 3, 1, 1};			int baselength = 0;		for (int i = 0; i < 5; i++) {			baselength += buffer[i];		}		// pseudo fixed point calculation. I think it needs smarter code		baselength <<= QRCodeImageReader.DECIMAL_POINT; 		baselength /= 7;		for  (int i = 0; i < 5; i++) {			int leastlength = baselength * modelRatio[i] - baselength / 2;			int mostlength = baselength * modelRatio[i] + baselength / 2;						//TODO rough finder pattern detection						int targetlength = buffer[(pointer + i + 1) % 5] << QRCodeImageReader.DECIMAL_POINT;			if (targetlength < leastlength || targetlength > mostlength) {				return false;			}		}		return true;	}		//obtain lines cross at the center of Finder Patterns		static Line[] findLineCross(Line[] lineAcross) {		Vector crossLines = new Vector();		Vector lineNeighbor = new Vector();		Vector lineCandidate = new Vector();		Line compareLine;		for (int i = 0; i < lineAcross.length; i++)			lineCandidate.addElement(lineAcross[i]);				for (int i = 0; i < lineCandidate.size() - 1; i++) {			lineNeighbor.removeAllElements();			lineNeighbor.addElement(lineCandidate.elementAt(i));			for (int j = i + 1; j < lineCandidate.size(); j++) {				if (Line.isNeighbor((Line)lineNeighbor.lastElement(), (Line)lineCandidate.elementAt(j))) {					lineNeighbor.addElement(lineCandidate.elementAt(j));					compareLine = (Line)lineNeighbor.lastElement();					if (lineNeighbor.size() * 5 > compareLine.getLength() &&							j == lineCandidate.size() - 1) {						crossLines.addElement(lineNeighbor.elementAt(lineNeighbor.size() / 2));						for (int k = 0; k < lineNeighbor.size(); k++)							lineCandidate.removeElement(lineNeighbor.elementAt(k));					}				}				//terminate comparison if there are no possibility for found neighbour lines				else if (cantNeighbor((Line)lineNeighbor.lastElement(), (Line)lineCandidate.elementAt(j)) ||					(j == lineCandidate.size() - 1)) {					compareLine = (Line)lineNeighbor.lastElement();					/*					 * determine lines across Finder Patterns when number of neighbour lines are 					 * bigger than 1/6 length of theirselves					 */										if (lineNeighbor.size() * 6 > compareLine.getLength()) {						crossLines.addElement(lineNeighbor.elementAt(lineNeighbor.size() / 2));						for (int k = 0; k < lineNeighbor.size(); k++) {							lineCandidate.removeElement(lineNeighbor.elementAt(k));						}					}					break;				}			}		}			Line[] foundLines = new Line[crossLines.size()];		for (int i = 0; i < foundLines.length; i++) {			foundLines[i] = (Line) crossLines.elementAt(i);		}		return foundLines;	}		static boolean cantNeighbor(Line line1, Line line2) {		if (Line.isCross(line1, line2))			return true;		return line1.isHorizontal()? Math.abs(line1.getP1().getY() - line2.getP1().getY()) > 1 : Math.abs(line1.getP1().getX() - line2.getP1().getX()) > 1;	}		//obtain slope of symbol	static int[] getAngle(Point[] centers) {		Line[] additionalLine = new Line[3];		for (int i = 0; i < additionalLine.length; i++) {			additionalLine[i] = new Line(centers[i],					centers[(i + 1) % additionalLine.length]);		}		// remoteLine - does not contain UL center		Line remoteLine = Line.getLongest(additionalLine);		Point originPoint = new Point();		for (int i = 0; i < centers.length; i++) {			if (!remoteLine.getP1().equals(centers[i]) &&				 !remoteLine.getP2().equals(centers[i])) {				originPoint = centers[i];				break;			}		}		canvas.println("originPoint is: " + originPoint);		Point remotePoint = new Point();		//with origin that the center of Left-Up Finder Pattern, determine other two patterns center.		//then calculate symbols angle