dancin' expressions

The other expression for a really good dancer, or something you might say if you were really dancin' up a storm, is
'she could really cut a rug' or, 'man, we were really cuttin' the rug'.
This saying is actually more popular than polishin' the floor', but its association with danncing is not as obvious, since dancing rarely takes place on carpeted floors. Anyone know how cut a rug first became associated with dance?