The mechanisms that order cellular packing geometry are critical for the functioning of many tissues, but they are poorly understood. Here, we investigate this problem in the developing wing of Drosophila. The surface of the wing is decorated by hexagonally packed hairs that are uniformly oriented by the planar cell polarity pathway. They are constructed by a hexagonal array of wing epithelial cells. Wing epithelial cells are irregularly arranged throughout most of development, but they become hexagonally packed shortly before hair formation. During the process, individual cell boundaries grow and shrink, resulting in local neighbor exchanges, and Cadherin is actively endocytosed and recycled through Rab11 endosomes. Hexagonal packing depends on the activity of the planar cell polarity proteins. We propose that these proteins polarize trafficking of Cadherin-containing exocyst vesicles during junction remodeling. This may be a common mechanism for the action of planar cell polarity proteins in diverse systems.