+ * @return {@link DetectorResult} encapsulating results of detecting a Data Matrix Code
+ * @throws NotFoundException if no Data Matrix Code can be found
+ */
+ public DetectorResult detect() throws NotFoundException {
+
+ ResultPoint[] cornerPoints = rectangleDetector.detect();
+ ResultPoint pointA = cornerPoints[0];
+ ResultPoint pointB = cornerPoints[1];
+ ResultPoint pointC = cornerPoints[2];
+ ResultPoint pointD = cornerPoints[3];
+
+ // Point A and D are across the diagonal from one another,
+ // as are B and C. Figure out which are the solid black lines
+ // by counting transitions
+ Vector transitions = new Vector(4);
+ transitions.addElement(transitionsBetween(pointA, pointB));
+ transitions.addElement(transitionsBetween(pointA, pointC));
+ transitions.addElement(transitionsBetween(pointB, pointD));
+ transitions.addElement(transitionsBetween(pointC, pointD));
+ Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
+
+ // Sort by number of transitions. First two will be the two solid sides; last two
+ // will be the two alternating black/white sides
+ ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
+ ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
+
+ // Figure out which point is their intersection by tallying up the number of times we see the
+ // endpoints in the four endpoints. One will show up twice.
+ Hashtable pointCount = new Hashtable();
+ increment(pointCount, lSideOne.getFrom());
+ increment(pointCount, lSideOne.getTo());
+ increment(pointCount, lSideTwo.getFrom());
+ increment(pointCount, lSideTwo.getTo());
+
+ ResultPoint maybeTopLeft = null;
+ ResultPoint bottomLeft = null;
+ ResultPoint maybeBottomRight = null;
+ Enumeration points = pointCount.keys();
+ while (points.hasMoreElements()) {
+ ResultPoint point = (ResultPoint) points.nextElement();
+ Integer value = (Integer) pointCount.get(point);
+ if (value.intValue() == 2) {
+ bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
+ } else {
+ // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
+ if (maybeTopLeft == null) {
+ maybeTopLeft = point;
+ } else {
+ maybeBottomRight = point;
+ }
+ }
+ }
+
+ if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ // Bottom left is correct but top left and bottom right might be switched
+ ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };
+ // Use the dot product trick to sort them out
+ ResultPoint.orderBestPatterns(corners);
+
+ // Now we know which is which:
+ ResultPoint bottomRight = corners[0];
+ bottomLeft = corners[1];
+ ResultPoint topLeft = corners[2];
+
+ // Which point didn't we find in relation to the "L" sides? that's the top right corner
+ ResultPoint topRight;
+ if (!pointCount.containsKey(pointA)) {
+ topRight = pointA;
+ } else if (!pointCount.containsKey(pointB)) {
+ topRight = pointB;
+ } else if (!pointCount.containsKey(pointC)) {
+ topRight = pointC;
+ } else {
+ topRight = pointD;
+ }
+
+ // Next determine the dimension by tracing along the top or right side and counting black/white
+ // transitions. Since we start inside a black module, we should see a number of transitions
+ // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
+ // end on a black module:
+
+ // The top right point is actually the corner of a module, which is one of the two black modules
+ // adjacent to the white module at the top right. Tracing to that corner from either the top left
+ // or bottom right should work here.
+ int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(),
+ transitionsBetween(bottomRight, topRight).getTransitions());
+ if ((dimension & 0x01) == 1) {
+ // it can't be odd, so, round... up?
+ dimension++;
+ }
+ dimension += 2;
+
+ //correct top right point to match the white module
+ ResultPoint correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension);
+
+ //We redetermine the dimension using the corrected top right point
+ int dimension2 = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(),
+ transitionsBetween(bottomRight, correctedTopRight).getTransitions());
+ dimension2++;
+ if ((dimension2 & 0x01) == 1) {
+ dimension2++;
+ }
+
+ BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, correctedTopRight, dimension2);
+
+ return new DetectorResult(bits, new ResultPoint[]{topLeft, bottomLeft, bottomRight, correctedTopRight});
+ }
+
+ /**
+ * Calculates the position of the white top right module using the output of the rectangle detector
+ */
+ private ResultPoint correctTopRight(ResultPoint bottomLeft,
+ ResultPoint bottomRight,
+ ResultPoint topLeft,
+ ResultPoint topRight,
+ int dimension) {
+
+ float corr = distance(bottomLeft, bottomRight) / (float)dimension;
+ int norm = distance(topLeft, topRight);
+ float cos = (topRight.getX() - topLeft.getX()) / norm;
+ float sin = (topRight.getY() - topLeft.getY()) / norm;
+
+ ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
+
+ corr = distance(bottomLeft, bottomRight) / (float)dimension;
+ norm = distance(bottomRight, topRight);
+ cos = (topRight.getX() - bottomRight.getX()) / norm;
+ sin = (topRight.getY() - bottomRight.getY()) / norm;
+
+ ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
+
+ int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() - transitionsBetween(bottomRight, c1).getTransitions());
+ int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() - transitionsBetween(bottomRight, c2).getTransitions());
+
+ if (l1 <= l2){
+ return c1;
+ }
+
+ return c2;
+ }
+
+ // L2 distance
+ private static int distance(ResultPoint a, ResultPoint b) {
+ return (int) Math.round(Math.sqrt((a.getX() - b.getX())
+ * (a.getX() - b.getX()) + (a.getY() - b.getY())
+ * (a.getY() - b.getY())));
+ }
+
+ /**
+ * Increments the Integer associated with a key by one.
+ */
+ private static void increment(Hashtable table, ResultPoint key) {
+ Integer value = (Integer) table.get(key);
+ table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
+ }
+
+ private static BitMatrix sampleGrid(BitMatrix image,
+ ResultPoint topLeft,
+ ResultPoint bottomLeft,
+ ResultPoint bottomRight,
+ ResultPoint topRight,
+ int dimension) throws NotFoundException {
+
+ GridSampler sampler = GridSampler.getInstance();
+
+ return sampler.sampleGrid(image,
+ dimension,
+ 0.5f,
+ 0.5f,
+ dimension - 0.5f,
+ 0.5f,
+ dimension - 0.5f,
+ dimension - 0.5f,
+ 0.5f,
+ dimension - 0.5f,
+ topLeft.getX(),
+ topLeft.getY(),
+ topRight.getX(),
+ topRight.getY(),
+ bottomRight.getX(),
+ bottomRight.getY(),
+ bottomLeft.getX(),
+ bottomLeft.getY());
+ }
+
+ /**
+ * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.