#include<iostream>
#include<cmath>
#include<vector>


using namespace std;

struct xy
{
	double xt;
	double yt;
};

struct xyR
{
	int xr;
	int yr;
};

//格点坐标表示(Bins)
struct xyzInt
{
	int xr;
	int yr;
	int zr;
};

//三维坐标表示(x,y,z) 单位 mm
struct xyzCoordinate
{
	double xc;
	double yc;
	double zc;
};



//二维验证
void xyReigon();
//三维验证
void xyzRegion(vector<xyzCoordinate>& track, xyzCoordinate startC, xyzCoordinate stopC, bool isOneRegion);

int main()
{
	//设二维线段的解析形式是 Ax + By + C = 0 起始点(x0,y0) 终点(x1,y1) 
	//格子区间为1*1（整数)
	/*
	对于二维区域来说，已知线段信息的情况下
	起点和终点的区域是已定的
	对于穿过的区域来说，与封闭区域的交点必有x或y是整数 计算出该点的坐标后 + 矢量的方向 ——> 得到区域信息

	对于三维区域来说，与封闭体积元必有某一面是有交点的，该交点的必有x或y或z是整数，计算出该点的坐标后 + 矢量的方向-->得到区域信息

	不重复的情况下 区域信息是该点坐标按矢量方向延展一个小的增量的点所在的区域为区域信息
	*/

	//二维验证

	//xyReigon();

	//三维验证

	//构建矢量链
	xyzCoordinate temp1;
	temp1.xc = 27.037571;
	temp1.yc = -5;
	temp1.zc = 2669.58;

	xyzCoordinate temp2;
	temp2.xc = -27.037571;
	temp2.yc = 5;
	temp2.zc = 2681.11;




	vector<xyzCoordinate> needDo;
	needDo.push_back(temp1);
	needDo.push_back(temp2);


	double delt = 0.01;
	double err = 1e-10;
	//构建新的矢量链 使之没有边界点 平行线段也可以处理
	for (int i = 0; i < needDo.size(); i++)
	{
		//判断有无边界点
		if (abs(int(needDo[i].xc) - needDo[i].xc) < err)
		{
			needDo[i].xc = needDo[i].xc + delt;
		}
		if (abs(int(needDo[i].yc) - needDo[i].yc) < err)
		{
			needDo[i].yc = needDo[i].yc + delt;
		}
		if (abs(int(needDo[i].zc) - needDo[i].zc) < err)
		{
			needDo[i].zc = needDo[i].zc + delt;
		}
	}

	//填入起始点
	vector<xyzCoordinate> track;
	track.push_back(temp1);
	bool isOneRegion = false;
	for (int i = 0; i < needDo.size()-1; i++)
	{
		//判断是否起始点和终点在同一区域
		if ((floor(needDo[i].xc) == floor(needDo[i + 1].xc)) && (floor(needDo[i].yc) == floor(needDo[i + 1].yc)) && (floor(needDo[i].zc) == floor(needDo[i + 1].zc)))
		{
			isOneRegion = true;
		}
		else
		{
			isOneRegion = false;
		}

		xyzRegion(track, needDo[i], needDo[i + 1], isOneRegion);

	}








	return 0;
}



