Algorithm Roadmap for Uxarray

[hongyuchen1030]

Overview

The Uxarray project proposes an algorithm that provides core functionality for geometry and integral operators. The pipeline for achieving these functionalities includes a series of helper functions as building blocks. The roadmap for achieving these functionalities involves developing and implementing these helper functions first, and then integrating them to create the core functionalities.

Expected Functionalities

Geometry Operators

- LATLONBOX:  Given an array of faces on the sphere, determine the minimum bounding rectangle of all faces in latitude-longitude space.

- CROSSSECTION:  Given an arbitrary line on the sphere and associated mesh (set of spherical polygons), generate all line segments confined to singular polygons.

- DUAL:  Compute the dual mesh (the set of spherical polygons connecting centroids of each mesh centroid)

- TRIANGULATION: Divide the arbitrary input meshes into triangles [very complicated, low priority]

Integral operators:​

​
- NON-CONSERVATIVE ZONAL AVG:  Given a set of lines of constant latitude, determine the fractional length from each of the faces that are crossed by the line of constant latitude.​

- CONSERVATIVE ZONAL AVG:  Given a set of latitude intervals, determine the fractional area from each of the faces that are crossed by the areal band.  These weights can be used to compute conservative zonal averages.​

- REGIONAL INTEGRAL:  Given a spherical polygon, determine the fractional area from each of the faces covered by the polygon.  These weights then can be used for “integrating” a field over the specified polygon.​

- REGRID:  Given two sets of spherical polygons, calculate the fractional area covered by all pairs of overlapping polygons.  These areas can then be used as “weights” for defining a conservative map between data on the two meshes.​

Roadmap / Goals

1. CROSS SECTION:

1.1. Detect if a given point is within the given great circle arc #356
1.2. Calculate the accurate and robust intersection point between two great circle arcs
1.3. Calculate the accurate and robust intersection point between a great circle arc and a constant latitude

2. LATLONBOX:

After the implementation of step 1.1 and 1.2, we can proceed to following functions

2.1. Determine if a given point is within a given polygon
2.2. Retrieve the bounding box for each polygon (Now exploring finding the most accurate float of the boundary)
2.3. Utilize an all-closed KD-Tree to store latitude and longitude bound

3. CONSERVATIVE ZONAL AVG:

After the implementation of the entire step 3, we can use bounding boxes to retrieve candidate polygons. Before proceeding to the following functionalities, we also need to make sure 1.3 is implemented.
3.1. Correct weight calculation for each face (Need to think about the overlapped/ shared edge) utilizing the sweep-line algorithm

4. Regrid:

After the implementation of the entire step 3, we can use bounding boxes to retrieve candidate polygons. Before proceeding to the following functionalities, we also need to make sure 1.3 is implemented.
3.1. Correct weight calculation for each face (Need to think about the overlapped/ shared edge) utilizing the sweep-line algorithm