针对每个存活细胞,创建相邻存活细胞的位掩码。例如,使用值为1、2、4和8的位表示北、东、南和西。您将得到一组16个平铺:
![Sixteen tiles](https://istack.dev59.com/QGfDV.webp)
如果你只想显示带有圆形轮廓的单元格,可以快速复制相应的平铺到画布或位图窗口中。这应该是相当快的,因为平铺已经被渲染了。
如果你真的需要轮廓作为曲线,请为每个平铺创建深红色线条的曲线。请注意,平铺0101和1010由两条曲线组成,平铺1111没有曲线,平铺0000是一个闭合曲线。
将当前单元格的曲线段偏移量移动到列表中。所有曲线(除了0000)都有松散的端点;这些端点总是在单元格边界交叉处。
现在你可以创建路径。创建一个查找表,可能是哈希表,包含所有端点。每个端点应该有两个相连的曲线段。现在从列表中选择一个曲线段。它的起点是曲线的起点。现在查找段的终点并进入下一个段。删除访问过的段并将它们添加到路径中。继续直到达到曲线的起点。将曲线添加到列表中。只要列表中仍有曲线段,就重复此过程。
您可能需要将没有邻居(0000)的单元格直接放入最终曲线列表中。您还必须将0101和1010单元格的两条线段视为单独的线段。
编辑:我已经在C语言中拼凑出了一个概念验证示例,它接受随机生成的细胞网格,并创建平滑渲染的PostScript文件。
命名不太一致,我很抱歉,但基本上有四种线段类型:闭合圆、尖峰(或鼻子)、四分之一圆弧和直壁。这些以顺时针方向渲染,因此封闭形状始终在曲线的右侧。
PS渲染中的
stype
路径字段由四分之一圆弧(
NE
、
SE
、
SW
、
NW
)、单元格大小的直线(
N1
,
E1
,
S1
,
W1
)和半个单元格大小的直线(
N2
,
E2
,
S2
,
W2
)组成。当然,您可以将它们呈现为直线序列和三次贝塞尔曲线,而不是使用PS命令。
每个段还存储单元格起始和结束角的位置,包括
NE
、
SE
、
SW
和
NW
枚举。
除单元格外,还有一个段列表和一个角网格,用于存储哪些段连接到一个角。一个角只能有没有或两个相连的段。
此示例在编译时具有固定的大小,以使C程序员的生活更轻松。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define N 24
#define die(...) exit((fprintf(stderr, __VA_ARGS__), 1))
enum {NW, NE, SE, SW, NCORNER};
static const int dx[NCORNER] = {0, 1, 1, 0};
static const int dy[NCORNER] = {0, 0, 1, 1};
struct stype {
const char *name;
int start;
int end;
const char *path;
};
#define STYPE(X) \
X(None, -1, -1, "") \
X(WallN, NW, NE, "E1") \
X(WallE, NE, SE, "S1") \
X(WallS, SE, SW, "W1") \
X(WallW, SW, NW, "N1") \
X(QuarterNE, SE, NW, "W2 SW N2") \
X(QuarterSE, SW, NE, "N2 NW E2") \
X(QuarterSW, NW, SE, "E2 NE S2") \
X(QuarterNW, NE, SW, "S2 SE W2") \
X(SpikeN, NE, NW, "S2 SE SW N2") \
X(SpikeE, SE, NE, "W2 SW NW E2") \
X(SpikeS, SW, SE, "N2 NW NE S2") \
X(SpikeW, NW, SW, "E2 NE SE W2") \
X(Circle, NW, NW, "MM")
#define STYPE_STRUCT(Name, S1, S2, P) {#Name, S1, S2, P},
#define STYPE_ENUM(Name, S1, S2, P) Name,
enum {STYPE(STYPE_ENUM) MAX_STYPE};
static const struct stype stype[MAX_STYPE] = { STYPE(STYPE_STRUCT)};
int ctype[16][3] = {
{Circle, None},
{SpikeN, None},
{SpikeE, None},
{QuarterNE, None},
{SpikeS, None},
{WallW, WallE, None},
{QuarterSE, None},
{WallW, None},
{SpikeW, None},
{QuarterNW, None},
{WallN, WallS, None},
{WallS, None},
{QuarterSW, None},
{WallE, None},
{WallN, None},
{ None},
};
struct seg {
int type;
int x;
int y;
};
struct pt {
int seg1;
int seg2;
};
int alive(int cell[N][N], int x, int y)
{
if (x < 0 || x >= N) return 0;
if (y < 0 || y >= N) return 0;
return cell[y][x];
}
void addpt(struct pt *pt, int seg)
{
if (pt->seg1 < 0) {
pt->seg1 = seg;
} else if (pt->seg2 < 0) {
pt->seg2 = seg;
} else {
die("Too many segments for point.\n");
}
}
int main(void)
{
int cell[N][N];
int count = 0;
int i, x, y;
for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
int r = 1 + abs(N/2 - x) + abs(N/2 - y);
cell[y][x] = (rand() / 4 < RAND_MAX / r);
if (cell[y][x]) count++;
}
}
struct seg seg[2 * count];
int nseg = 0;
for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
int ix = 0;
if (cell[y][x] == 0) continue;
if (alive(cell, x, y - 1)) ix |= 1;
if (alive(cell, x + 1, y)) ix |= 2;
if (alive(cell, x, y + 1)) ix |= 4;
if (alive(cell, x - 1, y)) ix |= 8;
int *p = ctype[ix];
while (*p != None) {
if (nseg >= 2 * count) die("Segment overflow\n");
seg[nseg].x = x;
seg[nseg].y = y;
seg[nseg].type = *p++;
nseg++;
}
}
}
struct pt pt[N + 1][N + 1];
memset(pt, -1, sizeof(pt));
for (i = 0; i < nseg; i++) {
int tp = seg[i].type;
int s = stype[tp].start;
int e = stype[tp].end;
x = seg[i].x;
y = seg[i].y;
addpt(&pt[y + dy[s]][x + dx[s]], i);
addpt(&pt[y + dy[e]][x + dx[e]], i);
}
puts("%!PS-Adobe 3.0");
puts("/A 10 def");
puts("/A2 A 2 mul def");
puts("/C { rcurveto } def");
puts("/L { rlineto } def");
puts("/START { newpath exch A2 mul exch A2 mul moveto } bind def");
puts("/END { closepath stroke } bind def");
puts("/MM { A 0 rmoveto NE SE SW NW } bind def");
puts("/NW { 0 A neg 0 A neg A A neg C } bind def");
puts("/NE { A 0 A 0 A A C } bind def");
puts("/SE { 0 A 0 A A neg A C } bind def");
puts("/SW { A neg 0 A neg 0 A neg A neg C } bind def");
puts("/N1 { 0 A2 neg L } bind def");
puts("/E1 { A2 0 L } bind def");
puts("/S1 { 0 A2 L } bind def");
puts("/W1 { A2 neg 0 L } bind def");
puts("/N2 { 0 A neg L } bind def");
puts("/E2 { A 0 L } bind def");
puts("/S2 { 0 A L } bind def");
puts("/W2 { A neg 0 L } bind def");
puts("57 180 translate");
for (i = 0; i < nseg; i++) {
struct seg *s = seg + i;
if (s->type == None) continue;
int x0 = s->x + dx[stype[s->type].start];
int y0 = s->y + dy[stype[s->type].start];
int j = i;
x = s->x + dx[stype[s->type].end];
y = s->y + dy[stype[s->type].end];
printf("%d %d START", x0, y0);
for (;;) {
printf(" %s", stype[s->type].path);
s->type = None;
if (x == x0 && y == y0) break;
if (pt[y][x].seg1 == j) {
j = pt[y][x].seg2;
} else {
j = pt[y][x].seg1;
}
s = seg + j;
x = s->x + dx[stype[s->type].end];
y = s->y + dy[stype[s->type].end];
}
puts(" END");
}
puts("showpage");
return 0;
}