Late 16th century; earliest use found in Henry Billingsley (d. 1606), merchant and translator. Either from recti- + line + -ed, or from post-classical Latin rectilineus rectiline + -ed. Compare earlier right-lined.