如何快速确定一个点在10000个面中的哪一个内？

Question

本帖最后由 cuit 于 2010-12-29 10:10:52 编辑

Answer 1

List<Directory<int, int>>.Contains(new Directory<int, int>{{ x, y }})

Answer 2

Directory可以做几何运算么？
点在面内的意义是指 面 包含 点，而不是 点 在面的各个定点上。

Answer 3

from q in lst where q.x1<x and q.x2>x and q.y1=<y and q.y2>=y select q;

Answer 4

改进数据级结构以加快判断：
1、bounding box，比如每个面预先计算一个外接四方形。外接四方形可以用来迅速过滤。
2、quartet tree，比如把面分类，类似东南角，西北角（西北角等还可以继续细分...）。只遍历相应类的面，可以大大加快判断。

Answer 5

多边形是多种多样的。
比如凸多边形，单纯的判断 x,y的值域是肯定不行的linq应该实现不了
我现在已经用射线法写好了判读点在多边形的算法。
只是线性的list<polygon>遍历起来比较没效率。
但是一时想不到更好的存储结构。

Answer 6

Region temp = new Region(面List);//面全部放到区域里
temp.IsVisible(new PointF(X,y));//判断点是否在区域内