A new method for estimating the packing quality of protein structures is presented. Atoms in high quality protein crystal structures are very uniformly distributed which is difficult to reproduce using structure prediction methods. Packing quality measures can therefore be used to assess structures of low quality and even to refine them. Previous methods mainly use the Voronoi cells of atoms to assess packing quality. The presented method uses only the lengths of edges in the Delaunay complex which is faster to compute since volumes of Voronoi cells are not evaluated explicitly. This is a novel application of the Delaunay complex that can improve the speed of packing quality computations. Doing so is an important step for, e.g., integrating packing measures into structure refinement methods. High- and low-resolution X-ray crystal structures were chosen to represent well- and poorly-packed structures respectively. Our results show that the developed method is correlated to the well-established RosettaHoles2 but three times faster.