ShortStraw: A Simiple and Effective Corner Finder for Polylines

Aaron Wolin and Tracy Hammond

Summary

ShortStraw is a simple corner finding algorithm for polylines. The algorithm initially resamples points in a stroke to be equidistant using the approach presented by Wobbrock et al. The algorithm then uses a bottom-up approach to find initial corner candidates by finding the length of "straws" in a stroke. Straw lengths are calculated at each point using the euclidean distance between two points that form a window around that point (±3). Based on a median straw length, any straw shorter than 0.95 * median is considered a corner candidate. The algorithm then uses a top-down approach to remove false postives and find missed corners. This is done by first checking if two consecutive corners contain a line between them. If not, a corner has been missed. The corner threshold is relaxed, and new corners computed between those two corners. A collinear check is done on triplet corners where the middle corner is removed if the corners are found to be collinear. The algorithm's accuracy, whether "correct corners found" or "all-or-nothing," was greater than that of Sezgin's and Kim and Kim's.

Discussion

The algorithm is incredibly simple, and elegant in that simplicity. The concept of straws work as an effective metaphor for the algorithm. The accuracy of the algorithm speaks for itself. However, one could argue that the test symbols did not contain an equal number of acute, right, and obtuse angles, and favored right and acute angles, which favor the algorithm. If either Sezgin or Kim and Kim perform better on obtuse corners, then the accuracies may be closer with a more equally balanced set. Although, I doubt these algorithms are better with obtuse, as obtuse angles seem like the more difficult corners to recognize.

The obvious problem with this algorithm, as described by the authors, is the difficult this algorihtm has in recognizing obtuse angles. A possible solution could be to have a second more relaxed threshold for obtuse candidate corners. For each obtuse candidate corner, one of the lines could be extended to create an acute angle opposite the obtuse angle. A threshold is applied to the acute angle. Anything greater than the threshold (say 5 degrees) is considered a corner.