Using Telecom V&H Coordinates In C#

• Download source - 17.5 KB

Introduction

In the late 1950s, Jay Donald developed a 2D coordinate system for AT&T to make it easier to calculate call charges, whose rates were based on the mileage between two points in the U.S. and Canada. His system is known as the Donald Elliptic Projection, and it represents points with vertical (V) and horizontal (H) values on a grid overlaid across North America. The grid’s origin (where V,H = 0,0) is in the upper North Atlantic Ocean, and the V and H values increase down and to the left respectively. Values from 0 to 10,000 cover the majority of the continental U.S. and Canada. This system made it easy to calculate distances in the field using slide rules, which was important in the 1950s. AT&T began using this system to define the areas where specific calling rates applied (i.e., rate centers). In the 1980s, this system was also adopted for expressing locations of telecom hardware (i.e., wire centers).

Background

The V&H coordinate system is still used to provide the locations for rate centers and wire centers in modern telecom reference databases. For example, the LERG (Local Exchange Routing Guide) published by iconectiv (formerly Telcordia) includes V&H coordinates for wire centers in its LERG7 table and rate centers in its LERG8 table. CCMI’s QTEL Telecom Suite provides rate center and wire center information, and their web site provides a way to freely look up this information. For example, CCMI’s NPA-NXX Rate Center Lookup page shows the following V&H coordinates for some NPA NXX values in Nashville, TN (where NPA = area code and NXX = central office (exchange) code):

This example shows that both NPA NXX values are in the same rate center, but they use different wire centers because they’re owned by different carriers.

While the V&H coordinate system is still used in the North American telecom industry, it is not typically used elsewhere. It is not a well-documented system, and the math behind its relation to other coordinate systems is complex. The V&H coordinate system is mentioned briefly at Voip-info.org and in Peter Dana’s Coordinate Systems Overview. However, the only detailed reference guide for the V&H coordinate system is available for sale on iconectiv’s Vertical and Horizontal Coordinates page. That page provides some background info and maps along with a link to purchase the Telcordia Notes on V&H Coordinates: The Mystery Unveiled. That document is a 190-page PDF that currently sells for $95. It delves into much of the complicated math behind the V&H coordinate system, how it relates to latitude and longitude, and how and why distance calculations work with it.

Most users of V&H coordinates no longer care about the math behind the system; they’re concerned only with how to use the coordinates for distance and position calculations. With modern computing power and mapping technology, it’s fast and desirable to convert V&H coordinates to and from latitude and longitude. That process is complex, but programmers at Bellcore (which became Telcordia) provided free C implementations of the algorithms in the 1990s and made them available on Usenet newsgroups such as comp.dcom.telecom.tech. An anonymous Bellcore employee created an ll_to_vh.c module for latitude and longitude to V&H conversion, which was later improved by Tom Libert. Then Col. G.L. Sicherman at Lucent/Bellcore took that ll_to_vh code, combined it with notes from an internal Bellcore memo by Erik Grimmelmann, and coded the vh2ll.c module for V&H to latitude and longitude conversion.

Those ll_to_vh and vh2ll modules are the code upon which all other public conversion implementations (including the one in this article) are based. That C code has been ported to at least Java (here and here), Python, and Perl/XS, but I couldn’t find a C# port. Since the history was fascinating and tangentially related to my day job, I decided to port the C code to C# and "clean it up" to look and behave like modern C# and .NET code.

Using the Code

The attached C# code defines a VHPoint structure with the following API:

public struct VHPoint : IEquatable<VHPoint>, IFormattable
{
    public VHPoint(double vertical, double horizontal)
    {
        this.Vertical = vertical;
        this.Horizontal = horizontal;
    }

    public VHPoint(GeoCoordinate coordinate)
    {
        // Note: This is based on the work of an anonymous
        // Bellcore employee with later changes by Tom Libert.
        ...
    }

    public GeoCoordinate ToGeoCoordinate()
    {
        // Note: This is based on an original implementation
        // by Col. G. L. Sicherman at Lucent (Bell Labs).
        ...
    }

    public double GetDistanceTo(VHPoint point, DistanceAlgorithm algorithm, DistanceUnit units)
    {
        ...
    }

    public static readonly VHPoint Origin;
    public double Vertical { get; }
    public double Horizontal { get; }

    // Other methods: operator==, operator!=, GetHashCode, Equals, ToString
    ...
}

VHPoint provides a constructor that takes V&H coordinates as doubles. Traditionally, V&H coordinates are stored as integers in telecom databases. However, the V&H algorithms work fine with fractional coordinates, so there’s no reason to restrict the API to integers. Integer conversion can be done by the VHPoint caller if desired.

