j**********3 发帖数: 3211 | 1 以前狗家的一个问题:
怎么判断一个点在多边形里?o(n), o(lgn)
这个怎么做啊?
由此,我想到相关的问题:
1. 给你一堆多边形的顶点,无序,你怎么知道某个点的下一个点是哪个点?也就是说
,你怎么从这些点中找到边缘?
2. 怎么判断两个多边形是否有交集?
3. 怎么判断两个多边形合并后的顶点?
4. 怎么求多边形面积
一头雾水,忘有大牛解答。。。 |
j***y 发帖数: 1640 | |
i**********g 发帖数: 758 | 3 re, read the book
【在 j***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有看过 普林斯顿 的 算法书?
|
j**********3 发帖数: 3211 | 4 没看过,求详解,哪本书,哪一章?
谢谢!
【在 j***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有看过 普林斯顿 的 算法书?
|
j**********3 发帖数: 3211 | 5 没看过,求详解,哪本书,哪一章?
谢谢!
【在 j***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有看过 普林斯顿 的 算法书?
|
j**********3 发帖数: 3211 | 6 求详解,具体是哪一章?谢谢!
【在 i**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : re, read the book
|
f**********r 发帖数: 2137 | 7 intro to algo, chapter 33
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求详解,具体是哪一章?谢谢!
|
j**********3 发帖数: 3211 | 8 谢谢!!
【在 f**********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : intro to algo, chapter 33
|
j**********3 发帖数: 3211 | 9 thanks!
【在 f**********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : intro to algo, chapter 33
|
f****y 发帖数: 243 | |
|
|
j**********3 发帖数: 3211 | 11 能详细说说么?
谢谢
【在 f****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : dp
|
f****y 发帖数: 243 | 12 想法是任选一对点,去掉与目标点在异侧的点,然后重复。。。直至三角形
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细说说么? : 谢谢
|
f****y 发帖数: 243 | 13 类似快排,不过复杂度到了n*logn
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能详细说说么? : 谢谢
|
e**y 发帖数: 1 | |
l*****u 发帖数: 13 | |
j**********3 发帖数: 3211 | 16 这是针对我上边哪个问题?
另外,给多边形的时候,那些点,是按顺序给的么?如果不按outline的顺序给的点,
我都不知道怎么找相邻点。
【在 f****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想法是任选一对点,去掉与目标点在异侧的点,然后重复。。。直至三角形
|
j**********3 发帖数: 3211 | 17 大牛,这些点,是按顺序给的么?如果不是,怎么知道多边形的边界呢?
另外,如何把两个多边形拼到一起,找交点呢?
【在 l*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是一个计算几何问题,Even-odd rule algorithm, O(n): : https://www.ics.uci.edu/~eppstein/161/960307.html
|
R*********d 发帖数: 34 | 18 应该是按顺序给的,专门有找凸包的算法:
1. Granham's scan O(NlogN)
2. Jarvis's march O(Nh)
两个算法在intro to algorithms 里面都有讲
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛,这些点,是按顺序给的么?如果不是,怎么知道多边形的边界呢? : 另外,如何把两个多边形拼到一起,找交点呢?
|
j**********3 发帖数: 3211 | 19 请问,您列出来的这两个算法,是针对哪个问题的呢?
谢谢!
【在 R*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是按顺序给的,专门有找凸包的算法: : 1. Granham's scan O(NlogN) : 2. Jarvis's march O(Nh) : 两个算法在intro to algorithms 里面都有讲
|
r***x 发帖数: 65 | 20 他说了啊。。找凸包的。。最小包含所有给定点的凸多边形。。
如果给的点无序。。排序就行吧
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问,您列出来的这两个算法,是针对哪个问题的呢? : 谢谢!
|
j**********3 发帖数: 3211 | 21 画个简单的5边形,你就发现排序不行啊!!
【在 r***x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他说了啊。。找凸包的。。最小包含所有给定点的凸多边形。。 : 如果给的点无序。。排序就行吧
|