In most transport planning studies, one of the first steps is the definition of a zoning scheme into which the study area is divided and the corresponding space is discretized. There are no clear rules on how to carry out this operation in an optimal way, and the dominating practice is to proceed on the basis of experience, trying to mix a certain degree of within-zone homogeneity and the convenience of using administrative borders as zone limits. The potential errors generated with this operation were examined, both at the statistical level when trip matrices are based on sampling and at the geographical level when all trips starting or ending in a zone are assumed to do so at its centroid. A set of quality criteria for a general zoning scheme and an algorithm that constructs a basic zoning on the basis of a sample of geo-referenced trip extreme points and improves it in successive steps according to those criteria are presented. A case study based on the mobility survey for the Lisbon, Portugal, metropolitan area illustrates those steps and the improvements achieved in each step. The magnitude of those improvements is significant and shows that more attention should definitely be given to this initial process in the transport planning studies.