As simple as it may sound it actually involves quite a few steps to achieve.
An outline would look something like this:
- Define the shape as a polygon, ie. point array
- Find bounds of polygon (the region the polygon fits inside)
- Contract polygon with padding using either a cetronid algorithm or simply a brute-force approach using center of bounds
- Define line height of text and use that as a basis for number of scan-lines
- Basically use a polygon-fill algorithm to find segment within the shape which can fill in text. The steps for this is:
- Use an odd/even scanner by getting an intersection point (using line intersection math) with text scan line and each of the lines between the points in the polygon
- Sort the points by x
- use odd and even point to create a segment. This segment will always be inside the polygon
- Add clipping using original polygon
- Draw in image
- Use the segments to get a width. Start parsing the text to fill and measure the width.
- When text width fits within the segment width then print the chars that fits
- Repeat for next text/words/chars until end of text or segments
In other words: you would need to implement a polygon fill algorithm but instead of filling in lines (per pixel line) you use the line as basis for the text.
This is fully doable; actually, I went ahead to create a challenge for myself on this problem, for the fun of it, so I created a generic solution that I put on GitHub released under MIT license.
The principle described above are implemented, and to visualize the steps:
Define the polygon and padding - here I chose to just use a simple brute-force and calculate a smaller polygon based on center and a padding value - the light grey is the original polygon and the black obviously the contracted version:
The points are defined as an array [x1, y1, x2, y2, ... xn, yn] and the code to contract it (see link to project for full source on all these parts):
var pPoints = [],
i = 0, x, y, a, d, dx, dy;
for(; i < points.length; i += 2) {
x = points[i];
y = points[i+1];
dx = x - bounds.px;
dy = y - bounds.py;
a = Math.atan2(dy, dx);
d = Math.sqrt(dx*dx + dy*dy) - padding;
pPoints.push(bounds.px + d * Math.cos(a),
bounds.py + d * Math.sin(a));
}
Next step is to define the lines we want to scan. The lines are based on line height for font:
That is simple enough - just make sure the start and end points are outside the polygon.
We use an odd/even scan approach and check intersection of the scanline versus all lines in the polygon. If we get a intersect point we store that in a list for that line.
The code to detect intersecting lines is:
function getIntersection(line1, line2) {
// "unroll" the objects
var p0x = line1.x1,
p0y = line1.y1,
p1x = line1.x2,
p1y = line1.y2,
p2x = line2.x1,
p2y = line2.y1,
p3x = line2.x2,
p3y = line2.y2,
// calc difference between the coords
d1x = p1x - p0x,
d1y = p1y - p0y,
d2x = p3x - p2x,
d2y = p3y - p2y,
// determinator
d = d1x * d2y - d2x * d1y,
px, py,
s, t;
// if is not intersecting/is parallel then return immediately
if (Math.abs(d) < 1e-14)
return null;
// solve x and y for intersecting point
px = p0x - p2x;
py = p0y - p2y;
s = (d1x * py - d1y * px) / d;
if (s >= 0 && s <= 1) {
// if s was in range, calc t
t = (d2x * py - d2y * px) / d;
if (t >= 0 && t <= 1) {
return {x: p0x + (t * d1x),
y: p0y + (t * d1y)}
}
}
return null;
}
Then we sort the point for each line and use pairs of points to create segments - this is actually a polygon-fill algorithm. The result will be:
The code to build segments is a bit extensive for this post so check out the project linked above.
And finally we use those segments to replace with actual text. We need to scan a text from current text pointer and see how much will fit inside the segment width. The current code is somewhat basic and skips a lot of considerations such as word breaks, text base-line position and so forth, but for initial use it will do.
The result when put together will be:
Hope this gives an idea about the steps involved.
