Tutorial Using Edge Based Techniques Part 2

Under Construction: More content coming soon.

Introduction

In Part I of this series of wiki articles, we described how to use Tinfour's pinwheel iterator to identify the immediate neighbors of a vertex in a Delaunay triangulation. In this second part of the Tutorial Using Edge-Based Techniques we will look at how we can use that concept to implement an application that detects anomalous sample points within a data survey.

The demonstration application we present here is based on the algorithms and ideas described in the Tinfour Project Notes webpage Using the Delaunay triangulation to detect anomalies in unstructured data. That article offered a real-world example that detected problematic temperature reports in a set of weather observations collected for a single hour in March of 2019. At that time, there was a significant error in data reported by a weather station located in the Gulf of Mexico. The article describes how errors and other anomalies could be detected by comparing data for one vertex to values obtained for its neighbors. In general, Tinfour's Project Notes center on concepts that could be applied using any software library that supported the Delaunay triangulation while these wiki pages focus on concrete implementations using the Tinfour API. So in these notes, we will look at the specific code techniques we used to obtain the results in the Project Notes.

The test data: Meterological Aerodrome Reports (METARs)

In the aviation and weather communities, real-time meteorological data is collected from a global network of weather stations which report observations once an hour. These reports are issued in text-based messages using a standard format known as the Meterological Aerodrome Report, or METAR. For this tutorial, we downloaded historical METARs from the U.S. National Center for Atmospheric Research (NCAR). While the processing of the raw data is outside the scope of this article, the data that we use in the example code below consists of a Java array of objects of type Metar with the following layout:

    class Metar {
        String stationID;    // Four uppercase letters or numerical digits
        double latitude;     // in degrees
        double longitude;    // in range -180 up to, but not including, 180
        int    temperature;  // degrees C
    };

METAR messages are always identified by a four-character station ID. For weather stations located weather stations associated with airports, the station ID will be the ICAO code for that airport (i.e. KLAX for Los Angeles International, RKSI for Seoul Korea, etc.). The figure below depicts temperature data for the anomalous data reported by station KHHV in 2019. KHHV is an automated reportng station located on an oil drilling platform located over an underwater feature known as the Alaminos Canyon in the Gulf of Mexico. The Delaunay triangulation shown in the image used METAR locations as vertices. The color-coded temperature data was interpolated from the Delaunay triangulation using Tinfour's Natural Neighbor Interpolator.

Working with geographic coordinates

The Tinfour API is designed to process vertices distributed over a 2D coordinate plane. The Tinfour Vertex class includes elements x and y which usually provide Cartesian coordinates. So to process METARs, which are obtained from points located on the surface of the Earth, we need some method for projecting geographic coordinates (latitude and longitude) to a Cartesian form. This kind of coordinate transformation is actually a major topic in Geographic Information Systems (GIS) and cartographic applications in general. For our purposes, we will just use a simplified version of the Mercator projection which is commonly used in web-based map applications (Mapquest, Google Maps, Carto, Mapbox, etc.).

The Mercator projection has the advantage that it can be used in interactive map applications to allow a user to continuously pan East and West without interruption. That feature makes the projection especially attractive when looking at low to medium latitudes (when cartographers speak of low and medium latitudes, they are typically referring to the magnitude of the latitude, rather than whether it is North or South). However, for higher latitudes, those larger than 60 degrees North or South, the Mercator introduces so much distortion of scale that it becomes problematic. So, if we were concerned about weather observations for higher latitudes, we would need to implement special handling for those stations. For purposes of this example code, we will ignore that consideration and focus on the problem at hand.

The following Java method maps a latitude and longitude to a point on the Cartesian plan. The coordinates are scaled based on the radius of the Earth in kilometers. Although it provides limited accuracy, it is sufficient for our purposes:

  static Point2D geo2Merc(double lat, double lon) {
    double x   = Math.toRadians(lon)* EARTH_RADIUS_KM;
    double phi = Math.toRadians(lat);
    double y   = Math.log(Math.tan(Math.PI / 4 + phi / 2)) * EARTH_RADIUS_KM;
    return new Point2D.Double(x, y);
  }

Wrapping around the International Date Line

Longitude presents a special problem when connecting vertices in a Delaunay triangulation. If we have a weather station located at 1 degree West (-1.0 degrees) and another at 1 degree East (+1.0 degrees), the first statiion is clearly to the left of the second when viewed on a coordinate plane.