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 的大作中提到】
: 没有看过 普林斯顿 的 算法书？
|
j**********3
发帖数: 3211 | 4 没看过，求详解，哪本书，哪一章？
谢谢！
【在 j***y 的大作中提到】
: 没有看过 普林斯顿 的 算法书？
|
j**********3
发帖数: 3211 | 5 没看过，求详解，哪本书，哪一章？
谢谢！
【在 j***y 的大作中提到】
: 没有看过 普林斯顿 的 算法书？
|
j**********3
发帖数: 3211 | 6 求详解，具体是哪一章？谢谢！
【在 i**********g 的大作中提到】
: re, read the book
|
f**********r
发帖数: 2137 | 7 intro to algo, chapter 33
【在 j**********3 的大作中提到】
: 求详解，具体是哪一章？谢谢！
|
j**********3
发帖数: 3211 | 8 谢谢！！
【在 f**********r 的大作中提到】
: intro to algo, chapter 33
|
j**********3
发帖数: 3211 | 9 thanks!
【在 f**********r 的大作中提到】
: intro to algo, chapter 33
|
f****y
发帖数: 243 | |
|
|
j**********3
发帖数: 3211 | 11 能详细说说么？
谢谢
【在 f****y 的大作中提到】
: dp
|
f****y
发帖数: 243 | 12 想法是任选一对点，去掉与目标点在异侧的点，然后重复。。。直至三角形
【在 j**********3 的大作中提到】
: 能详细说说么？
: 谢谢
|
f****y
发帖数: 243 | 13 类似快排，不过复杂度到了n*logn
【在 j**********3 的大作中提到】
: 能详细说说么？
: 谢谢
|
e**y
发帖数: 1 | |
l*****u
发帖数: 13 | |
j**********3
发帖数: 3211 | 16 这是针对我上边哪个问题？
另外，给多边形的时候，那些点，是按顺序给的么？如果不按outline的顺序给的点，
我都不知道怎么找相邻点。
【在 f****y 的大作中提到】
: 想法是任选一对点，去掉与目标点在异侧的点，然后重复。。。直至三角形
|
j**********3
发帖数: 3211 | 17 大牛，这些点，是按顺序给的么？如果不是，怎么知道多边形的边界呢？
另外，如何把两个多边形拼到一起，找交点呢？
【在 l*****u 的大作中提到】
: 这是一个计算几何问题，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 的大作中提到】
: 大牛，这些点，是按顺序给的么？如果不是，怎么知道多边形的边界呢？
: 另外，如何把两个多边形拼到一起，找交点呢？
|
j**********3
发帖数: 3211 | 19 请问，您列出来的这两个算法，是针对哪个问题的呢？
谢谢！
【在 R*********d 的大作中提到】
: 应该是按顺序给的，专门有找凸包的算法：
: 1. Granham's scan O(NlogN)
: 2. Jarvis's march O(Nh)
: 两个算法在intro to algorithms 里面都有讲
|
r***x
发帖数: 65 | 20 他说了啊。。找凸包的。。最小包含所有给定点的凸多边形。。
如果给的点无序。。排序就行吧
【在 j**********3 的大作中提到】
: 请问，您列出来的这两个算法，是针对哪个问题的呢？
: 谢谢！
|
j**********3
发帖数: 3211 | 21 画个简单的5边形，你就发现排序不行啊！！
【在 r***x 的大作中提到】
: 他说了啊。。找凸包的。。最小包含所有给定点的凸多边形。。
: 如果给的点无序。。排序就行吧
|
