An algorithm to interpolate concavities
José Duarte, Mark M. McKenney · 2021
Region interpolation methods impose restrictions that have an influence on how concavities are transformed, potentially, causing their transformation to be unnatural, e.g., a concavity unexpectedly appears (disappears) from (to) a point. In this work we present an algorithm to transform a line segment to a concavity, and a line segment to a simple non-closed linestring with possibly several concavities. The algorithm is deterministic, it does not assume that an element in the source is transformed directly to an element (or set of elements) in the target, works in stages (steps), i.e., several different transformations can occur while an element in the source is transformed to an element in the target, and its output is a set of moving segments representing the transformation. The complexity of a non-optimized implementation of the transformation of a segment to a concavity using the algorithm is O (kn2), where k is the number of steps in the transformation (the number of intermediate transformations in the transformation) and n is the number of points in the target geometry. The algorithm is primarily devised to be integrated with the region interpolation methods proposed in the spatiotemporal databases literature.