Question

摆得很正的矩形，四个边都平行于座标轴

经过数学课程洗礼，大家看到矩形都是直觉想到长与宽。然而在计算几何当中，我们倾向记录左下角座标（X 座标、Y 座标的下界）与右上角座标（X 座标、Y 座标的上界）。

就算矩形退化成线段、点，这种记录方式也不会有问题。

UVa 460 191

矩形相交

要判断矩形相交相当麻烦，相交的情形有许多种。

逆向思考，事情就变得容易多了：判断矩形不相交！以第二个矩形作为基准，第一个矩形完全落在其左方、右方、下方、上方，就是不相交。

如果是空心矩形，那麽还得侦测第一个矩形是不是被第二个矩形框住。

大量矩形交集，之一

两个矩形的交集还是矩形（可能退化成线段、点）。运用 Incremental Method 进行推理，大量矩形的交集当然还是矩形。

採用 Incremental Method，一次读入一个矩形，不断更新交集。时间複杂度 O(N)，N 是矩形数量。

大量矩形交集，之二

http://algo.kaust.edu.sa/Documents/cs372l07.pdf

大量矩形联集，之一

将联集区域切割为数个矩形。採用 Incremental Method，一次读入一个矩形，不断更新联集。

下面这段程式码仅计算联集面积。至于联集多边形，就请读者自行研究了。

Circle

圆形

记录圆心、半径。

UVa 10180 10425 10674 ICPC 4120

圆形相交

判断相交：圆心距大于等于半径差、小于等于半径和。

求得交点：一、馀弦定理，用半径、圆心距求得半个扇形角。二、圆心向量，顺时针和逆时针旋转，缩放成半径长度。

大量圆形联集

http://oi.abcdabcd987.com/ciru/

UVa 10969 ICPC 3532

Triangle

三角形

记录三个顶点，以逆时针顺序记录。

UVa 11122 11275 11836

大量三角形联集

我没有研究。

ICPC 3809

Helly's Theorem

Helly's Theorem

http://en.wikipedia.org/wiki/Helly's_theorem

一、一堆凸的东西，交集也是凸的。

二、二维的情况下，任选三个一组皆有交集，则全部合起来也有交集。三维的情况下，任选四个一组皆有交集，则全部合起来也有交集。以此类推。