Skip to content

Instantly share code, notes, and snippets.

@zyf0330
Last active April 16, 2024 05:57
Show Gist options
  • Save zyf0330/41a043d56a0577ee711e1999fa3c4b2a to your computer and use it in GitHub Desktop.
Save zyf0330/41a043d56a0577ee711e1999fa3c4b2a to your computer and use it in GitHub Desktop.
给定直角边长,从左上角以逆时针螺旋路径,填充该等腰三角形内的每个整数坐标点
function fillTriangle(N) {
const lines = [];
function makeRound() {
let x = round - 1;
let y = round - 1;
let step = 1;
try {
(lines[y] ??= [])[x] = n;
canFinishFill();
while (++step <= N - (round - 1) * 3) {
y++;
n++;
(lines[y] ??= [])[x] = n;
canFinishFill();
}
step = 1;
while (++step <= N - (round - 1) * 3) {
x++;
y--;
n++;
(lines[y] ??= [])[x] = n;
canFinishFill();
}
step = 1;
while (++step <= N - (round - 1) * 3 - 1) {
x--;
n++;
(lines[y] ??= [])[x] = n;
canFinishFill();
}
y++;
n++;
return true;
} catch (e) {
return false;
}
}
function canFinishFill() {
// 几何解释:N * N / 2 + N / 2
// N 边长的正方形的面积(即内含点的个数)被剖成两半,即等腰直角三角形 N * N / 2,再加上正方形对角线上的点两个三角形一人一半 N / 2
if (n === (N * (N + 1)) / 2) {
throw new Error("finish");
}
}
let round = 1;
let n = 1;
while (makeRound()) {
round++;
}
for (const line of lines) {
console.log(
JSON.stringify(line, (k, v) =>
/* console.log(k,v, typeof v), */ typeof v === "number"
? " ".repeat(2 - v.toString().length) + v
: v,
),
);
}
}
fillTriangle(+process.argv[2]);
@zyf0330
Copy link
Author

zyf0330 commented Apr 10, 2024

这是基于距离的算法
基于坐标的算法就是把对 step 的条件判断改为 x, y 点是否到达顶点

根据坐标直接计算位置处数字的算法:

  1. 先用坐标相对三条边的距离,检测该坐标在哪条边上,同时算出是第几个内嵌三角形
  2. 根据内嵌度,计算该三角形的首尾数字范围,进而计算位置处数字

忽略重复代码片段之类的细节

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment