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