Welcome, guest | Sign In | My Account | Store | Cart

Photographic document images are often rotated, if only slightly. This code mediates an input of a series of four points--assumed to be the corners of a rectangular document--in any order, as mouse clicks. Then it determines the orientation of the points and calculates a "quality" value, as an indication to the user of how well the four points s/he has chosen approximate to the corners of a rotated rectangle. Finally, it makes the information that it has been passed, or that it has been able to glean, available to the script that invoked it.

Python, 143 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143``` ```from sets import Set class onePoint : def __init__ ( self, X, Y ) : self . x = X self . y = Y def __repr__ ( self ) : return 'onePoint ( %s, %s )' % ( self . x, self . y ) def DistanceSq ( P0, P1 ) : return ( P0 . x - P1 . x ) ** 2 + ( P0 . y - P1 . y ) ** 2 class FourCorners : """http://www.mathpages.com/home/kmath201.htm: ... area of the ... triangle (x2-x3)(y1-y2) - (x1-x2)(y2-y3) A = ------------------------------- 2 In this same way it's easy to deduce that the area enclosed by a general quadralateral can be expressed in terms of the coordinates of its verticies as (x2-x4)(y1-y3) - (x1-x3)(y2-y4) A = ------------------------------- 2 1 / \ = - ( (x2y1-x1y2) + (x3y2-x2y3) + (x4y3-x3y4) + (x1y4-x4y1) ) 2 \ / It's worth noting that, assuming all the verticies are in the ++ quadrant of the xy coordinate system (i.e., all the coordinates are positive), these formulas give the positive area only if the verticies are numbered clockwise around the perimeter. If they are counter- clockwise, the computed area is negative. Of course, a quadralateral can have crossing edges, such that the verticies are clockwise around one region and counter-clockwise around the other. Thus, the computed area of a non-degenerate quadralateral can vanish, as in the case of the quadralateral shown in Figure 3. """ def __init__ ( self, alignmentImageSize, originalImageSize ) : self . _four = [ ] self . alignmentImageSize = alignmentImageSize self . originalImageSize = originalImageSize def buildResult ( self, status ) : pointsCriterion = PointsCriterion ( * self . _four ) result = { } for item in self . __dict__ : result [ item ] = self . __dict__ [ item ] for item in pointsCriterion . __dict__ : result [ item ] = pointsCriterion . __dict__ [ item ] result [ 'number' ] = len ( self . _four ) return result def send ( self, pointTuple ) : point = onePoint ( * pointTuple ) for aFour in self . _four : if aFour . x == point . x and aFour . y == point . y : if len ( self . _four ) < 4 : return { 'number': len ( self . _four ), 'status': "Duplicate point (rejected)", } else : return self . buildResult ( "Duplicate point (rejected)" ) if len ( self . _four ) == 4 : distances = { } for aFour in self . _four : distances [ DistanceSq ( aFour, point ) ] = aFour self . _four . remove ( distances [ min ( distances ) ] ) self . _four . append ( point ) if len ( self . _four ) < 4 : return { 'number': len ( self . _four ), 'status': "Need four distinct points", } return self . buildResult ( 'Have four points' ) class PointsCriterion : def QuadrilateralAreaAux ( self, P0, P1, P2, P3 ) : return 0.5 * ( ( P1 . x - P3 . x ) * ( P0 . y - P2 . y ) - ( P0 . x - P2 . x ) * ( P1 . y - P3 . y ) ) def TriangleAreaAux ( self, P0, P1, P2 ) : return 0.5 * ( ( P1 . x - P2 . x ) * ( P0 . y - P1 . y ) - ( P0 . x - P1 . x ) * ( P1 . y - P2 . y ) ) def __init__ ( self, P0, P1, P2, P3 ) : areas = { } tours = [ [ 0, 1, 2, 3 ], [ 0, 1, 3, 2 ], [ 0, 2, 1, 3 ], [ 0, 3, 1, 2 ], ] points = [ P0, P1, P2, P3 ] for tour in tours : area = self . QuadrilateralAreaAux ( * tuple ( [ points [ t ] for t in tour ] ) ) if area : if area < 0 : tour . reverse ( ) areas [ abs ( area ) ] = tour area = max ( areas ) clockwiseCorners = areas [ area ] comparisonArea = 2. * self . TriangleAreaAux ( * tuple ( [ points [ t ] for t in clockwiseCorners [ : 3 ] ] ) ) corners = [ points [ p ] for p in clockwiseCorners ] horizontals = [ corner . x for corner in corners ] horizontals . sort ( ) verticals = [ corner . y for corner in corners ] verticals . sort ( ) lefts = Set ( [ corner for corner in corners if corner . x in horizontals [ : 2 ] ] ) rights = Set ( [ corner for corner in corners if corner . x in horizontals [ -2 : ] ] ) uppers = Set ( [ corner for corner in corners if corner . y in verticals [ : 2 ] ] ) lowers = Set ( [ corner for corner in corners if corner . y in verticals [ -2 : ] ] ) self . upperLeft = lefts . intersection ( uppers ) . pop ( ) self . lowerLeft = lefts . intersection ( lowers ) . pop ( ) self . upperRight = rights . intersection ( uppers ) . pop ( ) self . lowerRight = rights . intersection ( lowers ) . pop ( ) self . horizontalRacking = self . lowerLeft . x - self . upperLeft . x self . verticalRacking = self . upperRight . y - self . upperLeft . y self . upperMost = min ( [ P . y for P in corners ] ) self . leftMost = min ( [ P . x for P in corners ] ) self . rightMost = max ( [ P . x for P in corners ] ) self . lowerMost = max ( [ P . y for P in corners ] ) self . quality = area / comparisonArea self . corners = corners if __name__ == "__main__" : fourCorners = FourCorners ( ( 110, 110 ), ( 500, 500 ) ) for corner in [ ( 0, 0 ), ( 0, 0 ), ( 100, 100 ), ( 0, 100 ), ( 0, 100 ), ( 100, 0 ), ( 5, 0 ), ( 100, 0 ), ( 100, 120 ), ( 100, 101 ), ( 100, 0 ), ] : result = fourCorners . send ( corner ) for item in result : print item, result [ item ] print 100 * '=' ``` Created by Bill Bell on Wed, 10 Mar 2004 (PSF)