矢量線的一種柵格化算法

1. 概述

1.1. 已知算法

將一條線段柵格化的最簡單的算法思路是根據其斜率,按X或Y方向步進取值:

線的柵格化
線的柵格化

除此之外還有一種算法是利用計算機圖形學中繪制直線的Bresenham算法,這種算法的效率很高,原理就是用遍歷的辦法規避乘法和除法,只用加減法就能完成線段的柵格化。

1.2. 本文算法

上述兩種算法有個問題就是都要經過一系列繁復的判斷,才能得到比較嚴密的結果,所以我并沒有采用。我這里采用的算法也是逐漸步進求值的辦法,只不過不再沿著X或者Y方向求值,而是沿著射線方向步進。這里的射線指的是從線段的起點開始,以1像素為步進單位,步進到線段的終點。因為線段的方向性問題,步進得到的點總會有重復的值,最后再進行去重操作即可。

算法過程簡述如下:

  1. 設線段的起點為\(O\),終點為\(E\),則方向向量為\(D=E-O\);
  2. 線段的長度L為向量\(D\)的模。以0為初值,L為終值,以1為步進值建立一個for循環,每次取的長度為d;
  3. \(t=d/L\),則線段上相應的點為\(P=O+tD\)。這個公式是根據射線向量方程推導出來的,可以參看這篇文章《已知線段上某點與起點的距離,求該點的坐標》;
  4. 將取的點都保存到容器中;
  5. 對容器中的點進行去重操作。

最終得到的點即為直線柵格化后的點。

2. 實現

具體的C++實現代碼如下:

#include <iostream>
#include <vector>

using namespace std;

const double EPSILON = 0.000001;

// 2D Point
struct Vector2d
{
public:
	Vector2d()
	{
	}

	Vector2d(double dx, double dy)
	{
		x = dx;
		y = dy;
	}

	// 矢量賦值
	void set(double dx, double dy)
	{
		x = dx;
		y = dy;
	}

	// 矢量相加
	Vector2d operator + (const Vector2d& v) const
	{
		return Vector2d(x + v.x, y + v.y);
	}

	// 矢量相減
	Vector2d operator - (const Vector2d& v) const
	{
		return Vector2d(x - v.x, y - v.y);
	}

	//矢量數乘
	Vector2d Scalar(double c) const
	{
		return Vector2d(c*x, c*y);
	}

	// 矢量點積
	double Dot(const Vector2d& v) const
	{
		return x * v.x + y * v.y;
	}

	//向量的模
	double Mod() const
	{
		return sqrt(x * x + y * y);
	}

	bool Equel(const Vector2d& v) const
	{
		if (abs(x - v.x) < EPSILON && abs(y - v.y) < EPSILON)
		{
			return true;
		}
		return false;
	}

	double x, y;
};

//柵格化一條線段
void RasterLine(std::pair<Vector2d, Vector2d> line, std::vector<Vector2d>& linePointList)
{
	Vector2d vecLine = line.second - line.first;
	double lineLength = vecLine.Mod();
	double step = 1.0;

	//根據距離逐步取
	vector<Vector2d> tmpPointList;
	double curLength = 0;
	while (curLength < lineLength)
	{
		curLength = curLength + step;
		Vector2d P = line.first + vecLine.Scalar(curLength / lineLength);
		P.x = (int)(P.x + 0.5);
		P.y = (int)(P.y + 0.5);
		tmpPointList.push_back(P);
	}

	//與最后一個值比較,去重
	linePointList.push_back(line.first);
	for (size_t i = 0; i < tmpPointList.size(); i++)
	{
		//與最后一個值比較,去重
		if (!tmpPointList[i].Equel(linePointList[linePointList.size() - 1]))
		{
			linePointList.push_back(tmpPointList[i]);
		}
	}

	if (!linePointList[linePointList.size() - 1].Equel(line.second))
	{
		linePointList.push_back(line.second);
	}
}


int main()
{
	Vector2d O(30, 60);
	Vector2d E(88, 104);
	std::pair<Vector2d, Vector2d> line(O, E);

	vector<Vector2d> linePointList;
	RasterLine(line, linePointList);

	for (size_t i = 0; i < linePointList.size(); i++)
	{
		cout << linePointList[i].x << ',' << linePointList[i].y << '\t';
	}
}

其運行的結果如下:

線的柵格化

3. 參考

[1].矢量數據柵格化
[2].Bresenham算法

posted @ 2020-03-04 21:20  charlee44  閱讀(...)  評論(...編輯  收藏
ag二分彩