# Contour pushing algorithm

I'm implementing push contour feature for web application. It is an ability to change the contour by touching it. Mouse pointer becomes a circle that bumps contour (like in Photoshop). Contour is polyline object and pushing circle is some point with defined radius.

Sequence of actions on mousemove is following:

1. Detect points in polyline that are closer to pushing point than defined radius
2. push those points or just draw circle segment in the defined area.

Questions:

1. How to determine points that are need to be pushed? I can iterate all segments in polyline (300-600 segments) and calculate distance for each like here: https://gist.github.com/mattdesl/47412d930dcd8cd765c871a65532ffac . But in this case full iteration 60 times per second is quite performance hard. May by some algorithm can do it more afficient?
2. How to push the point? we can't just change it position. As 1 point finally can become 2 points. It is more like drawing circle segment.
• Welcome to CS.SE! Please ask only one question per post. – D.W. Mar 3 at 22:28

I suggest you use a data structure for nearest neighbor search to speed up the process of finding all points in the polyline that are closer than the defined radius. That should lead to a significant speedup.

After some time of investigation and development I came up with some type of hybrid "Greiner–Hormann clipping algorithm" implementation and other approaches.

Following steps were used:

1. At first - generate two circles-polygons based on previous and current mouse move position.
2. Merge them using Convex Hull calculation by implementation Graham scan algorithm.
3. Detect all intersections between polyLine and generated capsule. Details:
1. Traverse two polygons and generate new one based on union/subtraction mode. Notes:
• traversal direction is chosen by sorted polar angle - to cover shared segments that Greiner–Hormann can not handle;
• starting point is calculated as one of the extreme vertices;
• for subtraction mode we traverse all possible polygons. Than we pick up one with the biggest area;
• detecting polygon order implements Shoelace algorithm (https://en.wikipedia.org/wiki/Shoelace_formula).
1. Optimize contour by removing:
• duplicates;
• close points, that are located closer than 1 pixel;
• points in one line by keeping only edges of the line.