The paper proposes the histogram-based density discovery scheme as an alternative complement in obtaining density to LOUVRE, a landmark-based routing in the vehicular urban environment. The histogram-based scheme does not have the scalability problem as the P2P density scheme. Furthermore, it better accurately determines the road connectivity by considering non-uniform density. The paper makes the contribution of finding the optimal segment size to guarantee density and connectivity accuracy by evaluating thousands of mobility traces from a realistic mobility generator. Results have verified the scheme's accuracy and its scalability.