[文本处理] 批处理用怎么实现快速判断点与多边形关系呢

tommytangtang

多边形顶点数据如下：
A
96.802,87.23
89.094,78.623
92.268,64.808
115.391,61.863
124.913,77.265
115.845,90.174
102.696,92.439
96.802,87.23
待判断的点

如果点在多边形外就保存下来>>c.txt
如果点在多边形内或者多边形边上就剔除它>>d.txt
基本思路是用射线法，计算以待判断点（yt，xt）为起点，
平行向右或者向上发射射线，依次与每条多边形的边发射，判断有没有交点，有偶数个交点包括0，就说明在多边形内，那么这一行数据>>d.txt。奇数个就>>c.txt
当某条边的两个顶点x坐标 x(1),x(2)满足如下条件时
If xt >= x1 And xt < x2 or xt <= x1 And xt > x2 then  ::就是说要依次找到相交的可能性，再去判断下面的
set yt=yi+(y2-y1)(xt-x1)/(x2-x1)
if yt > y0 Then Ncross = Ncross + 1    ::如果有交点，交点数Ncross就+1
每个点遍历每条边，if Ncross%2=0，>>d.txt
else if Ncross%2=1，>>c.txt
因为需要判断的点数据量非常大（有几百万个），用vb还可以做出来，但是速度太慢了，最近感受到了gawk的速度，想用gawk或者sed去解决，但是又涉及到二维数组，头大，哪位大神能帮帮忙

CrLf

sed 不用考虑，gawk 可能可以
如果数量大，还是用 perl 或者其他什么更合适的语言吧
另，Ncross+1 改用 Ncross= not Ncross 更好，这样就不需要计算 Ncross%2 了

tommytangtang

回复 2# CrLf


    批处理应该要比用vb编出来的速度快多了吧，我想先用批处理试试，批处理的数组像vb一样吗，论坛里一搜出来的都是vbs数组，vbs又是什么

CrLf

唔...其实批处理做这个是极其慢的
vbs 效率远比 vb 低，还是用 c 写个好了，最快

523066680

这么多点，撸主搞图形的？

tommytangtang

回复 4# CrLf


    额。。。前几天处理固定格式文本数据的时候你让我扔了个gawk到win32里

让我感受到了它处理文本速度上的快感，我还以为这种处理也很速度呢，好好的研究了几天，全网搜索了好多教程，但是一写起来，它的判断啊，数组让我崩溃了。。。

原来他不擅长这种啊。。。

tommytangtang

回复 5# 523066680


    算是吧，经常用autocad的，工作需要自己弄点小程序

neorobin

回复 6# tommytangtang

推荐书籍
计算机图形学的算法基础
计算机图形学几何工具算法详解

维基百科: http://en.wikipedia.org/wiki/Point_in_polygon

523066680

回复 7# tommytangtang


   
这里面88是什么意思？不是Z轴吧，数据类型不一样
100.477 85.911 88
96.747 84.002 88

tommytangtang

回复 9# 523066680


    哈哈，被你发现了，最后一列是我乱加上去的，本来应该是不同的数据表示z轴的，88吉利

tommytangtang

回复 8# neorobin


    谢谢推荐，我说的思路和维基百科的差不多（全英文的只看懂了大概。。。）

CrLf

回复 6# tommytangtang


    纯批很慢，第三方工具很快

neorobin

找到些代码
http://rosettacode.org/wiki/Ray-casting_algorithm

tommytangtang

回复 13# neorobin


    大神给的都太高端了，全E文经常看不懂，他处理的多边形只是矩形吗，那么多语言写出来了，好像就freebasic好理解一点

523066680

回复 14# tommytangtang


　　按你的平行线的方法应该就可以的，他给的是书，可以慢慢看。
这个还是解决当下问题要紧吧？ 以前我还折腾一点儿，现在也记不起来咯。
楼主给个公式我可以用perl写写。（1楼那个公式太潦草……）
图我做出来了，还好不是凹多边形，（gl老版本，见笑）