need help with algorithm for generalized middleline of polyline shape
bram
I have a question about the design of an algorithm. any comments would be very appreciated. thanks!
I am working on a "digital ink and paint" program, a digital equivalent of classic Disney-like cell animation. I am looking for an algorithm to reduce polyline shapes which represent the contours of pen strokes ( artists drawings that have been scanned and vectorized) into a more simplified line representation where only the middle line of each stroke is taken into account, and not the thickness of the stroke, ie not the contour but the "middle line". The rationale behind it is that in digital ink and paint you have two layers: the "line art" layer, where line thickness and line texture is important, and the so called "color layer" where only the division of the image in colored zones is important (in handmade cell animation the same effect is achieved by drawing on one side of a cell and painting it on the back side).
The problem is arbitrary shapes need to be supported:
- the simplest case: a straight line drawn with a marker pen, would result in a vectorized contour consisting of a polyline in the form of a long small rectangle. the required middle line would then be a straight line in the middle of the rectangle. But a "real" line has variable thickness and usually ends in a tip.
- 2nd case: drawing an X-shape. the contour will be not convex, the "middle line" becomes two lines.
- 3rd case : a circle (or topological equivalent)
- 4rth case: a composition of these 2nd and 3rd cases, e.g. a drawing of a pentagram.
I am thinking of a two phase algorithm:
- first do a topological analysis by identifying tip points and crossings and construct a planar graph representing the underlying structure. Partition the contour points by identifying them as laying on edges or vertices of this graph.
- the midpoint of a "tip" node is the point itself
- the midpoint of a "crossing" node is a the centroid of the (convex) shape of the points on crossing node
- the middel line of an edge starts and ends on the middle points of its vertices. the points on an edge are divided in say a "top" and a "bottom" partition, separated by the two "left tip" and "right tip" points of the vertices. Then a triangulation is constructed where each triangle should have both "top" and "bottom" points. The middleline of the edge is then the polyline formed by the centroids of each triangle, plus the endpoints.
There are still some I need to work out
- represent "holes" in the topological phase. can a graph
represent those?
- the triangulation of an edge
- constructing the middleline for and edge from the centroids of the triangulation.
bram
I think it will be easier to first construct the triangulation mesh and then infer the topology from it. I also changed my mind about how a middle line is constructed from a triangulation mesh.
For the triangulation I will search the shortest line segment that connects two point of the polyline AND that falls completely inside it. This way
the plygon is split in two parts and I can recursively repeat this proces. All added segments + original polyline will result in the desired
triangulation mesh.
Also, I suspect that the midpoint of every added segment will lay on the middleline we are looking for.
bram
"shortest line segment that connects two point of the polyline AND that falls completely inside it. "
- for each point:
- "find the shortest line segment that connects this point with another point of the polyline AND that falls completely inside it. "
- take the minimum
sub-algorithm:
"find the shortest line segment that connects this point with another point of the polyline AND that falls completely inside it. "
Here I start from the following observation:
- let P(i) be the first point
- if we iterate through the line segments P(i)P(i+1), P(i)P(i+2), P(i)P(i+3), etc.. , the slope of these line segments will increase in a monotone way as, long as the polygon P(i)..P(i+j)P(i) is convex. If for a certain j the polygon P(i)..P(i+j)P(i) becomes non-convex, the slope will decrease and subsequenst segments P(i)P(i+j) fall outside the original polygon untill the slope is again greater than the last maximum.
- if we iterate in the other direction, the slope will first decrease, then increase where the polygon is not convex.
- if we alternate between those two directions, we get some sort of minimax algorithm with a narrowing window of minimum and maximum slopes that indicate which line segments fall into the original polygon. we stop when the two iterators arrive at the same point.
- for each line segment that is valid (i.e. is inside) we calculate the length. we keep track of the line segment with minimal length