给个题目～～， 做不出来了。。。。

folklore

有数百亿计的三维空间直线， 其中某些直线可能会聚焦（聚焦非相交，可用设一固定Epsilon值，距离小于该值认定为聚焦）于某一空间点， 如何找出聚焦数最多的前N个点的坐标（或以聚焦数降序排序）


PS:
聚焦： 就像平行光通过凹透镜，聚焦某一点一样

Ager

暂有两个问题。

（1）“可用设一固定Epsilon值，距离小于该值认定为聚焦” —— 是不是可以这么认为：假设空间中有一点P，P的ε领域内，若有n个直线相交点存在，则可以认为这n个交点是“关于(P,ε)的聚焦”集合的元素。 ？？那么，对这个n有要求吗？（我觉得应该有。）

（2）“聚焦： 就像平行光通过凹透镜，聚焦某一点一样”  ？？

Ager

“可用设一固定Epsilon值，距离小于该值认定为聚焦”

—— 其实上面我讲的那个视角（方法）倒是复杂了。不妨反过来，像这样：

若空间中有一对直线相交于P，那么有P的ε领域，可记为(P,ε)。（可能须要）求出所有(Pi,ε)，再判别有哪些(Pi,ε)“交会”，从而得到交会组。对于每个交会组，由一系列“分权值”（最简单的例子是交会元素的数量）计算出该交会组的“总权值”。显然，总权值越大的交会组，就越具有聚焦意义。

楼主，请问，是不是这个意思？

folklore

回复 2# Ager


    面壁，
มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้มั้้้้้้้้้้้้้้

folklore

回复 3# Ager


    关健是直线的数量， 这个是难题。。。。理论最快的算法也是n^2， 这个太大了。

sqfasd

其实就是聚类吧，用K均值算法就好了。
K均值算法。不过有限制条件，只能找出K个聚焦集合，而且K不能太大，这个做不了排序，复杂度太高。
大概思想是：
1.先随机找K个点做为种子，代表K个集合的聚焦点
2.遍历所有直线，把直线归类到K个集合之一(按最小距离准则)，然后重新计算每个集合的中心
3.迭代第二步直到满足聚焦条件

复杂度为O(n*k*t),n是总数，k为聚焦集个数，t为迭代次数

folklore

回复 6# sqfasd


    学习了。

sqfasd

回复 7# folklore

闻道有先后，术业有专攻，相互学习
这是数据挖掘很普通的算法

starwing83

直线的坐标有没有限制？如果在1024＊1024＊1024内，那么每个像素点保存一个“直线经过”的数字，对每条直线进行像素标记，最后排序这么多个数字。

如果直线最多16条相交，4G内存就足够了。

wait_rabbit

sqfasd 发表于 2013-06-29 08:52
其实就是聚类吧，用K均值算法就好了。
K均值算法。不过有限制条件，只能找出K个聚焦集合，而且K不能太大， ...

学习，前段时间刚瞅了瞅 k-means clustering。