AreaPocket.cpp

// AreaPocket.cpp
// Copyright 2011, Dan Heeks
// This program is released under the BSD license. See the file COPYING for details.

// implements CArea::MakeOnePocketCurve

#include "Area.h"

#include <map>
#include <set>

static const CAreaPocketParams* pocket_params = NULL;

class IslandAndOffset
{
public:
	const CCurve* island;
	CArea offset;
	std::list<CCurve> island_inners;
	std::list<IslandAndOffset*> touching_offsets;

	IslandAndOffset(const CCurve* Island)
	{
		island = Island;

		offset.m_curves.push_back(*island);
		offset.m_curves.back().Reverse();

		offset.Offset(-pocket_params->stepover);


		if(offset.m_curves.size() > 1)
		{
			for(std::list<CCurve>::iterator It = offset.m_curves.begin(); It != offset.m_curves.end(); It++)
			{
				if(It == offset.m_curves.begin())continue;
				island_inners.push_back(*It);
				island_inners.back().Reverse();
			}
			offset.m_curves.resize(1);
		}
	}
};

class CurveTree
{
	static std::list<CurveTree*> to_do_list_for_MakeOffsets;
	void MakeOffsets2();
	static std::list<CurveTree*> islands_added;

public:
	Point point_on_parent;
	CCurve curve;
	std::list<CurveTree*> inners;
	std::list<const IslandAndOffset*> offset_islands;
	CurveTree(const CCurve &c)
	{
		curve = c;
	}
	~CurveTree(){}

	void MakeOffsets();
};
std::list<CurveTree*> CurveTree::islands_added;

class GetCurveItem
{
public:
	CurveTree* curve_tree;
	std::list<CVertex>::iterator EndIt;
	static std::list<GetCurveItem> to_do_list;

	GetCurveItem(CurveTree* ct, std::list<CVertex>::iterator EIt):curve_tree(ct), EndIt(EIt){}

	void GetCurve(CCurve& output);
	CVertex& back(){std::list<CVertex>::iterator It = EndIt; It--; return *It;}
};

std::list<GetCurveItem> GetCurveItem::to_do_list;
std::list<CurveTree*> CurveTree::to_do_list_for_MakeOffsets;

void GetCurveItem::GetCurve(CCurve& output)
{
	// walk around the curve adding spans to output until we get to an inner's point_on_parent
	// then add a line from the inner's point_on_parent to inner's start point, then GetCurve from inner

	// add start point
	if(CArea::m_please_abort)return;
	output.m_vertices.insert(this->EndIt, CVertex(curve_tree->curve.m_vertices.front()));

	std::list<CurveTree*> inners_to_visit;
	for(std::list<CurveTree*>::iterator It2 = curve_tree->inners.begin(); It2 != curve_tree->inners.end(); It2++)
	{
		inners_to_visit.push_back(*It2);
	}

	const CVertex* prev_vertex = NULL;

	for(std::list<CVertex>::iterator It = curve_tree->curve.m_vertices.begin(); It != curve_tree->curve.m_vertices.end(); It++)
	{
		const CVertex& vertex = *It;
		if(prev_vertex)
		{
			Span span(prev_vertex->m_p, vertex);

			// order inners on this span
			std::multimap<double, CurveTree*> ordered_inners;
			for(std::list<CurveTree*>::iterator It2 = inners_to_visit.begin(); It2 != inners_to_visit.end();)
			{
				CurveTree *inner = *It2;
				double t;
				if(span.On(inner->point_on_parent, &t))
				{
					ordered_inners.insert(std::make_pair(t, inner));
					It2 = inners_to_visit.erase(It2);
				}
				else
				{
					It2++;
				}
				if(CArea::m_please_abort)return;
			}

			if(CArea::m_please_abort)return;
			for(std::multimap<double, CurveTree*>::iterator It2 = ordered_inners.begin(); It2 != ordered_inners.end(); It2++)
			{
				CurveTree& inner = *(It2->second);
				if(inner.point_on_parent.dist(back().m_p) > 0.01/CArea::m_units)
				{
					output.m_vertices.insert(this->EndIt, CVertex(vertex.m_type, inner.point_on_parent, vertex.m_c));
				}
				if(CArea::m_please_abort)return;

				// vertex add after GetCurve
				std::list<CVertex>::iterator VIt = output.m_vertices.insert(this->EndIt, CVertex(inner.point_on_parent));

				//inner.GetCurve(output);
				GetCurveItem::to_do_list.push_back(GetCurveItem(&inner, VIt));
			}

			if(back().m_p != vertex.m_p)output.m_vertices.insert(this->EndIt, vertex);
		}
		prev_vertex = &vertex;
	}

	if(CArea::m_please_abort)return;
	for(std::list<CurveTree*>::iterator It2 = inners_to_visit.begin(); It2 != inners_to_visit.end(); It2++)
	{
		CurveTree &inner = *(*It2);
		if(inner.point_on_parent != back().m_p)
		{
			output.m_vertices.insert(this->EndIt, CVertex(inner.point_on_parent));
		}
		if(CArea::m_please_abort)return;

		// vertex add after GetCurve
		std::list<CVertex>::iterator VIt = output.m_vertices.insert(this->EndIt, CVertex(inner.point_on_parent));

		//inner.GetCurve(output);
		GetCurveItem::to_do_list.push_back(GetCurveItem(&inner, VIt));

	}
}

