求点与多边形位置关系如何快速判断出来

Question

Java 一个点（x,y）和 1万个多边形 如何快速的判断这个点和多边形关系的算法 

Answer 1

java我不熟练，不过可以跟你说说方法。把所有点按x从小到大排序x0，x1，x2，...，xN，x(题目中的点)，xN+1，xN+2，...，xN+M。从x0开始判断，判断其临点x是否大于x(题)，如是便把此多边形标记起来，判断到xN(如果xN+1与x题相等也要进行判断，后面亦如此)为止。然后把标记的多边形再与x(题)作细分比较，直到x(题)与他们没有任何关系或者在他们其中一个之内、顶点上、边上为止。