The 3D structure of a protein is the main physical support of a protein's biological function; 3D protein folds are primarily maintained through interactions between amino acids. Inter-residue contacts are essential for the stability of protein folds. Therefore, many methodologies in the fields of structure analysis, structure prediction, and structure-function relationships are based on residue contacts. The present study provides a comparative analysis of two approaches for determining contacts: the classical distance-threshold method and an application of Laguerre, or weighted Voronoi tessellation. First, we examined mean contact distributions and their dependence on residue volumes, accessibility and hydrophobicity. In general, the different methods gave concordant results, although the method based on Cα distances showed significant discrepancies with the all-atom tessellation method. We also analyzed preferential contacts between all amino acid species and studied the influence of protein chain length, the proximity of the residues along the sequence, and the secondary structure environment. Interestingly, the discrepancies between methods were occasionally large enough to substantially change the relative preferences of some contacts. Finally, a case study on disulfide bridges demonstrated the importance of the structural environment in determining contacts from tessellation. In conclusion, the tessellation method is more accurate because of its fine adaptation to local protein topology, with far-reaching implications for most contact-based prediction methods of protein folding.