求一算法或想法

Question

求一算法或想法
已知一多边形（连续封闭，边都是直线）的各顶点坐标，（如存放在一个Vector里面）
给定一座标就其是否在该多边形内.

Answer 1

Polygon p = new Polygon(new int[]{0,10,10,0}, new int[]{0,0,10,10},4);
System.out.println(p.contains(3,3));
System.out.println(p.contains(13,3));

Answer 2

通过给定点,任意做一条不通过任何顶点的直线。求n边形的n条边（线段）与该直线的交点（如果线段与直线不相交，则交点为null）；交点用和给定点的有向距离表示（正负任意）。那么如果为正的交点有奇数个，那么该点在多边形内部，否则在多边形外部。

Answer 3

我觉得数学上的方法有：
  任意取多边形上的两点，设这两点的坐标分别为a（x1,y1)和b(x2,y2),需要判断的点为c(x3,y3).判断：
if ((x3>min(x1,x2)&&x3<max(x1,x2) && (y3>min(y1,y2)&&y3<max(y1,y2))
意思就是该点在任意两点"之间"；
如果任意两点都满足，则包含，否则不包含。
这个想法，不知道对不对。

Answer 4

图形学的经典问题，除了楼上说的，还有转角法，即点A绕多边形走一圈，AP扫过的角度如果是0则P在多边形外，如果是360度则P在多边形内。不过由于涉及到算角度，效率低一些

Answer 5

to Moonwalk:你这个方法只适用于凸多边形吧？

Answer 6

TO:回复人： ChDw(米) ( ) 信誉：155 
先谢谢了，去看看。TO:回复人： gogon() ( ) 信誉：100 
跟我原来想的差不多，但如何确定你做的这次直线不通过任何顶点？TO:回复人： Moonwalk(难为水) ( ) 信誉：100 
>任意取多边形上的两点
是指取任意两个多边形顶点吧？不是多边形内部的点是吧？
〉if ((x3>min(x1,x2)&&x3<max(x1,x2) && (y3>min(y1,y2)&&y3<max(y1,y2))
这个判断应该会跟你取的是那两点有关系吧。（取不同的两点，可能得到不同的结果）

Answer 7

Java里面的java.awt.Polygon 应该就是使用 Moonwalk(难为水)  说的方法完成的

Answer 8

计算机里判定是否通过一个点需要用最小距离来判断。这样当n比较大，而计算机的精度不够高的时候甚至找不到一条不通过任何顶点的直线。
不过如果不是这种情况的话，求各顶点与给定点连线的夹角的tan值。然后在这之外随便取一个就可以了。

Answer 9

Java里面的java.awt.Polygon 的判断算法;
    public boolean contains(double x, double y) {
        if (npoints <= 2 || !getBoundingBox().contains(x, y)) {
return false;
}
int hits = 0;

int lastx = xpoints[npoints - 1];
int lasty = ypoints[npoints - 1];
int curx, cury;

// Walk the edges of the polygon
for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
curx = xpoints[i];
cury = ypoints[i];

if (cury == lasty) {
continue;
}

int leftx;
if (curx < lastx) {
if (x >= lastx) {
continue;
}
leftx = curx;
} else {
if (x >= curx) {
continue; 
}
leftx = lastx;
}

double test1, test2;
if (cury < lasty) {
if (y < cury || y >= lasty) {
continue;
}
if (x < leftx) {
hits++;
continue;
}
test1 = x - curx;
test2 = y - cury;
} else {
if (y < lasty || y >= cury) {
continue;
}
if (x < leftx) {
hits++;
continue;
}
test1 = x - lastx;
test2 = y - lasty;
}

if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
hits++;
}
}

return ((hits & 1) != 0);
    }

Answer 10

解析几何的内容吧，都忘了=================================================================
        角落里的理想
                http://blog.csdn.net/zdsdiablo/
                                 --------十分钟年华老去
=================================================================

Answer 11

约当办法到是可以``不过怎么在计算机上实现``怎么先在外面找一点`??``怎么能确定找的点就是在外面`??``我的想法是``做过这个已知点A(x0,y0)直线``y=x0``再用这个直线和多边形S的边相交``得到一组交点``它们的纵坐标自上而下为(y1, y2, y3, ......)`由一对Y值得到一个区间``(y1,y2),(y3,y4)....若交点正为S的端点``则它的对应纵坐标自成一个区间``(y5,y5),(y6,y7)...判断y0是否在这一组区间就可以判断点A是S的内点`

Answer 12

嗯``有点意思了`` battlet说的比我的简单``只点比y0大的y值的点```看看最后的区间是否闭合``不用都做出区间来再比``