A long time ago in a galaxy far, far away (ie more than a year ago, and outside of the default country) one web developer decided to write a self-made Flash (he was not without delusions of grandeur, of course). The problem back then seemed difficult and very interesting. This article will be about some issues that he met on this way.
Those who draw in Flash know that the shapes in it (filled areas) within the same layer never overlap, and the lines are always drawn on top of the filled figures. This approach is, in my view, a nice plus - you have an image that you can see. However, writing a vector editor leads to the necessity of solving the problem to calculate the union of the drawable objects (lines, filled areas). Below I will try to show how it can be done step-by-step.
For simplicity, further I will refer to filled areas bounded by straight lines and quadratic Bezier curves as polygons. As a rule, mentiontioning the edges, I will keep in mind the visible stroke straight or curved segments.
So, we have two images that we want to combine. Any given set of edges, and polygons.
Here's what we know about the edges:
So, on the right you can see the 5 edges: two blue and three dark yellow.
What we know about the polygons:
In light of the fact that a polygon is a complex object, we shall describe it as a closed outer contour + set of unintersected inner contours (holes).
It is clear that the presence of the union of two of vector images is a difficult task, therefore I will break it down into several sub-tasks. That's what I've got:
As a result of all these actions in the original image, we can expect the desired result of the union.
I think it is clear that each of the subtasks is a sometimes non-trivial problem. Therefore, we will consider them separately.
There are different kinds of the segments, so consider three possible cases separately.
As you know, finding the intersection of the two straight segments is not particularly difficult, we need only remember that for the calculations it is convenient to represent them in a parametric form (formula y = kx + b has a fatal flaw: low precision for nearly-vertical lines):
// M - a point on the segment, S - the beginning of the segment, // D - the end of the segment, t - value in the range [0; 1] M1 = S1 + (D1-S1) * t1 // parametric representation of the first segment M2 = S2 + (D2-S2) * t2 // parametric representation of the second segment // Crossing - is when M1 = M2 - the system of equations, // from which we 's get the value t1: Xs1 + (Xd1-Xs1) * t1 = Xs2 + (Xd2-Xs2) * t2 Ys1 + (Yd1-Ys1) * t1 = Ys2 + (Yd2-Ys2) * t2
I will not describe the solving of the t1 (I think everyone can do it). After obtaining the values t1 we need to ensure that it lies in the range [0; 1] (otherwise, the segments do not intersect), then it can substitute a formula defining a first section, thus obtaining coordinates of the points of intersection:
Xm = Xs1 + (Xd1-Xs1) * t1 Ym = Ys1 + (Yd1-Ys1) * t1
The intersection of a Bezier curve and the straight segment is not so easy, but it is solved analytically, especially if we pre guess and rotate the segment and the curve so that the segment has become a strictly horizontal:
// P0, P1, P2 - the point defining the curve; t - value in the range [0; 1]; // parametric representation of the curve: M1 = (1-t1) ^ 2 * P0 + 2 * t1 * (1-t1) * P1 + t1 ^ 2 * P2 // S - the beginning of the segment, D - end; // parametric representation of the straight segment: M2 = S + (D - S) * t2 // rotate points P0, P1, P2, S and D by the angle a = -atan2 (Yd-Ys, Xd-Xs); // below are the known formulas for this rotate // (point specified by (X, Y) became the point (Xn, Yn)) Xn = X*cos(a) - Y*sin(a) Yn = X*sin(a) + Y*cos(a) // formula of the curve has not changed (but values P0, P1 and P2 are changed) Xm1 = (1-t1)^2 * Xp0 + 2*t1*(1-t1) * Xp1 + t1^2 * Xp2 Ym1 = (1-t1)^2 * Yp0 + 2*t1*(1-t1) * Yp1 + t1^2 * Yp2 // formula of the straight segment became simpler for coordinate Y: Xm2 = Xs + (Xd-Xs) * t2 Ym2 = Ys // since after the rotation we have Ys = Yd // M1 = M2, т.е. Xm1 = Xm2 Ym1 = Ym2 // enough to consider only the formula for Y, // because that is where there is a simplification: (1-t1)^2*Yp0 + 2*t1*(1-t1)*Yp1 + t1^2*Yp2 = Ys
Solving this quadratic equation, we find the value t1 (and there can be two). For each value of t1, as in the case of straight segments, it is necessary to make sure that it is in the range [0; 1]. Substituting the values of t1 in the original (before rotation) the formula of the curve, we obtain the coordinates of the desired intersection points.
Here you can do optimization: pre-check segments overlapping by bounding boxes and if no, then stop the current branch of recursion.The moment, which can cause difficulty - a dividing a Bezier curve into two parts (ie, the calculation of new control points, to determine the end point of the first curve, which coincides with the start point of the second curve, easily substituting in the formula of the curve t = 0.5). As it turned out, it is sufficient to calculate the coordinates of the centers of segments of a predetermined reference triangle - result points are the control points of the new curves. Figure on the left illustrates the solution: curve (P0, P1, P2) is divided into two curves, the support of which a first triangle (P0, P1 ', P2') is highlighted in blue. The control point of the second curve (P2 ', ..., P2) is calculated similarly.
To be continued...