//三维验证
void xyzRegion(vector<xyzCoordinate>& track, xyzCoordinate startC, xyzCoordinate stopC, bool isOneRegion)
{

	//1 默认会在矢量链第一个起点填充 所以 如果起始点和终点在同一个区域 那么就不需要填充 反之则只需要填充终点 而终点根据算法会自动进行填充
	if (isOneRegion == true)
		return;

	//2 如果起点和终点不在同一个区域
	//2.1 计算矢量方向

	/*
	//起始点坐标 和 终点坐标
	xyzCoordinate startC;
	xyzCoordinate stopC;

	startC.xc = -14.58253;
	startC.yc = 58.655225;
	startC.zc = 2655;

	stopC.xc = -14.81154;
	stopC.yc = 58.850528;
	stopC.zc = 2669.5811;
	*/
	//矢量方向
	//不允许平行
	double deltX = stopC.xc - startC.xc;
	double deltY = stopC.yc - startC.yc;
	double deltZ = stopC.zc - startC.zc;

	double lengthVector = sqrt(deltX * deltX + deltY * deltY + deltZ * deltZ);

	double directionX = deltX / lengthVector;
	double directionY = deltY / lengthVector;
	double directionZ = deltZ / lengthVector;

	int dirChangeX = 0;
	int dirChangeY = 0;
	int dirChangeZ = 0;

	if (directionX > 0)
		dirChangeX = 1;
	else if(directionX < 0)
		dirChangeX = -1;

	if (directionY > 0)
		dirChangeY = 1;
	else if (directionY < 0)
		dirChangeY = -1;

	if (directionZ > 0)
		dirChangeZ = 1;
	else if (directionZ < 0)
		dirChangeZ = -1;


	//输出信息
	cout << "startC: " << startC.xc << " " << startC.yc << " " << startC.zc << endl;
	cout << "stopC: " << stopC.xc << " " << stopC.yc << " " << stopC.zc << endl;
	cout << "deltX: " << deltX << endl;
	cout << "deltY: " << deltY << endl;
	cout << "deltZ: " << deltZ << endl;
	cout << "lengthVector: " << lengthVector << endl;
	cout << "directionX: " << directionX << " directionY: " << directionY << " directionZ: " << directionZ << endl;
	cout << "dirChangeX: " << dirChangeX << " dirChangeY: " << dirChangeY << " dirChangeZ: " << dirChangeZ << endl;


	//2.2 计算穿过的面->得到非起点所在的体积元的位置信息
	//获取两个起始和终点之间的信息 （只考虑穿过的点 即从起点开始穿过的体积元之间的面 ）
	//都是同类型的比较 所以不涉及变量提升 可以直接比较浮点数
	//X只允许Y Z不是格点的点 Y只允许X和Y是格点的点 Z允许所有点
	vector<xyzCoordinate> Lattice;

	//我们要求起始点和终末点必须处于某个体积元中 因此如果起始点和终末点处于体积元的边框上 则沿矢量方向添加一个小量
	//起始点和终末点不在体积元的边框上(函数前判断)
	double err = 1e-10;

	/*
	if (abs(int(startC.xc) - startC.xc) < err)
	{
		startC.xc = startC.xc + directionX * 0.1;
	}

	if (abs(int(startC.yc) - startC.yc) < err)
	{
		startC.yc = startC.yc + directionY * 0.1;
	}

	if (abs(int(startC.zc) - startC.zc) < err)
	{
		startC.zc = startC.zc + directionZ * 0.1;
	}

	if (abs(int(stopC.xc) - stopC.xc) < err)
	{
		stopC.xc = stopC.xc + directionX * 0.1;
	}

	if (abs(int(stopC.yc) - stopC.yc) < err)
	{
		stopC.yc = stopC.yc + directionY * 0.1;
	}

	if (abs(int(stopC.zc) - stopC.zc) < err)
	{
		stopC.zc = stopC.zc + directionZ * 0.1;
	}

	cout << "调整后" << endl;
	cout << "startC: " << startC.xc << " " << startC.yc << " " << startC.zc << endl;
	cout << "stopC: " << stopC.xc << " " << stopC.yc << " " << stopC.zc << endl;
	*/
	//计算X
	//取空间体积元为1cm*1cm*1cm
	int unit = 10; //10mm
	//X只允许Y Z不是格点的点 Y只允许X和Y是格点的点 Z允许所有点 避免重复计数
	//floor向负无穷取整
	//int直接舍小数取整

	int isOppositeSignX = 0;
	int isOppositeSignY = 0;
	int isOppositeSignZ = 0;

	if (startC.xc * stopC.xc < 0)
	{
		isOppositeSignX = 1;
	}

	if (startC.yc * stopC.yc < 0)
	{
		isOppositeSignY = 1;
	}

	if (startC.zc * stopC.zc < 0)
	{
		isOppositeSignZ = 1;
	}

	cout << int(int(stopC.yc / unit)) << endl;
	cout << int(startC.yc / unit) << endl;


	int timesX = abs(int(stopC.xc / unit) - int(startC.xc / unit) ) + isOppositeSignX;
	int timesY = abs(int(stopC.yc / unit) - int(startC.yc / unit) ) + isOppositeSignY;
	int timesZ = abs(int(stopC.zc / unit) - int(startC.zc / unit) ) + isOppositeSignZ;

	cout << "timesX: " << timesX << " timesY: " << timesY << " timesZ: " << timesZ << endl;

	double delt = 0.001;

	for (int i = 1; i <= timesX; i++)
	{
		double tempx;
		if (dirChangeX > 0)
			tempx = floor(startC.xc / unit + i) * unit;
		else
			tempx = ceil(startC.xc / unit - i) * unit;

		xyzCoordinate temp;
		temp.xc = tempx;
		temp.yc = startC.yc + (tempx - startC.xc) * directionY / directionX;
		temp.zc = startC.zc + (tempx - startC.xc) * directionZ / directionX;

		if ((abs(int(temp.yc) - temp.yc) > err) && (abs(int(temp.zc) - temp.zc) > err))
		{
			//微小的偏移 使其进入体积
			temp.xc = temp.xc + dirChangeX * delt;
			Lattice.push_back(temp);
		}

	}

	for (int i = 1; i <= timesY; i++)
	{
		double tempy;
		if (dirChangeY > 0)
			tempy = floor(startC.yc / unit + i) * unit;
		else
			tempy = ceil(startC.yc / unit - i) * unit;
		xyzCoordinate temp;
		temp.xc = startC.xc + (tempy - startC.yc) * directionX / directionY;
		temp.yc = tempy;
		temp.zc = startC.zc + (tempy - startC.yc) * directionZ / directionY;

		if (abs(int(temp.zc) - temp.zc) > err)
		{
			temp.yc = temp.yc + dirChangeY * delt;
			Lattice.push_back(temp);
		}

	}

	for (int i = 1; i <= timesZ; i++)
	{
		double tempz;
		if (dirChangeZ > 0)
			tempz = floor(startC.zc / unit + i) * unit;
		else
			tempz = ceil(startC.zc / unit - i) * unit;
		xyzCoordinate temp;
		temp.xc = startC.xc + (tempz - startC.zc) * directionX / directionZ;
		temp.yc = startC.yc + (tempz - startC.zc) * directionY / directionZ;
		temp.zc = tempz;
		temp.zc = temp.zc + dirChangeZ * delt;
		Lattice.push_back(temp);
	}

	//输出所有

	for (int i = 0; i < Lattice.size(); i++)
	{
		cout << "Lattice: " << Lattice[i].xc << " " << Lattice[i].yc << " " << Lattice[i].zc << endl;
	}



	//2.3 将结果输入track中返回
	for (int i = 0; i < Lattice.size(); i++)
	{
		track.push_back(Lattice[i]);
	}
	return;


	/*
	vector<xyzInt> xyzVolume;



	for (int i = 0; i < Lattice.size(); i++)
	{
		xyzInt tempI;
		tempI.xr = floor(Lattice[i].xc / unit);
		tempI.yr = floor(Lattice[i].yc / unit);
		tempI.zr = floor(Lattice[i].zc / unit);
		xyzVolume.push_back(tempI);
	}


	for (int i = 0; i < xyzVolume.size(); i++)
	{
		cout << "Volume: " << xyzVolume[i].xr << " " << xyzVolume[i].yr << " " << xyzVolume[i].zr << endl;
	}
	*/























	return;
}






























































