matthiasm@8: function [overlap, normoverlap] = rectintSparse(A,B)
matthiasm@8: %
matthiasm@8: % A(i,:) = [x y w h]
matthiasm@8: % B(j,:) = [x y w h]
matthiasm@8: % overlap(i,j) = area of intersection
matthiasm@8: % normoverla(i,j)
matthiasm@8: %
matthiasm@8: % Same as built-in rectint, but uses less memory.
matthiasm@8: % Use rectintSparseC for a faster version.
matthiasm@8: %
matthiasm@8: 
matthiasm@8: leftA = A(:,1);
matthiasm@8: bottomA = A(:,2);
matthiasm@8: rightA = leftA + A(:,3);
matthiasm@8: topA = bottomA + A(:,4);
matthiasm@8: 
matthiasm@8: leftB = B(:,1)';
matthiasm@8: bottomB = B(:,2)';
matthiasm@8: rightB = leftB + B(:,3)';
matthiasm@8: topB = bottomB + B(:,4)';
matthiasm@8: 
matthiasm@8: numRectA = size(A,1);
matthiasm@8: numRectB = size(B,1);
matthiasm@8: 
matthiasm@8: %out = rectintSparseLoopC(leftA, rightA, topA, bottomA, leftB, rightB, topB, bottomB);
matthiasm@8: 
matthiasm@8: nnz = ceil(0.2*numRectA*numRectB); % guess of number of non-zeroes
matthiasm@8: overlap = sparse([], [], [], numRectA, numRectB, nnz);
matthiasm@8: normoverlap = sparse([], [], [], numRectA, numRectB, nnz);
matthiasm@8: for j=1:numRectB
matthiasm@8:   for i=1:numRectA
matthiasm@8:     tmp = (max(0, min(rightA(i), rightB(j)) - max(leftA(i), leftB(j)) ) ) .* ...
matthiasm@8: 	(max(0, min(topA(i), topB(j)) - max(bottomA(i), bottomB(j)) ) );
matthiasm@8:     if tmp>0
matthiasm@8:       overlap(i,j) = tmp;
matthiasm@8:       areaA = (rightA(i)-leftA(i))*(topA(i)-bottomA(i));
matthiasm@8:       areaB = (rightB(j)-leftB(j))*(topB(j)-bottomB(j));
matthiasm@8:       normoverlap(i,j) = min(tmp/areaA, tmp/areaB);
matthiasm@8:     end
matthiasm@8:     %fprintf('j=%d, i=%d, overlap=%5.3f, norm=%5.3f\n',...
matthiasm@8:     %	    j, i, overlap(i,j), normoverlap(i,j));
matthiasm@8:   end
matthiasm@8: end
matthiasm@8: 
matthiasm@8: 
matthiasm@8: if 0
matthiasm@8: N = size(bboxDense01,2); % 1000;
matthiasm@8: rect = bboxToRect(bboxDense01)';
matthiasm@8: A = rect(1:2,:);
matthiasm@8: B = rect(1:N,:);
matthiasm@8: 
matthiasm@8: tic; out1 = rectint(A, B); toc
matthiasm@8: tic; out2 = rectintSparse(A, B); toc
matthiasm@8: tic; out3 = rectintSparseC(A, B); toc
matthiasm@8: tic; out4 = rectintC(A, B); toc
matthiasm@8: assert(approxeq(out1, out2))
matthiasm@8: assert(approxeq(out1, full(out3)))
matthiasm@8: assert(approxeq(out1, out4))
matthiasm@8: end