根据要求，看起来有个简单的解决方案。
首先，将三角形边缘光栅化。你可以使用 Bresenham 的线段绘制算法（如下面的代码所示）或任何有效的方法。然后填充区域间的空白部分。这适用于任意薄的三角形。
为了确保不管以什么顺序绘制三角形和提供给光栅化共享边界的顶点顺序是什么，都没有间隙，你需要在共享边缘的三角形中以相同的方式对共享边界进行光栅化。 "相同的方式" 意味着每次都使用相同的像素点。
为了保证每次从相同的顶点坐标对获取相同的像素点，你基本上需要建立一个固定的顺序，即建立一条规则，无论以何种顺序给出两个顶点，它总是选择相同的顶点之一。
强制执行此顺序的一种简单方法是将你的线段（三角形边缘）视为 2-d 矢量，并在其指向负 y 方向或平行于 x 轴且指向负 x 方向时翻转其方向。是时候画一些 ASCII 艺术啦！ :)
3 2 1
\ | /
\ | /
\|/
4 --------+--------- 0
/|\
/ | \
/ | \
5 6 7
4 -> 0
5 -> 1
6 -> 2
7 -> 3
看，这里的线段1和线段5实际上是同一种东西，唯一的区别是从起点到另一个端点的方向。因此，我们通过将段4到7转化为段0到3并消除方向歧义来将这些情况减少了一半。也就是说，我们选择朝着y值增加的方向走，或者如果边缘上的y值相同，则选择朝着x值增加的方向走。
以下是如何在代码中实现此功能：
#include <stddef.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define SCREEN_HEIGHT 22
#define SCREEN_WIDTH 78
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH];
void SetPixel(long x, long y, char color)
{
if ((x < 0) || (x >= SCREEN_WIDTH) ||
(y < 0) || (y >= SCREEN_HEIGHT))
{
return;
}
if (Screen[y][x] == ' ')
Screen[y][x] = color;
else
Screen[y][x] = '*';
}
void Visualize(void)
{
long x, y;
for (y = 0; y < SCREEN_HEIGHT; y++)
{
for (x = 0; x < SCREEN_WIDTH; x++)
{
printf("%c", Screen[y][x]);
}
printf("\n");
}
}
typedef struct
{
long x, y;
unsigned char color;
} Point2D;
long ContourX[SCREEN_HEIGHT][2];
#define ABS(x) ((x >= 0) ? x : -x)
void ScanLine(long x1, long y1, long x2, long y2)
{
long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt;
sx = x2 - x1;
sy = y2 - y1;
if (sy < 0 || sy == 0 && sx < 0)
{
k = x1; x1 = x2; x2 = k;
k = y1; y1 = y2; y2 = k;
sx = -sx;
sy = -sy;
}
if (sx > 0) dx1 = 1;
else if (sx < 0) dx1 = -1;
else dx1 = 0;
if (sy > 0) dy1 = 1;
else if (sy < 0) dy1 = -1;
else dy1 = 0;
m = ABS(sx);
n = ABS(sy);
dx2 = dx1;
dy2 = 0;
if (m < n)
{
m = ABS(sy);
n = ABS(sx);
dx2 = 0;
dy2 = dy1;
}
x = x1; y = y1;
cnt = m + 1;
k = n / 2;
while (cnt--)
{
if ((y >= 0) && (y < SCREEN_HEIGHT))
{
if (x < ContourX[y][0]) ContourX[y][0] = x;
if (x > ContourX[y][1]) ContourX[y][1] = x;
}
k += n;
if (k < m)
{
x += dx2;
y += dy2;
}
else
{
k -= m;
x += dx1;
y += dy1;
}
}
}
void DrawTriangle(Point2D p0, Point2D p1, Point2D p2)
{
long y;
for (y = 0; y < SCREEN_HEIGHT; y++)
{
ContourX[y][0] = LONG_MAX;
ContourX[y][1] = LONG_MIN;
}
ScanLine(p0.x, p0.y, p1.x, p1.y);
ScanLine(p1.x, p1.y, p2.x, p2.y);
ScanLine(p2.x, p2.y, p0.x, p0.y);
for (y = 0; y < SCREEN_HEIGHT; y++)
{
if (ContourX[y][1] >= ContourX[y][0])
{
long x = ContourX[y][0];
long len = 1 + ContourX[y][1] - ContourX[y][0];
while (len--)
{
SetPixel(x++, y, p0.color);
}
}
}
}
int main(void)
{
Point2D p0, p1, p2, p3;
memset(Screen, ' ', sizeof(Screen));
srand((unsigned)time(NULL));
for (;;)
{
p0.x = rand() % SCREEN_WIDTH;
p0.y = rand() % SCREEN_HEIGHT;
p1.x = rand() % SCREEN_WIDTH;
p1.y = rand() % SCREEN_HEIGHT;
p2.x = rand() % SCREEN_WIDTH;
p2.y = rand() % SCREEN_HEIGHT;
p3.x = rand() % SCREEN_WIDTH;
p3.y = rand() % SCREEN_HEIGHT;
{
long vsx = p0.x - p1.x;
long vsy = p0.y - p1.y;
long v1x = p0.x - p2.x;
long v1y = p0.y - p2.y;
long v2x = p0.x - p3.x;
long v2y = p0.y - p3.y;
long z1 = vsx * v1y - v1x * vsy;
long z2 = vsx * v2y - v2x * vsy;
if (z1 * z2 < 0) break;
}
}
printf("%ld:%ld %ld:%ld %ld:%ld %ld:%ld\n\n",
p0.x, p0.y,
p1.x, p1.y,
p2.x, p2.y,
p3.x, p3.y);
p0.color = '-';
DrawTriangle(p0, p3, p1);
p1.color = '+';
DrawTriangle(p1, p2, p0);
Visualize();
return 0;
}
示例输出：
30:10 5:16 16:6 59:17
+++
++++++++
++++++++++++
+++++++++++++++++
+++++++++++++++****---
+++++++++++++****-----------
++++++++++****-------------------
++++++*****----------------------------
+++****-------------------------------------
****---------------------------------------------
*-----------------------------------------------------
-
说明：
- "+" - 三角形1的像素
- "-" - 三角形2的像素
- "*" - 三角形1和2之间共享的边缘像素
请注意，即使没有未填充的间隙（像素），由于另一个在其上方绘制的三角形覆盖了共享边缘上的像素，因此可能会出现显示为不连续或形状尴尬的三角形，如果它太薄。例如：
2:20 12:8 59:15 4:17
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