class IslandAndOffsetLink
{
public:
	const IslandAndOffset* island_and_offset;
	CurveTree* add_to;
	IslandAndOffsetLink(const IslandAndOffset* i, CurveTree* a){island_and_offset = i; add_to = a;}
};

static Point GetNearestPoint(CurveTree* curve_tree, std::list<CurveTree*> &islands_added, const CCurve &test_curve, CurveTree** best_curve_tree)
{
	// find nearest point to test_curve, from curve and all the islands in 
	double best_dist;
	Point best_point = curve_tree->curve.NearestPoint(test_curve, &best_dist);
	*best_curve_tree = curve_tree;
	for(std::list<CurveTree*>::iterator It = islands_added.begin(); It != islands_added.end(); It++)
	{
		CurveTree* island = *It;
		double dist;
		Point p = island->curve.NearestPoint(test_curve, &dist);
		if(dist < best_dist)
		{
			*best_curve_tree = island;
			best_point = p;
			best_dist = dist;
		}
	}

	return best_point;
}

void CurveTree::MakeOffsets2()
{
	// make offsets

	if(CArea::m_please_abort)return;
	CArea smaller;
	smaller.m_curves.push_back(curve);
	smaller.Offset(pocket_params->stepover);

	if(CArea::m_please_abort)return;

	// test islands
	for(std::list<const IslandAndOffset*>::iterator It = offset_islands.begin(); It != offset_islands.end();)
	{
		const IslandAndOffset* island_and_offset = *It;

		if(GetOverlapType(island_and_offset->offset, smaller) == eInside)
			It++; // island is still inside
		else
		{
			inners.push_back(new CurveTree(*island_and_offset->island));
			islands_added.push_back(inners.back());
			inners.back()->point_on_parent = curve.NearestPoint(*island_and_offset->island);
			if(CArea::m_please_abort)return;
			Point island_point = island_and_offset->island->NearestPoint(inners.back()->point_on_parent);
			if(CArea::m_please_abort)return;
			inners.back()->curve.ChangeStart(island_point);
			if(CArea::m_please_abort)return;

			// add the island offset's inner curves
			for(std::list<CCurve>::const_iterator It2 = island_and_offset->island_inners.begin(); It2 != island_and_offset->island_inners.end(); It2++)
			{
				const CCurve& island_inner = *It2;
				inners.back()->inners.push_back(new CurveTree(island_inner));
				inners.back()->inners.back()->point_on_parent = inners.back()->curve.NearestPoint(island_inner);
				if(CArea::m_please_abort)return;
				Point island_point = island_inner.NearestPoint(inners.back()->inners.back()->point_on_parent);
				if(CArea::m_please_abort)return;
				inners.back()->inners.back()->curve.ChangeStart(island_point);
				to_do_list_for_MakeOffsets.push_back(inners.back()->inners.back()); // do it later, in a while loop
				if(CArea::m_please_abort)return;
			}

			smaller.Subtract(island_and_offset->offset);

			std::set<const IslandAndOffset*> added;

			std::list<IslandAndOffsetLink> touching_list;
			for(std::list<IslandAndOffset*>::const_iterator It2 = island_and_offset->touching_offsets.begin(); It2 != island_and_offset->touching_offsets.end(); It2++)
			{
				const IslandAndOffset* touching = *It2;
				touching_list.push_back(IslandAndOffsetLink(touching, inners.back()));
				added.insert(touching);
			}

			while(touching_list.size() > 0)
			{
				IslandAndOffsetLink touching = touching_list.front();
				touching_list.pop_front();
				touching.add_to->inners.push_back(new CurveTree(*touching.island_and_offset->island));
				islands_added.push_back(touching.add_to->inners.back());
				touching.add_to->inners.back()->point_on_parent = touching.add_to->curve.NearestPoint(*touching.island_and_offset->island);
				Point island_point = touching.island_and_offset->island->NearestPoint(touching.add_to->inners.back()->point_on_parent);
				touching.add_to->inners.back()->curve.ChangeStart(island_point);
				smaller.Subtract(touching.island_and_offset->offset);

				// add the island offset's inner curves
				for(std::list<CCurve>::const_iterator It2 = touching.island_and_offset->island_inners.begin(); It2 != touching.island_and_offset->island_inners.end(); It2++)
				{
					const CCurve& island_inner = *It2;
					touching.add_to->inners.back()->inners.push_back(new CurveTree(island_inner));
					touching.add_to->inners.back()->inners.back()->point_on_parent = touching.add_to->inners.back()->curve.NearestPoint(island_inner);
					if(CArea::m_please_abort)return;
					Point island_point = island_inner.NearestPoint(touching.add_to->inners.back()->inners.back()->point_on_parent);
					if(CArea::m_please_abort)return;
					touching.add_to->inners.back()->inners.back()->curve.ChangeStart(island_point);
					to_do_list_for_MakeOffsets.push_back(touching.add_to->inners.back()->inners.back()); // do it later, in a while loop
					if(CArea::m_please_abort)return;
				}

				for(std::list<IslandAndOffset*>::const_iterator It2 = touching.island_and_offset->touching_offsets.begin(); It2 != touching.island_and_offset->touching_offsets.end(); It2++)
				{
					if(added.find(*It2)==added.end() && ((*It2) != island_and_offset))
					{
						touching_list.push_back(IslandAndOffsetLink(*It2, touching.add_to->inners.back()));
						added.insert(*It2);
					}
				}
			}

			if(CArea::m_please_abort)return;
			It = offset_islands.erase(It);

			for(std::set<const IslandAndOffset*>::iterator It2 = added.begin(); It2 != added.end(); It2++)
			{
				const IslandAndOffset* i = *It2;
				offset_islands.remove(i);
			}

			if(offset_islands.size() == 0)break;
			It = offset_islands.begin();
		}
	}

	CArea::m_processing_done += CArea::m_MakeOffsets_increment;
	if(CArea::m_processing_done > CArea::m_after_MakeOffsets_length)CArea::m_processing_done = CArea::m_after_MakeOffsets_length;

	std::list<CArea> separate_areas;
	smaller.Split(separate_areas);
	if(CArea::m_please_abort)return;
	for(std::list<CArea>::iterator It = separate_areas.begin(); It != separate_areas.end(); It++)
	{
		CArea& separate_area = *It;
		CCurve& first_curve = separate_area.m_curves.front();

		CurveTree* nearest_curve_tree = NULL;
		Point near_point = GetNearestPoint(this, islands_added, first_curve, &nearest_curve_tree);

		nearest_curve_tree->inners.push_back(new CurveTree(first_curve));

		for(std::list<const IslandAndOffset*>::iterator It = offset_islands.begin(); It != offset_islands.end();It++)
		{
			const IslandAndOffset* island_and_offset = *It;
			if(GetOverlapType(island_and_offset->offset, separate_area) == eInside)
				nearest_curve_tree->inners.back()->offset_islands.push_back(island_and_offset);
			if(CArea::m_please_abort)return;
		}

		nearest_curve_tree->inners.back()->point_on_parent = near_point;

		if(CArea::m_please_abort)return;
		Point first_curve_point = first_curve.NearestPoint(nearest_curve_tree->inners.back()->point_on_parent);
		if(CArea::m_please_abort)return;
		nearest_curve_tree->inners.back()->curve.ChangeStart(first_curve_point);
		if(CArea::m_please_abort)return;
		to_do_list_for_MakeOffsets.push_back(nearest_curve_tree->inners.back()); // do it later, in a while loop
		if(CArea::m_please_abort)return;
	}
}