//二维验证
void xyReigon()
{
	//A B C 均不为0
	//曲线 Ax + By + C = 0
	double A = 2.7;
	double B = 4.5;
	double C = -5;

	//起点
	double x0 = 0.5;
	double y0 = 0.81;
	//终点
	double x1 = 4.5;
	double y1 = -1.59;

	cout << "线段: " << A << "x + " << B << "y + " << C << " = 0" << endl;
	cout << "起点: (" << x0 << "," << y0 << ")" << endl;
	cout << "终点: (" << x1 << "," << y1 << ")" << endl;

	//区域格点这样定义 1.0*1.0的正方形区域
	//区域(m,n)表示 x取值[m,m+1) y取值[n,n+1)

	int DirectionX = 0;
	int DirectionY = 0;


	//第一步 求出矢量方向
	//x y的方向 如果x方向没有变化 就默认正方向 
	if (x1 >= x0)
		DirectionX = 1;
	else
		DirectionX = -1;

	if (y1 >= y0)
		DirectionY = 1;
	else
		DirectionY = -1;

	cout << "DirectionX: " << DirectionX << " DirectionY: " << DirectionY << endl;
	//由于只需要判断区域 所以不需要严格按照直线来进行 只需要按照方向方式就可以得到区域

	//第二步 求出所有交点
	vector<int> LatticeX;
	vector<int> LatticeY;

	//交点填充
	//LatticeX.push_back(floor(x0));
	//LatticeY.push_back(floor(y0));

	int lengthX = abs(floor(x1) - floor(x0));
	for (int i = 0; i <= lengthX; i++)
	{
		int tempX = floor(x0) + i * DirectionX;
		LatticeX.push_back(tempX);
	}

	int lengthY = abs(floor(y1) - floor(y0));
	for (int i = 0; i <= lengthY; i++)
	{
		int tempY = floor(y0) + i * DirectionY;
		LatticeY.push_back(tempY);
	}


	//输出交点
	/*
	for (int i = 0; i < LatticeX.size(); i++)
	{
		cout << " x: " << LatticeX[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < LatticeY.size(); i++)
	{
		cout << " y: " << LatticeY[i] << " ";
	}
	cout << endl;
	*/
	//对于(x,y)都在格点 存在重复计数 考虑到可能性低 所以暂时不予额外处理 默认不经过对角线s
	//计算交点坐标

	vector<xy> candidateXY;//交点
	vector<xyR> xyRe; //区域

	double delt = 0.3;

	double xtt, ytt;

	for (int i = 0; i < LatticeX.size(); i++)
	{
		xtt = LatticeX[i];

		if (((xtt < x1) && (xtt > x0)) || ((xtt < x0) && (xtt > x1)))
		{
			ytt = (-C - A * xtt) / B;

			xy xytt;
			xytt.xt = xtt;
			xytt.yt = ytt;

			candidateXY.push_back(xytt);

			xyR xyrtt;
			xyrtt.xr = floor(xtt + DirectionX * delt);
			xyrtt.yr = floor(ytt);
			xyRe.push_back(xyrtt);

		}

	}

	for (int i = 0; i < LatticeY.size(); i++)
	{
		ytt = LatticeY[i];
		if (((ytt < y1) && (ytt > y0)) || ((ytt < y0) && (ytt > y1)))
		{
			xtt = (-C - B * ytt) / A;

			xy xytt;
			xytt.xt = xtt;
			xytt.yt = ytt;

			candidateXY.push_back(xytt);

			xyR xyrtt;
			xyrtt.xr = floor(xtt);
			xyrtt.yr = floor(ytt + DirectionY * delt);
			xyRe.push_back(xyrtt);
		}
	}

	//输出交点
	for (int i = 0; i < candidateXY.size(); i++)
	{
		cout << " (" << candidateXY[i].xt << "," << candidateXY[i].yt << ") ";
	}
	cout << endl;
	cout << "区域 ";
	for (int i = 0; i < xyRe.size(); i++)
	{
		cout << " (" << xyRe[i].xr << "," << xyRe[i].yr << ") ";
	}
	return;
}