知识卡片
计算几何把空间关系转为算法
几何任务可以涉及点、线段、多边形等对象的查询、构造和更新;选择算法时应明确维度、输入规模、精度模型与是否需要多次查询。
249的03397–03399定义点、线段、矩形、多维对象和半开整数区间接口;03400–03401列出最近点、相交和几何包围等应用。预处理是否值得取决于查询次数与更新成本;浮点舍入、退化位置、维度及边界包含规则会影响正确性。
260提及动态维护凸包以及按极角排序的Graham扫描;角度相同的点需正确处理距离与共线,方向比较可基于叉积,无须必然计算三角函数。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 计算几何把空间关系转为算法
- · 经典问题
- · 相关算法
原书出处 · 3 处
- · 查看原书依据
计算几何的相关问题。在过去几个世纪里,数学家们已经研究过很多这样的问题,自20世纪70年代起,计算几何开始被看做几何算法的一个子学科系统,相关数据结构保证了算法能够高效地执行。在这样的条件下,算法帮助技术人员解决了现实中大量的问题,本章将会介绍其中一些算法。本章阐述的一些数据结构和算法对于本科生来说
- · 查看原书依据
输入数据 计算机和问题必须定义输入数据。最常用的几种输入数据是: ·二维平面点集。 ·二维平面线段集。 ·二维平面矩形集合。 ·二维平面任意多边形集合。 二维结构(线、矩形和圆)有着对应的三维结构(面、立方体和球面)和n维结构(例如超平面、超立方和超球体)。高级计算几何问题均可以扩展到更高的维度。
- · 查看原书依据
Graham扫描,这个算法在1972年提出,需要使用到简单的三角函数性质。使用图9-9检查右折的方法,一个恰当的实现只需要简单的数据结构和基本的数学计算。Graham扫描首先将所有的点按照和最左下方的点的夹角进行排序,它能在O(n log n)的时间内计算出凸包。需要注意的是夹角相同的点,其顺序是按
参考来源
- 位置:《算法技术手册》第9章《概述》(spine1644;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1607.html;u248-ch09-001)。
- 结论依据:248全文与249的接口和任务分类对照实读。
- 原始内容:计算几何的相关问题。在过去几个世纪里,数学家们已经研究过很多这样的问题,自20世纪70年代起,计算几何开始被看做几何算法的一个子学科系统,相关数据结构保证了算法能够高效地执行。在这样的条件下,算法帮助技术人员解决了现实中大量的问题,本章将会介绍其中一些算法。本章阐述的一些数据结构和算法对于本科生来说
- 位置:《算法技术手册》第9章《经典问题》(spine1644;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1607.html;u249-ch09-001)。
- 结论依据:249的03397–03399定义点、线段、矩形、多维对象和半开整数区间接口;03400–03401列出最近点、相交和几何包围等应用。预处理是否值得取决于查询次数与更新成本;浮点舍入、退化位置、维度及边界包含规则会影响正确性。
- 原始内容:输入数据 计算机和问题必须定义输入数据。最常用的几种输入数据是: ·二维平面点集。 ·二维平面线段集。 ·二维平面矩形集合。 ·二维平面任意多边形集合。 二维结构(线、矩形和圆)有着对应的三维结构(面、立方体和球面)和n维结构(例如超平面、超立方和超球体)。高级计算几何问题均可以扩展到更高的维度。
- 位置:《算法技术手册》第9章《相关算法》(spine1654;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1617.html;u260-ch09-001)。
- 结论依据:260提及动态维护凸包以及按极角排序的Graham扫描;角度相同的点需正确处理距离与共线,方向比较可基于叉积,无须必然计算三角函数。
- 原始内容:Graham扫描,这个算法在1972年提出,需要使用到简单的三角函数性质。使用图9-9检查右折的方法,一个恰当的实现只需要简单的数据结构和基本的数学计算。Graham扫描首先将所有的点按照和最左下方的点的夹角进行排序,它能在O(n log n)的时间内计算出凸包。需要注意的是夹角相同的点,其顺序是按