Blob Blame Raw
/*
    ......... 2015 Ivan Mahonin

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <cassert>

#include "contour.h"


using namespace std;


const Vector Contour::blank;


void Contour::clear() {
	if (!chunks.empty()) {
		chunks.clear();
		first = 0;
	}
}

void Contour::move_to(const Vector &v) {
	if (chunks.empty()) {
		if (!v.is_equal_to(blank))
			chunks.push_back(Chunk(MOVE, v));
	} else {
		if (!v.is_equal_to(chunks.back().p1)) {
			if (chunks.back().type == MOVE)
				chunks.back().p1 = v;
			else
			if (chunks.back().type == CLOSE)
				chunks.push_back(Chunk(MOVE, v));
			else {
				chunks.push_back(Chunk(CLOSE, chunks[first].p1));
				chunks.push_back(Chunk(MOVE, v));
			}
		}
	}
	first = chunks.size();
}

void Contour::line_to(const Vector &v) {
	if (!v.is_equal_to(current()))
		chunks.push_back(Chunk(LINE, v));
}

void Contour::conic_to(const Vector &v, const Vector &t) {
	if (!v.is_equal_to(current()))
		chunks.push_back(Chunk(CONIC, v, t));
}

void Contour::cubic_to(const Vector &v, const Vector &t0, const Vector &t1) {
	if (!v.is_equal_to(current()))
		chunks.push_back(Chunk(CUBIC, v, t0, t1));
}

void Contour::close() {
	if (chunks.size() > first) {
		if (first > 0)
			chunks.push_back(Chunk(CLOSE, chunks[first-1].p1));
		else
			chunks.push_back(Chunk(CLOSE, blank));
		first = chunks.size();
	}
}

void Contour::line_split(
	Rect &ref_line_bounds,
	const Rect &bounds,
	const Vector &min_size,
	const Vector &p1,
	int level )
{
	assert(level > 0);

	if (allow_split_lines) {
		const Vector &p0 = current();
		if ( fabs(p1.x - p0.x) > min_size.x
		  || fabs(p1.y - p0.y) > min_size.y )
		{
			Vector p = (p0 + p1)*0.5;
			line_split(ref_line_bounds, bounds, min_size, p, level-1);
			line_split(ref_line_bounds, bounds, min_size, p1, level-1);
			return;
		}
	}

	line_to(p1);
	return;

	// TODO: fix bugs

	ref_line_bounds = ref_line_bounds.expand(p1);

	if (bounds.intersects(ref_line_bounds)) {
		Vector s = ref_line_bounds.p1 - ref_line_bounds.p0;
		if ( fabs(s.x) > min_size.x
		  || fabs(s.y) > min_size.y )
		{
			line_to(p1);
			ref_line_bounds.p0 = p1;
			ref_line_bounds.p1 = p1;
			return;
		}
	}

	if (!chunks.empty())
		chunks.back().p1 = p1;
}

void Contour::conic_split(
	Rect &ref_line_bounds,
	const Rect &bounds,
	const Vector &min_size,
	const Vector &p1,
	const Vector &center,
	Real radius,
	Real radians0,
	Real radians1,
	int level )
{
	assert(level > 0);

	const Vector &p0 = current();
	if ( fabs(p1.x - p0.x) > min_size.x
	  || fabs(p1.y - p0.y) > min_size.y )
	{
		Rect b = conic_bounds(p0, p1, center, radius, radians0, radians1);
		if (bounds.intersects(b)) {
			Real radians = 0.5*(radians0 + radians1);
			Vector p( radius*cos(radians) + center.x,
					  radius*sin(radians) + center.y );
			conic_split(ref_line_bounds, bounds, min_size,  p, center, radius, radians0, radians, level - 1);
			conic_split(ref_line_bounds, bounds, min_size, p1, center, radius, radians, radians1, level - 1);
			return;
		}
	}
	line_split(ref_line_bounds, bounds, min_size, p1);
}

void Contour::cubic_split(
	Rect &ref_line_bounds,
	const Rect &bounds,
	const Vector &min_size,
	const Vector &p1,
	const Vector &bezier_pp0,
	const Vector &bezier_pp1,
	int level )
{
	assert(level > 0);

	const Vector &p0 = current();
	if ( fabs(p1.x - p0.x) > min_size.x
	  || fabs(p1.y - p0.y) > min_size.y )
	{
		Rect b = cubic_bounds(p0, p1, bezier_pp0, bezier_pp1);
		if (bounds.intersects(b)) {
			Vector pp = (bezier_pp0 + bezier_pp1)*0.5;
			Vector pp00 = (p0 + bezier_pp0)*0.5;
			Vector pp11 = (p1 + bezier_pp1)*0.5;
			Vector pp01 = (pp00 + pp)*0.5;
			Vector pp10 = (pp11 + pp)*0.5;
			Vector p = (pp01 + pp10)*0.5;

			cubic_split(ref_line_bounds, bounds, min_size,  p, pp00, pp01, level - 1);
			cubic_split(ref_line_bounds, bounds, min_size, p1, pp10, pp11, level - 1);
			return;
		}
	}
	line_split(ref_line_bounds, bounds, min_size, p1);
}

void Contour::split(Contour &c, const Rect &bounds, const Vector &min_size) const {
	c.clear();

	Rect line_bounds;
	line_bounds.p0 = c.current();
	line_bounds.p1 = c.current();

	for(ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) {
		switch(i->type) {
		case MOVE:
			c.move_to(i->p1);
			line_bounds.p0 = c.current();
			line_bounds.p1 = c.current();
			break;
		case LINE:
		case CLOSE:
			c.line_split(line_bounds, bounds, min_size, i->p1);
			break;
		case CONIC:
			{
				const Vector &p0 = c.current();
				Vector center;
				Real radius = 0.0;
				Real radians0 = 0.0;
				Real radians1 = 0.0;
				if (conic_convert(p0, i->p1, i->t0, center, radius, radians0, radians1))
					c.conic_split(line_bounds, bounds, min_size, i->p1, center, radius, radians0, radians1);
				else
					c.line_split(line_bounds, bounds, min_size, i->p1);
			}
			break;
		case CUBIC:
			{
				const Vector &p0 = c.current();
				Vector pp0, pp1;
				cubic_convert(p0, i->p1, i->t0, i->t1, pp0, pp1);
				c.cubic_split(line_bounds, bounds, min_size, i->p1, pp0, pp1);
			}
			break;
		}
	}
}

bool Contour::conic_convert(
	const Vector &p0,
	const Vector &p1,
	const Vector &t,
	Vector &out_center,
	Real &out_radius,
	Real &out_radians0,
	Real &out_radians1 )
{
	Real tl = sqrt(t.x*t.x + t.y*t.y);
	if (fabs(tl) < 1e-6) {
		out_center = Vector();
		out_radius = 0.0;
		out_radians0 = 0.0;
		out_radians1 = 0.0;
		return false;
	}

	Vector d = p1 - p0;
	Vector n(-t.y/tl, t.x/tl);

	Real r = 0.5*(d.x*d.x + d.y*d.y)/(d.x*n.x + d.y*n.y);
	out_center = p0 + n*r;
	out_radius = fabs(r);
	out_radians0 = atan2(p0.y - out_center.y, p0.x - out_center.x);
	out_radians1 = atan2(p1.y - out_center.y, p1.x - out_center.x);
	bool ccw = r > 0.0;

	out_radians0 = wrap_angle(out_radians0, 2.0*M_PI);
	out_radians1 = wrap_angle(out_radians1, 2.0*M_PI);
	if (ccw) { if (out_radians1 < out_radians0) out_radians1 += 2.0*M_PI; }
	    else { if (out_radians1 > out_radians0) out_radians1 -= 2.0*M_PI; }

	return true;
}

Rect Contour::conic_bounds(
	const Vector &p0,
	const Vector &p1,
	const Vector &center,
	Real radius,
	Real radians0,
	Real radians1 )
{
	radius = fabs(radius);

	Rect r;
	r.p0 = p0;
	r.p1 = p1;

	if (angle_between(radians0, radians1, 0.0*M_PI, 2.0*M_PI))
		r = r.expand(Vector(center.x + radius, center.y));
	if (angle_between(radians0, radians1, 0.5*M_PI, 2.0*M_PI))
		r = r.expand(Vector(center.x, center.y + radius));
	if (angle_between(radians0, radians1, 1.0*M_PI, 2.0*M_PI))
		r = r.expand(Vector(center.x - radius, center.y));
	if (angle_between(radians0, radians1, 1.5*M_PI, 2.0*M_PI))
		r = r.expand(Vector(center.x, center.y - radius));

	return r;
}

void Contour::cubic_convert(
	const Vector &p0,
	const Vector &p1,
	const Vector &t0,
	const Vector &t1,
	Vector &out_bezier_pp0,
	Vector &out_bezier_pp1 )
{
	out_bezier_pp0 = t0/3.0 + p0;
	out_bezier_pp1 = p1 - t1/3.0;
}

Rect Contour::cubic_bounds(
	const Vector &p0,
	const Vector &p1,
	const Vector &bezier_pp0,
	const Vector &bezier_pp1 )
{
	Rect r;
	r.p0.x = min(min(p0.x, bezier_pp0.x), min(p1.x, bezier_pp1.x));
	r.p0.y = min(min(p0.y, bezier_pp0.y), min(p1.y, bezier_pp1.y));
	r.p1.x = max(max(p0.x, bezier_pp0.x), max(p1.x, bezier_pp1.x));
	r.p1.y = max(max(p0.y, bezier_pp0.y), max(p1.y, bezier_pp1.y));
	return r;
}

void Contour::transform(const Rect &from, const Rect &to) {
	Vector s( (to.p1.x - to.p0.x)/(from.p1.x - from.p0.x),
			  (to.p1.y - to.p0.y)/(from.p1.y - from.p0.y) );
	Vector o( to.p0.x - from.p0.x*s.x,
			  to.p0.y - from.p0.y*s.y );
	for(Contour::ChunkList::iterator i = chunks.begin(); i != chunks.end(); ++i) {
		i->p1 = i->p1*s + o;
		i->t0 = i->t0*s;
		i->t1 = i->t1*s;
	}
}

void Contour::downgrade(Contour &c, const Vector &min_size) const {
	c.clear();
	Rect r;
	for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) {
		switch(i->type) {
			case Contour::CLOSE:
				c.close();
				r.p0 = r.p1 = c.current();
				break;
			case Contour::MOVE:
				c.move_to(i->p1);
				r.p0 = r.p1 = c.current();
				break;
			case Contour::CONIC:
			case Contour::CUBIC:
			case Contour::LINE:
				r = r.expand(i->p1);
				if ( fabs(r.p1.x - r.p0.x) > min_size.x
				  || fabs(r.p1.y - r.p0.y) > min_size.y )
				{
					c.line_to(i->p1);
					r.p0 = r.p1 = c.current();
				}
				break;
		}
	}
}

void Contour::to_polyspan(Polyspan &polyspan) const {
	polyspan.move_to(0.0, 0.0);
	Vector p0;
	for(Contour::ChunkList::const_iterator i = chunks.begin(); i != chunks.end(); ++i) {
		switch(i->type) {
			case Contour::CLOSE:
				polyspan.close();
				break;
			case Contour::MOVE:
				polyspan.move_to(i->p1.x, i->p1.y);
				break;
			case Contour::LINE:
				polyspan.line_to(i->p1.x, i->p1.y);
				break;
			case Contour::CONIC: {
					Vector center;
					Real radius = 0.0;
					Real radians0 = 0.0;
					Real radians1 = 0.0;
					if (conic_convert(p0, i->p1, i->t0, center, radius, radians0, radians1)) {
						// TODO: fix bugs
						Vector pp0( center.x + 2.0*radius*cos(0.5*(radians0 + radians1)),
								    center.y + 2.0*radius*sin(0.5*(radians0 + radians1)) );
						polyspan.conic_to(pp0.x, pp0.y, i->p1.x, i->p1.y);
					} else {
						polyspan.line_to(i->p1.x, i->p1.y);
					}
				}
				break;
			case Contour::CUBIC: {
					Vector pp0, pp1;
					cubic_convert(p0, i->p1, i->t0, i->t1, pp0, pp1);
					polyspan.cubic_to(pp0.x, pp0.y, pp1.x, pp1.y, i->p1.x, i->p1.y);
				}
				break;
			default:
				break;
		}
		p0 = i->p1;
	}
}