void CurveTree::MakeOffsets()
{
	to_do_list_for_MakeOffsets.push_back(this);
	islands_added.clear();

	while(to_do_list_for_MakeOffsets.size() > 0)
	{
		CurveTree* curve_tree = to_do_list_for_MakeOffsets.front();
		to_do_list_for_MakeOffsets.pop_front();
		curve_tree->MakeOffsets2();
	}
}

void recur(std::list<CArea> &arealist, const CArea& a1, const CAreaPocketParams &params, int level)
{
	//if(level > 3)return;

    // this makes arealist by recursively offsetting a1 inwards
    
	if(a1.m_curves.size() == 0)
		return;
    
	if(params.from_center)
		arealist.push_front(a1);
	else
		arealist.push_back(a1);

    CArea a_offset = a1;
    a_offset.Offset(params.stepover);
    
    // split curves into new areas
	if(CArea::HolesLinked())
	{
		for(std::list<CCurve>::iterator It = a_offset.m_curves.begin(); It != a_offset.m_curves.end(); It++)
		{
            CArea a2;
			a2.m_curves.push_back(*It);
            recur(arealist, a2, params, level + 1);
		}
	}
    else
	{
        // split curves into new areas
		a_offset.Reorder();
        CArea* a2 = NULL;
       
		for(std::list<CCurve>::iterator It = a_offset.m_curves.begin(); It != a_offset.m_curves.end(); It++)
		{
			CCurve& curve = *It;
			if(curve.IsClockwise())
			{
				if(a2 != NULL)
					a2->m_curves.push_back(curve);
			}
			else
			{
				if(a2 != NULL)
					recur(arealist, *a2, params, level + 1);
				else
					a2 = new CArea();
                a2->m_curves.push_back(curve);
			}
		}

		if(a2 != NULL)
			recur(arealist, *a2, params, level + 1);
	}
}