There’s also a constructor that takes an instance of .NET 4’s GeoCoordinate class to initialize the VHPoint using latitude and longitude. Internally, this uses the algorithm from Bellcore’s ll_to_vh.c module to convert latitude and longitude to V&H coordinates. The ToGeoCoordinate method complements that constructor and provides the conversion from V&H coordinates to latitude and longitude. It uses the algorithm from Col. Sicherman’s vh2ll.c module to do the conversion.

I would love to provide a clear, succinct explanation of these conversion algorithms, but that’s beyond my abilities. Telcordia’s document takes 190 pages to explain the math behind the algorithms. Rather than provide an explanation, I’ve tried to provide a clear, succinct port of the C code to C#. I used Visual Studio’s refactoring tools to safely rename variables and constants when I thought it would make the code clearer. But beyond that, we’re stuck with the sparse comments from the original C code for explanations of what the code is doing and why.

The GetDistanceTo method provides three different algorithms for estimating the distance between two VHPoints. It can return the distance in meters, kilometers, international miles, or U.S. survey miles. The supported distance algorithms are:

• Short Calculation – The fastest way to calculate distances using just the V&H coordinates. It's calculated as Sqrt(((V₁ – V₂)² + (H₁ – H₂)²) / 10).
• Long Calculation – A longer, iterative way to calculate rate distances using just the V&H coordinates. It takes into account how the V&H grid cell sizes increase gradually as the distance increases.
• GeoCoordinate – The slowest way to calculate distances. This converts the V&H coordinates to latitude and longitude and then calculates the distance using GeoCoordinate’s GetDistanceTo method.

The "Short Calculation" for distance was the first algorithm used with V&H coordinates, and its simplicity was the primary motivator for the creation of the V&H coordinate system. Later, as computational power increased, the iterative "Long Calculation" was devised to provide more accurate estimates for rate mileage. The "GeoCoordinate" algorithm is provided as a modern alternative only; it wasn’t used as a traditional method for estimating rate mileage. Each algorithm produces slightly different estimates.

The VHPoint code uses C# 6 syntax, which can be compiled in Visual Studio 2015 or later. Some C# 6 specific features used are getter-only auto-properties, expression-bodied function members, using static, string interpolation, and nameof expressions. VHPoint only uses readonly fields, so instances are immutable and thread-safe. It also implements <a href="https://msdn.microsoft.com/en-us/library/ms131187.aspx">IEquatable<VHPoint></a> and the == and != operators for easy equality checking.

Here’s a simple example that uses VHPoints for Austin, TX and Nashville, TN. It estimates the mileage between them using the "Short Calculation" algorithm. Then it outputs the V&H coordinates, the latitude and longitude coordinates, and the estimated mileage between them.

var austinTx = new VHPoint(9004, 3995);
var nashvilleTn = new VHPoint(7010, 2710);
var usMilesBetweenAustinAndNashville = austinTx.GetDistanceTo
(nashvilleTn, DistanceAlgorithm.ShortVHCalculation, DistanceUnit.InternationalMile);
WriteLine($"Austin, TX: {austinTx} ({austinTx.ToGeoCoordinate()})");
WriteLine($"Nashville, TN: {nashvilleTn} ({nashvilleTn.ToGeoCoordinate()})");
WriteLine($"Miles between: {usMilesBetweenAustinAndNashville:N1}");

The output of this is:

Austin, TX: {V=9004, H=3995} (30.2693702251436, -97.7325447113926)
Nashville, TN: {V=7010, H=2710} (36.1593150338062, -86.7734248612693)
Miles between: 750.2

Google estimates a car trip between Austin, TX and Nashville, TN at 865 miles along roads. However, the mileage estimate above is along a great circle, which is the route a plane would fly between the two cities, so it is shorter than a driving route. GPS Visualizer estimates the great circle route between Austin’s airport (AUS) and Nashville’s airport (BNA) as 756.1 miles. Even though the V&H coordinates above were for midtown areas instead of the airports, we can see that VHPoint’s mileage estimate is fairly accurate.

Test Cases

The attached Program.cs file runs through several test cases for each VHPoint operation to validate that each operation is consistent and correct.

Test(0, 0, 50.7305, -42.8054, "VH Grid Origin", "Upper North Atlantic Ocean");
Test(2207, 11384, 64.8383, -147.7024, "Fairbanks", "Alaska");
Test(3961, 1370, 44.3134, -69.7775, "Augusta", "Maine");
Test(5623, 5794, 47.8427, -100.6696, "Butte", "North Dakota");
Test(7010, 2710, 36.1593, -86.7734, "Nashville", "Tennessee");
Test(8351, 527, 25.7746, -80.1903, "Miami", "Florida");
Test(9004, 3995, 30.2693, -97.7325, "Austin", "Texas");
Test(9476, 7620, 32.6749, -117.1077, "National City", "California");
Test(11591, 15609, 21.3142, -157.8634, "Honolulu", "Hawaii");
Test(7944, -3044, 17.7467, -64.7082, "St Croix", "Virgin Islands");

