Abstract: To address the copyright protection requirements of point data in vector maps, this paper proposes a lossless watermarking algorithm based on storage characteristics. First, Thiessen polygons are constructed from the coordinate points of the vector map, with each point feature corresponding to a unique polygon. Secondly, the ordering of point features is determined according to the magnitude relationship between the perimeters of adjacent polygons. Thirdly, the perimeters of adjacent polygons are summed pairwise and normalized using the min-max method. A mapping function establishes the relationship between the watermark and the normalized values. Finally, the storage order of adjacent point features is adjusted to embed the watermark. For watermark detection, Thiessen polygons are reconstructed, and the watermark is extracted based on the ordering of adjacent point features and the established mapping relationship. Experiments demonstrate that the algorithm is robust against translation, scaling, and rotation. Moreover, since no coordinate values are modified during embedding, the method achieves lossless watermarking, preserves the usability of high-precision map data, and enhances the algorithm’s practicality.