static CArea make_obround(const Point& p0, const Point& p1, double radius)
{
    Point dir = p1 - p0;
    double d = dir.length();
    dir.normalize();
    Point right(dir.y, -dir.x);
    CArea obround;
    CCurve c;
	if(fabs(radius) < 0.0000001)radius = (radius > 0.0) ? 0.002 : (-0.002);
    Point vt0 = p0 + right * radius;
    Point vt1 = p1 + right * radius;
    Point vt2 = p1 - right * radius;
    Point vt3 = p0 - right * radius;
	c.append(vt0);
    c.append(vt1);
    c.append(CVertex(1, vt2, p1));
    c.append(vt3);
    c.append(CVertex(1, vt0, p0));
    obround.append(c);
    return obround;
}
    
static bool feed_possible(const CArea &area_for_feed_possible, const Point& p0, const Point& p1, double tool_radius)
{
    CArea obround = make_obround(p0, p1, tool_radius);
    obround.Subtract(area_for_feed_possible);
	return obround.m_curves.size() == 0;
}

void MarkOverlappingOffsetIslands(std::list<IslandAndOffset> &offset_islands)
{
	for(std::list<IslandAndOffset>::iterator It1 = offset_islands.begin(); It1 != offset_islands.end(); It1++)
	{
		std::list<IslandAndOffset>::iterator It2 = It1;
		It2++;
		for(;It2 != offset_islands.end(); It2++)
		{
			IslandAndOffset &o1 = *It1;
			IslandAndOffset &o2 = *It2;

			if(GetOverlapType(o1.offset, o2.offset) == eCrossing)
			{
				o1.touching_offsets.push_back(&o2);
				o2.touching_offsets.push_back(&o1);
			}
		}
	}
}

