知识卡片
几何算法先定义退化与精度
开始前明确重复点、共线、端点重合、水平或垂直线段、边界包含及数值精度的处理。一般位置假设可以简化证明,但真实数据不一定满足;浮点舍入使接近零的方向判定不稳定,应采用适合输入范围的稳健谓词或精确算术。
262限制重复线段、共线重叠和零长度线段,水平或垂直线段仍需精确排序与事件处理。平行且不同直线不等于共线;共享端点是否算交点应事先定义。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 几何算法先定义退化与精度
- · 输入/输出
原书出处 · 2 处
- · 查看原书依据
一般位置,能够简化很多算法。 ·输入包含的点是否均匀分布?或者这些点在某种方式上聚成簇,可能会导致某些算法处于最坏情况? 本章描述的大多数算法都有值得我们去寻求正确方法的异常边缘情形,我们将在代码中描述这些情形。
- · 查看原书依据
不会出现重复的线段。没有两条线段会共线(也就是说,重叠或者有相同的斜率)。算法需要仔细地计算和精准地排序线段,这样才能支持垂直线段或者水平线段。没有一条线段只有一个点(例如,一条起点和终点相同的线段)。 [1]水平线段被认为左端点(高于)右端点。
参考来源
- 位置:《算法技术手册》第9章《假设》(spine1645;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1608.html;u250-ch09-002)。
- 结论依据:250全文及249的精度讨论实读。
- 原始内容:一般位置,能够简化很多算法。 ·输入包含的点是否均匀分布?或者这些点在某种方式上聚成簇,可能会导致某些算法处于最坏情况? 本章描述的大多数算法都有值得我们去寻求正确方法的异常边缘情形,我们将在代码中描述这些情形。
- 位置:《算法技术手册》第9章《输入/输出》(spine1655;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1618.html;u262-ch09-002)。
- 结论依据:262限制重复线段、共线重叠和零长度线段,水平或垂直线段仍需精确排序与事件处理。平行且不同直线不等于共线;共享端点是否算交点应事先定义。
- 原始内容:不会出现重复的线段。没有两条线段会共线(也就是说,重叠或者有相同的斜率)。算法需要仔细地计算和精准地排序线段,这样才能支持垂直线段或者水平线段。没有一条线段只有一个点(例如,一条起点和终点相同的线段)。 [1]水平线段被认为左端点(高于)右端点。