The Test procedure takes a pair of V&H coordinates and latitude and longitude coordinates to make sure the VHPoint code correctly handles conversions to and from latitude and longitude. It attempts to reverse geocode the latitude and longitude to ensure the point is in the expected city. It also compares the distance estimates (for each algorithm and unit) to known points to make sure the results are consistent.

EnsureLongCalc(6272, 2992, 6130, 2925, 50, "Indianapolis to Muncie (Indiana)");
EnsureLongCalc(5536, 2828, 5461, 2993, 57, "Detroit to Flint (Michigan)");
EnsureLongCalc(8285, 4651, 7947, 4373, 141, "Eldorado to Oklahoma City (Oklahoma)");
EnsureLongCalc(7235, 4599, 7110, 4369, 85, "Abilene to Topeka (Kansas)");
EnsureLongCalc(5536, 2828, 5986, 3426, 238, "Detroit, MI to Chicago, IL");

The EnsureLongCalc method does additional checking of the "Long Calculation" algorithm for estimating rate mileage. Several publicly available AT&T state guidebooks (e.g., Michigan, Oklahoma, Kansas) include the algorithm with a detailed test case, so it was important to make sure the algorithm handled those cases correctly.

The full output of the test program is:

Austin, TX: {V=9004, H=3995} (30.2693702251436, -97.7325447113926)
Nashville, TN: {V=7010, H=2710} (36.1593150338062, -86.7734248612693)
Miles between: 750.2

-------------------- VH Grid Origin, Upper North Atlantic Ocean --------------------
Given V&H: {V=0, H=0}
Given Lat/Long: 50.7305, -42.8054
Address: Reverse Geocoding Request Status: ZERO_RESULTS
Calculated Lat/Long: 50.7305527204251, -42.805421995133 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=50.7305527204251,-42.805421995133
Calculated V&H: {V=0.00272955582386203, H=-0.0115524752491183} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.00 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.00 mi
Distance To Downtown Nashville, TN Using Given V&H: 2376.65 mi
Distance To TN State Capitol Using Calculated Lat/Long: 2382.62 mi

-------------------- Fairbanks, Alaska --------------------
Given V&H: {V=2207, H=11384}
Given Lat/Long: 64.8383, -147.7024
Address: 300 Slater Dr, Fairbanks, AK 99701, USA
Calculated Lat/Long: 64.8383870101231, -147.702487081487 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=64.8383870101231,-147.702487081487
Calculated V&H: {V=2207.01982176852, H=11383.9990191629} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 3135.40 mi
Distance To TN State Capitol Using Calculated Lat/Long: 3146.15 mi

-------------------- Augusta, Maine --------------------
Given V&H: {V=3961, H=1370}
Given Lat/Long: 44.3134, -69.7775
Address: 98 Perham St, Augusta, ME 04330, USA
Calculated Lat/Long: 44.3134895095705, -69.7775311987667 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=44.3134895095705,-69.7775311987667
Calculated V&H: {V=3961.01136066591, H=1369.98383929929} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 1053.19 mi
Distance To TN State Capitol Using Calculated Lat/Long: 1056.72 mi

-------------------- Butte, North Dakota --------------------
Given V&H: {V=5623, H=5794}
Given Lat/Long: 47.8427, -100.6696
Address: 2901-2973 4th Ave NW, Butte, ND 58723, USA
Calculated Lat/Long: 47.8427878988344, -100.669606900516 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=47.8427878988344,-100.669606900516
Calculated V&H: {V=5623.01691999776, H=5793.9929727455} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 1069.34 mi
Distance To TN State Capitol Using Calculated Lat/Long: 1074.24 mi

-------------------- Nashville, Tennessee --------------------
Given V&H: {V=7010, H=2710}
Given Lat/Long: 36.1593, -86.7734
Address: 222 2nd Ave S, Nashville, TN 37201, USA
Calculated Lat/Long: 36.1593150338062, -86.7734248612693 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=36.1593150338062,-86.7734248612693
Calculated V&H: {V=7010.0003079036, H=2709.99485696478} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.00 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.00 mi
Distance To Downtown Nashville, TN Using Given V&H: 0.00 mi
Distance To TN State Capitol Using Calculated Lat/Long: 0.75 mi

-------------------- Miami, Florida --------------------
Given V&H: {V=8351, H=527}
Given Lat/Long: 25.7746, -80.1903
Address: 2-50 NE 2nd Ave, Miami, FL 33132, USA
Calculated Lat/Long: 25.7746122738116, -80.1903149887716 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=25.7746122738116,-80.1903149887716
Calculated V&H: {V=8351.00039400534, H=526.996302815198} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.00 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.00 mi
Distance To Downtown Nashville, TN Using Given V&H: 810.17 mi
Distance To TN State Capitol Using Calculated Lat/Long: 817.50 mi