void CArea::MakeOnePocketCurve(std::list<CCurve> &curve_list, const CAreaPocketParams &params)const
{
	if(CArea::m_please_abort)return;
#if 0  // simple offsets with feed or rapid joins
	CArea area_for_feed_possible = *this;

	area_for_feed_possible.Offset(-params.tool_radius - 0.01);
	CArea a_offset = *this;

	std::list<CArea> arealist;
	recur(arealist, a_offset, params, 0);

	bool first = true;

	for(std::list<CArea>::iterator It = arealist.begin(); It != arealist.end(); It++)
	{
		CArea& area = *It;
		for(std::list<CCurve>::iterator It = area.m_curves.begin(); It != area.m_curves.end(); It++)
		{
			CCurve& curve = *It;
			if(!first)
			{
				// try to join these curves with a feed move, if possible and not too long
				CCurve &prev_curve = curve_list.back();
				const Point &prev_p = prev_curve.m_vertices.back().m_p;
				const Point &next_p = curve.m_vertices.front().m_p;

				if(feed_possible(area_for_feed_possible, prev_p, next_p, params.tool_radius))
				{
					// join curves
					prev_curve += curve;
				}
				else
				{
					curve_list.push_back(curve);
				}
			}
			else
			{
				curve_list.push_back(curve);
			}
			first = false;
		}
	}
#else
	pocket_params = &params;
	if(m_curves.size() == 0)
	{
		CArea::m_processing_done += CArea::m_single_area_processing_length;
		return;
	}
	CurveTree top_level(m_curves.front());

	std::list<IslandAndOffset> offset_islands;

	for(std::list<CCurve>::const_iterator It = m_curves.begin(); It != m_curves.end(); It++)
	{
		const CCurve& c = *It;
		if(It != m_curves.begin())
		{
			IslandAndOffset island_and_offset(&c);
			offset_islands.push_back(island_and_offset);
			top_level.offset_islands.push_back(&(offset_islands.back()));
			if(m_please_abort)return;
		}
	}

	MarkOverlappingOffsetIslands(offset_islands);

	CArea::m_processing_done += CArea::m_single_area_processing_length * 0.1;

	double MakeOffsets_processing_length = CArea::m_single_area_processing_length * 0.8;
	CArea::m_after_MakeOffsets_length = CArea::m_processing_done + MakeOffsets_processing_length;
	double guess_num_offsets = sqrt(GetArea(true)) * 0.5 / params.stepover;
	CArea::m_MakeOffsets_increment = MakeOffsets_processing_length / guess_num_offsets;

	top_level.MakeOffsets();
	if(CArea::m_please_abort)return;
	CArea::m_processing_done = CArea::m_after_MakeOffsets_length;

	curve_list.push_back(CCurve());
	CCurve& output = curve_list.back();

	GetCurveItem::to_do_list.push_back(GetCurveItem(&top_level, output.m_vertices.end()));

	while(GetCurveItem::to_do_list.size() > 0)
	{
		GetCurveItem item = GetCurveItem::to_do_list.front();
		item.GetCurve(output);
		GetCurveItem::to_do_list.pop_front();
	}

	// delete curve_trees non-recursively
	std::list<CurveTree*> CurveTreeDestructList;
	for(std::list<CurveTree*>::iterator It = top_level.inners.begin(); It != top_level.inners.end(); It++)
	{
		CurveTreeDestructList.push_back(*It);
	}
	while(CurveTreeDestructList.size() > 0)
	{
		CurveTree* curve_tree = CurveTreeDestructList.front();
		CurveTreeDestructList.pop_front();
		for(std::list<CurveTree*>::iterator It = curve_tree->inners.begin(); It != curve_tree->inners.end(); It++)
		{
			CurveTreeDestructList.push_back(*It);
		}
		delete curve_tree;
	}

	CArea::m_processing_done += CArea::m_single_area_processing_length * 0.1;
#endif
}