以整数点坐标与绕原点转数表示角度的类,支持角度排序与旋转扫描(rotational sweeping),也可代表点或向量。

Description: A class for ordering angles (as represented by int points and a number of rotations around the origin). Useful for rotational sweeping. Sometimes also represents points or vectors. Usage: vector v = {w[0], w[0].t360() …}; // sorted int j = 0; rep(i,0,n) { while (v[j] < v[i].t180()) ++j; }

  • 结构与字段(据实现)

    • Angle {int x, y, t;}:(x,y) 为笛卡尔坐标,t 为绕原点的完整旋转次数。
    • operator-:向量差。
  • 半平面与旋转

    • half():判断点在”下半平面”(y<0 或 y==0且x<0),用于角度排序分半;断言 (x,y) 非零点。
    • t90/t180/t360:分别表示旋转90°/180°/360°后的新角度;t180 = {-x,-y, t+half()},t360 = {x,y, t+1}。
  • 排序与比较

    • operator<:按三元组 (t, half(), yb.x) 与 (t, half(), xb.y) 字典序比较,实现极角排序;注释提示可加 dist2() 以同时比较距离。
  • 辅助操作

    • segmentAngles(a,b):计算覆盖线段的”最小角区间”(若 b<a 则交换,再判定是否跨越180°分界)。
    • operator+(a, b):将点 a 与向量 b 相加,并根据是否跨越180°调整 t。
    • angleDiff(a, b):计算”角 b - 角 a”,返回新 Angle,内部按旋转公式与 t 差值处理。
  • 典型用法(Usage 示例)

    • 对点集构建 Angle 数组(含多圈副本如 w[i].t360())并排序;
    • 双指针扫描:while (v[j] < v[i].t180()) ++j,以统计正向三角形等。

关联节点