问面经里的问题:怎么判断一个点在多边形里?

原帖地址:mitbbs

以前狗家的一个问题:

怎么判断一个点在多边形里?o(n), o(lgn)

这个怎么做啊?

由此,我想到相关的问题:
1. 给你一堆多边形的顶点,无序,你怎么知道某个点的下一个点是哪个点?也就是说
,你怎么从这些点中找到边缘?

2. 怎么判断两个多边形是否有交集?

3. 怎么判断两个多边形合并后的顶点?

4. 怎么求多边形面积

一头雾水,忘有大牛解答。。。