This paper first proposes a new clustering algorithm for selection of reference points (RPs) based on virtual positions of access points for indoor localization in area without linear constraints, which can not only cluster automatically but also guarantee the consistency of methods between the offline phase clustering and the online phase positioning. A new weighted algorithm based on physical distance is then presented for position determination. With angle velocity measurement provided such as by gyroscope, the weighted algorithm is particularly suited for scenarios where the mobile moves along a trajectory. The number of clusters in traditional RP clustering algorithms needs to be predefined, which means an unsuitable number of clusters would lead to poor estimation accuracy. Traditional weighted K-nearest neighbor (WKNN) algorithm weights the RPs’coordinates by the inverse of the received signal strength indication (RSSI) difference, which is not accurate enough because of the exponential relationship between RSSI and physical distance. Furthermore, methods based on probabilistic model or data fusion do not consider the uneven spatial resolution of Wi-Fi RSSI. Experimental results show that the proposed weighted algorithm considerably outperforms the K-nearest neighbor (KNN), Euclidean-WKNN, ManhattanWKNN, EWKNN, LiFS, and GPR in terms of positioning accuracy which is defined as the cumulative distribution function of position error. The results also demonstrate that RPs in indoor area without linear constraints can be clustered automatically by the proposed clustering algorithm, and cumulative distribution function of the proposed clustering algorithm outperforms KNN, WKNN, RP location clustered, and signal distance clustered.