以整数点坐标与绕原点转数表示角度的类,支持角度排序与旋转扫描(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,以统计正向三角形等。