Adapting Marching Squares to operate on sparse matrices

Sammanfattning: Marching Squares is an algorithm that iterates over a given matrix filled with data points and outputs lines depending on the values in the grid. The algorithm iterates over the matrix four data points at a time in the shape of a square, hence its name. Those lines are later built to coherent polygons which could later be used in large-scale applications, such as in geographic information systems. In this study, two new variants of the Marching Squares algorithm are introduced, Delta A and Delta B. The goal of the new algorithms is to outperform the classical implementation in terms of memory and speed, when the given matrix is sparse. In conclusion, the Delta A variant performs better than the classical implementation of Marching Squares when the fillrate is 20-25% in terms of speed and has an advantage in peak memory allocation when the fillrate is below 7%. The Delta B variant performs better than the classical implementation in terms of speed up until a fillrate of 30% and has a much clearer advantage in terms of peak memory allocation for fillrates below 80%. It is shown to be advantageous for the new variants to iterate over non-zero data points rather than the grid for sparse matrices when creating polygons.