s*****e 发帖数: 16824 | 1 没有这方面的知识,只能求大家帮助了。我现在遇到一个问题,需要把在n维空间里的
点投影到跟一个n维向量垂直的面上,然后找出这些投影中间距离最长的两点。请问有
什么算法么?有相关链接也可以,我可以自己看看。 | l*********s 发帖数: 5409 | | s*****V 发帖数: 21731 | 3 没看懂,1个点不就一个投影点么?怎么又出来两点。还是你有一堆投影?
算法我不知道,不过从数学上你说的这种投影长度应该很好算。空间中任意两点之间可
以有一个矢量A,这个矢量在任意平面(假设平面的单位法矢量为n)上投影为
A - A 点 n ,然后就可以算长度了。
然后你就排序好了
【在 s*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有这方面的知识,只能求大家帮助了。我现在遇到一个问题,需要把在n维空间里的 : 点投影到跟一个n维向量垂直的面上,然后找出这些投影中间距离最长的两点。请问有 : 什么算法么?有相关链接也可以,我可以自己看看。
| t****t 发帖数: 6806 | 4 我觉得他说得挺明白的啊, "把在n维空间里的点投影到跟一个n维向量垂直的面上", 就
是说有(若干)点和一个面, 没说是一个点啊.
投影其实不难算, 不过我看楼主也不会, 自己拿三维的推推应该就可以了. 难的是N个
二维点怎么求最大距离, 当然最笨最简单的办法是O(n^2), 如果要更快的, 我其实也不
知道有没有.
【在 s*****V 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看懂,1个点不就一个投影点么?怎么又出来两点。还是你有一堆投影? : 算法我不知道,不过从数学上你说的这种投影长度应该很好算。空间中任意两点之间可 : 以有一个矢量A,这个矢量在任意平面(假设平面的单位法矢量为n)上投影为 : A - A 点 n ,然后就可以算长度了。 : 然后你就排序好了
| l*********s 发帖数: 5409 | 5 stackflow has a post about convex hulk detection, still O(N^2) in worse
case, but on average could be much more efficient than brutal force
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得他说得挺明白的啊, "把在n维空间里的点投影到跟一个n维向量垂直的面上", 就 : 是说有(若干)点和一个面, 没说是一个点啊. : 投影其实不难算, 不过我看楼主也不会, 自己拿三维的推推应该就可以了. 难的是N个 : 二维点怎么求最大距离, 当然最笨最简单的办法是O(n^2), 如果要更快的, 我其实也不 : 知道有没有.
| g*****y 发帖数: 7271 | 6 Really? 举个反例?
不过人这不是2维平面,是n-1维的吧。
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得他说得挺明白的啊, "把在n维空间里的点投影到跟一个n维向量垂直的面上", 就 : 是说有(若干)点和一个面, 没说是一个点啊. : 投影其实不难算, 不过我看楼主也不会, 自己拿三维的推推应该就可以了. 难的是N个 : 二维点怎么求最大距离, 当然最笨最简单的办法是O(n^2), 如果要更快的, 我其实也不 : 知道有没有.
| t****t 发帖数: 6806 | 7 咦, 我好象搞错了, sorry. 昨晚上没睡好, 今天脑袋有点短路.
【在 g*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Really? 举个反例? : 不过人这不是2维平面,是n-1维的吧。
| w***g 发帖数: 5958 | 8 没有generic的比O(N^2)好的算法. 对于n-1维面中可以人为放置N个点使得它们之间两
两距离相等, 然后稍微扰动其中一个产生一对距离最大的. 这种情况下应该没有好办
法快速找出最远的一对. Convex hull跟这个不是同一个问题.
【在 g*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Really? 举个反例? : 不过人这不是2维平面,是n-1维的吧。
| s*****e 发帖数: 16824 | 9 是多个点。
【在 s*****V 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看懂,1个点不就一个投影点么?怎么又出来两点。还是你有一堆投影? : 算法我不知道,不过从数学上你说的这种投影长度应该很好算。空间中任意两点之间可 : 以有一个矢量A,这个矢量在任意平面(假设平面的单位法矢量为n)上投影为 : A - A 点 n ,然后就可以算长度了。 : 然后你就排序好了
| n******t 发帖数: 4406 | 10 对计算几何不了解,但是貌似你这个问题和投影关系不大,就是算N维空间中一个点集
里面的最大的距离pair.因为你反正第一步是算个投影坐标。
【在 s*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有这方面的知识,只能求大家帮助了。我现在遇到一个问题,需要把在n维空间里的 : 点投影到跟一个n维向量垂直的面上,然后找出这些投影中间距离最长的两点。请问有 : 什么算法么?有相关链接也可以,我可以自己看看。
|
|