在多边形裁剪算法中，计算两条边的交点需要进行乘法运算。当使用 64 位整数坐标时，两个 64 位整数相乘可能产生 128 位的中间结果。为了避免溢出并保持精度，Clipper1 实现了一个自定义的 128 位整数结构 Int128。
考虑计算两条边是否共线的判断：
// 判断三点是否共线
// 使用叉积：(pt1-pt2) × (pt2-pt3) = 0
// 展开：(pt1.Y - pt2.Y) * (pt2.X - pt3.X) == (pt1.X - pt2.X) * (pt2.Y - pt3.Y)
// 假设坐标范围接近 Int64.MaxValue
long a = 4611686018427387903L; // 接近 loRange
long b = 4611686018427387902L;
long c = a * b; // 溢出！
| 坐标范围 | 乘积范围 | 是否溢出 |
|---|---|---|
| ≤ 46,340 (Int32 安全范围) | ≤ 2.1×10⁹ | 否（Int64 可容纳） |
| ≤ 10⁹ (loRange) | ≤ 10¹⁸ | 否（Int64 可容纳） |
| ≤ 10¹⁸ (hiRange) | ≤ 10³⁶ | 是（需要 Int128） |
internal struct Int128
{
private Int64 hi; // 高 64 位（有符号）
private UInt64 lo; // 低 64 位（无符号）
public Int128(Int64 _lo)
{
lo = (UInt64)_lo;
if (_lo < 0) hi = -1; // 符号扩展
else hi = 0;
}
public Int128(Int64 _hi, UInt64 _lo)
{
lo = _lo;
hi = _hi;
}
public Int128(Int128 val)
{
hi = val.hi;
lo = val.lo;
}
}
Int128 结构（16 字节）：
┌────────────────────────────────────────────────────────────────┐
│ hi (Int64) │
│ 符号位 │ 高63位数值 │
├────────────────────────────────────────────────────────────────┤
│ lo (UInt64) │
│ 低64位数值 │
└────────────────────────────────────────────────────────────────┘
总范围：-2¹²⁷ 到 2¹²⁷-1
从 Int64 构造 Int128 时，需要正确处理负数：
public Int128(Int64 _lo)
{
lo = (UInt64)_lo;
if (_lo < 0)
hi = -1; // 全1（0xFFFFFFFFFFFFFFFF），表示负数扩展
else
hi = 0; // 全0，表示正数
}
示例：
Int64 值: -1 = 0xFFFFFFFFFFFFFFFF
Int128 表示: hi = 0xFFFFFFFFFFFFFFFF, lo = 0xFFFFFFFFFFFFFFFF
= -1 (128位)
Int64 值: 100
Int128 表示: hi = 0x0000000000000000, lo = 0x0000000000000064
= 100 (128位)
public bool IsNegative()
{
return hi < 0;
}
原理：128 位有符号整数的最高位（hi 的符号位）决定整体符号。
public static bool operator ==(Int128 val1, Int128 val2)
{
if ((object)val1 == (object)val2) return true;
else if ((object)val1 == null || (object)val2 == null) return false;
return (val1.hi == val2.hi && val1.lo == val2.lo);
}
public static bool operator !=(Int128 val1, Int128 val2)
{
return !(val1 == val2);
}
public override bool Equals(System.Object obj)
{
if (obj == null || !(obj is Int128))
return false;
Int128 i128 = (Int128)obj;
return (i128.hi == hi && i128.lo == lo);
}
public override int GetHashCode()
{
return hi.GetHashCode() ^ lo.GetHashCode();
}
public static bool operator >(Int128 val1, Int128 val2)
{
if (val1.hi != val2.hi)
return val1.hi > val2.hi; // 先比较高位
else
return val1.lo > val2.lo; // 高位相同则比较低位
}
public static bool operator <(Int128 val1, Int128 val2)
{
if (val1.hi != val2.hi)
return val1.hi < val2.hi;
else
return val1.lo < val2.lo;
}
比较逻辑：
hi（有符号比较）
lo（无符号比较）
示例：
A = (hi=0, lo=100) // = 100
B = (hi=0, lo=200) // = 200
A < B 因为 hi 相同，100 < 200
C = (hi=-1, lo=max) // = -1
D = (hi=0, lo=1) // = 1
C < D 因为 -1 < 0
public static Int128 operator +(Int128 lhs, Int128 rhs)
{
lhs.hi += rhs.hi;
lhs.lo += rhs.lo;
if (lhs.lo < rhs.lo) lhs.hi++; // 处理低位进位
return lhs;
}
lhs.lo = 0xFFFFFFFFFFFFFFFF (最大无符号64位)
+ rhs.lo = 0x0000000000000001
─────────────────────────────
结果.lo = 0x0000000000000000 (溢出，产生进位)
检测方法：如果 lhs.lo < rhs.lo，说明发生了溢出
需要将 hi 加 1 来处理进位
// 大数加法
Int128 a = new Int128(0, 0xFFFFFFFFFFFFFFFF); // 2^64 - 1
Int128 b = new Int128(0, 1); // 1
Int128 c = a + b; // c.hi = 1, c.lo = 0 // = 2^64
public static Int128 operator -(Int128 val)
{
if (val.lo == 0)
return new Int128(-val.hi, 0);
else
return new Int128(~val.hi, ~val.lo + 1);
}
对于补码表示的整数，取负操作等价于"按位取反后加1"：
原值: val = (hi, lo)
取反: ~val = (~hi, ~lo)
加1: -val = (~hi, ~lo + 1)
特殊情况：当 lo = 0 时
- ~lo + 1 会产生溢出，变回 0
- 需要向 hi 进位
- 简化为 (-hi, 0)
// 正数取负
Int128 pos = new Int128(0, 100); // = 100
Int128 neg = -pos; // = -100
// neg.hi = ~0 = -1, neg.lo = ~100 + 1 = -100（作为无符号数）
// lo = 0 的特殊情况
Int128 a = new Int128(5, 0); // = 5 * 2^64
Int128 b = -a; // = -5 * 2^64
// b.hi = -5, b.lo = 0
public static Int128 operator -(Int128 lhs, Int128 rhs)
{
return lhs + -rhs;
}
减法通过取负后加法实现，简化了代码。
public static explicit operator double(Int128 val)
{
const double shift64 = 18446744073709551616.0; // 2^64
if (val.hi < 0)
{
if (val.lo == 0)
return (double)val.hi * shift64;
else
return -(double)(~val.lo + ~val.hi * shift64);
}
else
return (double)(val.lo + val.hi * shift64);
}
128 位整数可以表示为：value = hi * 2^64 + lo
// 正数转换
double result = (double)lo + (double)hi * (2^64);
// 负数转换
// 需要先计算绝对值，再取负
// |val| = ~val + 1 = ~lo + 1 + ~hi * 2^64
// 简化：|val| ≈ ~lo + ~hi * 2^64（忽略+1的精度影响）
double result = -((double)(~lo) + (double)(~hi) * (2^64));
double 只有 53 位有效数字，无法精确表示所有 128 位整数值。这个转换主要用于：
这是 Int128 最重要的方法，用于计算两个 64 位整数的 128 位乘积：
public static Int128 Int128Mul(Int64 lhs, Int64 rhs)
{
// 处理符号
bool negate = (lhs < 0) != (rhs < 0);
if (lhs < 0) lhs = -lhs;
if (rhs < 0) rhs = -rhs;
// 将 64 位分解为两个 32 位部分
UInt64 int1Hi = (UInt64)lhs >> 32;
UInt64 int1Lo = (UInt64)lhs & 0xFFFFFFFF;
UInt64 int2Hi = (UInt64)rhs >> 32;
UInt64 int2Lo = (UInt64)rhs & 0xFFFFFFFF;
// 计算四个部分乘积
UInt64 a = int1Hi * int2Hi;
UInt64 b = int1Lo * int2Lo;
UInt64 c = int1Hi * int2Lo + int1Lo * int2Hi;
// 组合结果
UInt64 lo;
Int64 hi;
hi = (Int64)(a + (c >> 32));
unchecked { lo = (c << 32) + b; }
if (lo < b) hi++;
Int128 result = new Int128(hi, lo);
return negate ? -result : result;
}
将 64 位整数分解为高低 32 位后，乘法可以表示为：
int1Hi int1Lo
× int2Hi int2Lo
─────────────────────
b = int1Lo × int2Lo (0-64位)
c1 = int1Hi × int2Lo (32-96位)
c2 = int1Lo × int2Hi (32-96位)
a = int1Hi × int2Hi (64-128位)
─────────────────────
最终 128 位结果
位置分布：
|----a----|----c----|----b----|
96-128 32-96 0-64
(c需要分拆到高位和低位)
步骤1：符号处理
bool negate = (lhs < 0) != (rhs < 0); // 异或判断结果符号
if (lhs < 0) lhs = -lhs; // 转为正数计算
if (rhs < 0) rhs = -rhs;
步骤2：分解为 32 位
UInt64 int1Hi = (UInt64)lhs >> 32; // 高32位
UInt64 int1Lo = (UInt64)lhs & 0xFFFFFFFF; // 低32位
步骤3：计算部分乘积
UInt64 a = int1Hi * int2Hi; // 高×高，结果在位置 64-128
UInt64 b = int1Lo * int2Lo; // 低×低，结果在位置 0-64
UInt64 c = int1Hi * int2Lo + int1Lo * int2Hi; // 交叉项，位置 32-96
步骤4：组合结果
// hi 包含：a（完整）+ c的高32位
hi = (Int64)(a + (c >> 32));
// lo 包含：b（完整）+ c的低32位（左移32位后）
unchecked { lo = (c << 32) + b; }
// 处理低位加法的进位
if (lo < b) hi++;
源代码注释解释了这一点：
//nb: Constructing two new Int128 objects every time we want to multiply longs
//is slow. So, although calling the Int128Mul method doesn't look as clean, the
//code runs significantly faster than if we'd used the * operator.
即：每次乘法都创建两个 Int128 对象会很慢，直接使用静态方法更高效。
internal static bool SlopesEqual(TEdge e1, TEdge e2, bool UseFullRange)
{
if (UseFullRange)
return Int128.Int128Mul(e1.Delta.Y, e2.Delta.X) ==
Int128.Int128Mul(e1.Delta.X, e2.Delta.Y);
else
return (cInt)(e1.Delta.Y) * (e2.Delta.X) ==
(cInt)(e1.Delta.X) * (e2.Delta.Y);
}
internal bool PointOnLineSegment(IntPoint pt,
IntPoint linePt1, IntPoint linePt2, bool UseFullRange)
{
if (UseFullRange)
// 使用 Int128 进行精确计算
return /* ... */ &&
((Int128.Int128Mul((pt.X - linePt1.X), (linePt2.Y - linePt1.Y)) ==
Int128.Int128Mul((linePt2.X - linePt1.X), (pt.Y - linePt1.Y))));
else
// 使用普通 64 位计算
return /* ... */ &&
((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) ==
(linePt2.X - linePt1.X) * (pt.Y - linePt1.Y));
}
void RangeTest(IntPoint Pt, ref bool useFullRange)
{
if (useFullRange)
{
if (Pt.X > hiRange || Pt.Y > hiRange ||
-Pt.X > hiRange || -Pt.Y > hiRange)
throw new ClipperException("Coordinate outside allowed range");
}
else if (Pt.X > loRange || Pt.Y > loRange ||
-Pt.X > loRange || -Pt.Y > loRange)
{
useFullRange = true; // 自动升级到高精度模式
RangeTest(Pt, ref useFullRange);
}
}
| 条件 | 使用类型 | 性能 |
|---|---|---|
| 坐标 ≤ loRange | Int64 | 快 |
| 坐标 > loRange 且 ≤ hiRange | Int128 | 较慢（约2-3倍） |
| 坐标 > hiRange | 异常 | N/A |
// 检查是否需要高精度
bool NeedsHighPrecision(Paths paths)
{
foreach (var path in paths)
foreach (var pt in path)
if (Math.Abs(pt.X) > ClipperBase.loRange ||
Math.Abs(pt.Y) > ClipperBase.loRange)
return true;
return false;
}
// 坐标缩放以避免高精度
double scale = 1.0;
if (NeedsHighPrecision(paths))
{
// 找到最大坐标
long maxCoord = 0;
foreach (var path in paths)
foreach (var pt in path)
{
maxCoord = Math.Max(maxCoord, Math.Abs(pt.X));
maxCoord = Math.Max(maxCoord, Math.Abs(pt.Y));
}
// 计算缩放因子
scale = (double)ClipperBase.loRange / maxCoord;
// 应用缩放
ScalePaths(paths, scale);
}
本章详细分析了 Clipper1 的 Int128 高精度整数实现：
设计目的：避免 64 位乘法的溢出问题
结构设计：
核心运算：
关键方法：Int128Mul 实现两个 64 位整数的精确乘法
自动切换：当坐标超过 loRange 时自动启用高精度模式
理解 Int128 的实现有助于理解 Clipper 如何在保持高精度的同时处理大范围坐标。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。