-------------------- Austin, Texas --------------------
Given V&H: {V=9004, H=3995}
Given Lat/Long: 30.2693, -97.7325
Address: 965-1099 N Interstate 35 Frontage Rd, Austin, TX 78702, USA
Calculated Lat/Long: 30.2693702251436, -97.7325447113926 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=30.2693702251436,-97.7325447113926
Calculated V&H: {V=9004.01056278259, H=3994.9867130089} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 750.15 mi
Distance To TN State Capitol Using Calculated Lat/Long: 752.51 mi

-------------------- National City, California --------------------
Given V&H: {V=9476, H=7620}
Given Lat/Long: 32.6749, -117.1077
Address: 835-899 Roosevelt Ave, National City, CA 91950, USA
Calculated Lat/Long: 32.6749441711387, -117.10779765405 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=32.6749441711387,-117.10779765405
Calculated V&H: {V=9476.00600927168, H=7619.98059652587} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 1737.51 mi
Distance To TN State Capitol Using Calculated Lat/Long: 1739.43 mi

-------------------- Honolulu, Hawaii --------------------
Given V&H: {V=11591, H=15609}
Given Lat/Long: 21.3142, -157.8634
Address: 361 River St, Honolulu, HI 96817, USA
Calculated Lat/Long: 21.3142669712309, -157.863494374223 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=21.3142669712309,-157.863494374223
Calculated V&H: {V=11591.0212039459, H=15608.9826801904} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 4328.63 mi
Distance To TN State Capitol Using Calculated Lat/Long: 4337.12 mi

-------------------- St Croix, Virgin Islands --------------------
Given V&H: {V=7944, H=-3044}
Given Lat/Long: 17.7467, -64.7082
Address: Christiansted Harbor Seaplane Base (SSB), Christiansted, St Croix, USVI
Calculated Lat/Long: 17.7467681163929, -64.7082328429113 (from Given V&H)
Calculated Lat/Long Map URL: http://maps.google.com/maps?q=17.7467681163929,-64.7082328429113
Calculated V&H: {V=7944.00747498826, H=-3044.01425437623} (from Given Lat/Long)
Distance From Given V&H To Calculated V&H: 0.01 mi
Distance From Given Lat/Long To Calculated Lat/Long: 0.01 mi
Distance To Downtown Nashville, TN Using Given V&H: 1843.39 mi
Distance To TN State Capitol Using Calculated Lat/Long: 1854.93 mi

Points of Interest

The units of the V&H grid are based on the square root of 1/10^th of a mile, which is why the division by 10 occurs inside the radical in the "Short Calculation" distance formula. The V&H grid was created before the international mile was standardized in 1959, so V&H grid miles are actually based on the U.S. survey mile. One international mile is exactly 0.999998 U.S. survey miles, so they differ by only 2 parts per million, which is about 1/8^th of an inch or 3.2 mm. For points 1,000 miles apart, the international and U.S survey distances differ by about 10.5 feet (3.2 m).

There is an Alaskan variation of the V&H grid that is even more obscure than the standard V&H grid. The Alaskan V&H grid uses a different center point that isn’t publicly documented. The LERG8 table includes Alaskan V&H coordinates as "minor" coordinates. The LergInfo.doc file says that minor coordinates are used to rate calls when the calling and called numbers "are in Rate Centers that are closer together than a number of air miles specified in the rating company's tariff". LergInfo.doc goes on to say that the minor V&H coordinates in Alaska are computed using a different algorithm than major V&H coordinates. When I asked iconectiv for more information about Alaskan minor coordinates, I was told by a routing engineer:

"All we know about Alaska is that the minors are computed against a different midpoint, undoubtedly to reduce the error caused by the distortion of plotting the planet on 2D coordinates. All major V&Hs and all non-Alaska minors are centered on a point near the middle of the 48 contiguous states and southern tier of Canadian provinces. (The point is near the Manitoba-Minnesota border.) Alaska coordinates are the least accurate in this system because they are the furthest from that point. Alaska minors, presumably created by agreement among Alaskan service providers, are based on a point somewhere in Alaska, and are used for intra-Alaska calls only."

So minor coordinates on the Alaskan V&H grid won’t work correctly with the VHPoint type. The "Short Calculation" and "Long Calculation" distance algorithms might work if the Alaskan V&H grid units are also based on the square root of 1/10^th of a mile, but I can’t find any documentation that guarantees that. The VHPoint logic for converting to and from latitude and longitude (and thus the "GeoCoordinate" distance algorithm) will not work because of the different center point. But unless you work at an Alaskan phone company and are rating calls that originate and terminate inside Alaska, this shouldn’t be too much of a limitation.