geometry

id: geometry  
title: 编程面试几何 Cheat Sheet  
description: 编程面试几何学习指南，包括练习题、技巧、时间复杂度及推荐资源  
keywords:  
  [几何编程面试学习指南, 几何编程面试技巧, 几何练习题, 几何实用技巧, 几何时间复杂度, 几何推荐学习资源]  
sidebar_label: 几何  
toc_max_heading_level: 2​

引言

几何学是数学的一个分支，研究与距离、形状、大小以及图形相对位置相关的空间属性。大多数计算机科学课程中并不教授高级几何（例如三维几何），因此你可以预期面试中只会涉及二维几何问题。

在算法面试中，几何通常不是问题的重点（毕竟，你并不是在被考察数学能力）。你通常需要在问题中结合使用其他算法和/或数据结构。

边界情况

• 零值。这种情况总是容易让人犯错。

技巧

两点之间的距离

比较两点之间的距离时，直接使用 dx² + dy² 就足够了。无需对结果开方。示例：到原点的 K 个最近点

圆形重叠

判断两个圆是否重叠，只需检查两圆圆心之间的距离是否小于它们半径之和。

矩形重叠

两个矩形重叠，当且仅当以下条件成立：

overlap = rect_a.left < rect_b.right and \
  rect_a.right > rect_b.left and \
  rect_a.top > rect_b.bottom and \
  rect_a.bottom < rect_b.top
​

这里有一个不错的可视化演示。示例：矩形重叠

示例题目

• 你有一张平面，上面有很多矩形，求有多少个矩形互相交叉。
• 对于二维平面上的一组点，你会用哪种数据结构来查询距离原点最近的 k 个点？
• 给定多个点，找出距离原点最近的 k 个点。
• 如何对一个多边形进行三角剖分？

必备题目

如果你正在备考这个主题，这些题目是必须练习的。

• 矩形重叠

推荐练习题目

在你已经掌握相关知识并完成必备题目练习后，建议做这些题目。

• 到原点的 K 个最近点
• 矩形面积

推荐课程

import AlgorithmCourses from '../_courses/AlgorithmCourses.md'

免责声明：
本文档采用基于机器的 AI 翻译服务进行翻译。尽管我们力求准确，但请注意，自动翻译可能存在错误或不准确之处。应以原文语言版本的文档作为权威依据。如需获取关键信息，建议使用专业的人工翻译。对于因使用本翻译而产生的任何误解或误读，我们概不负责。