tommytangtang

回复 15# 523066680


    谢谢热心的版版，我这个也不急的，这个是我的举例，如果数据量只有这么几个数的话，我用autocad也可以解决的，主要是大批量的判断，就非常难搞了

neorobin

回复 14# tommytangtang

处理的是一般多边形, 在C代码中有测试用的多边形, 顶点坐标可以看出是一个 正4边形, 和一个 凹 8边形

vec vsq[] = {	{0,0}, {10,0}, {10,10}, {0,10},
			{2.5,2.5}, {7.5,0.1}, {7.5,7.5}, {2.5,7.5}};
 
polygon_t sq = { 4, vsq }, /* outer square */
sq_hole = { 8, vsq };      /* outer and inner square, ie hole */
复制代码

523066680

其实这个问题应该看这本书：《实时碰撞检测算法技术》而且我手上有一本，
当时纯粹手贱买下的，从来没看过……  http://www.tup.com.cn/book/Showbook.asp?CPBH=033422-01&DJ=52


第五章就有  点与多边形之间的测试、点与三角形之间的测试（多边形可以分为多个三角形）

CrLf

按顶楼算法实现了基本功能，也不懂得到的结果是不是正确的，撸主搞个样本来比对下吧：
http://bbs.bathome.net/viewthread.php?tid=31486

523066680

回复 19# CrLf


    你把筛选的顶点分两批晒一下，我可以脚本绘图 （纯粹找事做）

CrLf

回复 20# 523066680


    那敢情好，有劳您老人家了！

    顺便请教一下用什么脚本绘图比较方便

523066680

回复 21# CrLf

虽说Perl和python都有很多绘图接口，但是数据表达上的话还是python比较好用
不过我也忘了python怎么用了， =_= 正在用C语言+OPENGL绘图

523066680

回复 21# CrLf


    C.txt 有一个点在里面， 是哪个还不清楚[attach]7585[/attach]
    B.txt 的坐标全在外面
我自己抄了个算法，结果也不对，难道是绘图有问题？晕。

2014-08-18， 按碰撞检测算法书上的算法做了一个

C/C++的代码以及链接参考附件

Perl代码：

use IO::Handle;
STDOUT->autoflush(1);

my $coordfile="a.txt";
my @poly=(
    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,
);

our @V;
my $i=0;
while (scalar(@poly)>0) {
    $V[$i]{x}=shift @poly;
    $V[$i]{y}=shift @poly;
    $i++;
}

my ($x, $y);
my %dot;
open READ,"<",$coordfile or die "$!";
open INPOLY, ">", "inside.txt" or die;
open OUTPOLY, ">", "outside.txt" or die ;
foreach (<READ>) {
    ($x, $y, undef) = split(/ |,/, $_);
    #print $x," , ",$y,"\n";
    $dot{x} = $x;
    $dot{y} = $y;

    if (&pointInPolygon(\%dot) eq "true") {
        print INPOLY "$x, $y\r\n";
        print "($x, $y) in polygon\n";
    } else {
        print OUTPOLY "$x, $y\r\n";
    }
}
close READ;
close INPOLY;
close OUTPOLY;

sub pointInPolygon {
    our @V;
    my $p = shift;
    my $npoints = $#V+1;
    my ($low, $high) = (0, $npoints);
    do {
        $mid = ($low + $high) / 2;
        $mid=int($mid)+1 if ($mid > int($mid));
        if ( &TriangleIsCCW($V[0], $V[$mid], $p) eq "true" ) {
            $low = $mid;
        } else {
            $high = $mid;
        }
    } while ( ($low + 1) < $high);

    if( ($low == 0) or ($high == $npoints) ) {
        #print "$npoints $low $mid $high\n";
        return "false";
    }
    return &TriangleIsCCW($V[$low], $V[$high], $p);
}

sub TriangleIsCCW {
    my ($p0, $p1, $p2) = @_;
    my $cross;
    my ($d0, $d1, $d2, $d3);
    $d0 = ($p1->{x} - $p0->{x});
    $d1 = ($p1->{y} - $p0->{y});
    $d2 = ($p2->{x} - $p0->{x});
    $d3 = ($p2->{y} - $p0->{y});

    $cross = &Cross($d0, $d1, $d2, $d3);
    if ($cross > 0) {
        return "true";
    } else {
        return "false";
    }
}

sub Cross {
    #T Cross(T x0, T y0, T x1, T y1) {
    #//|x0 y0| = |a b|
    #//|x1 y1|   |c d|
    #//ad * bc
    #//x0 * y1 - x1 * y0
    my ($x0, $y0, $x1, $y1) = @_;
    my $result;
    $result = ($x0 * $y1) - ($y0 * $x1);
    return $result;
}
复制代码

在区域范围内的点：
100.477, 85.911
96.747, 84.002
96.817, 75.030
105.692, 67.907
97.253, 70.233
111.950, 80.117
105.931, 76.600
111.138, 85.624
114.157, 74.060

tommytangtang

回复 23# 523066680


    结果不对啊，挑出来的坐标和之前我给的a.txt都对不上了，之前给的x没有小于10的，基本都是50以上
版主绘图没问题，我打印到图上也和你一样的
图中，红色的点是a.txt。蓝色的点是得到的结果。

523066680

回复 24# tommytangtang


这里面分明没有小于10的
100.477, 85.911
96.747, 84.002
96.817, 75.030
105.692, 67.907
97.253, 70.233
111.950, 80.117
105.931, 76.600
111.138, 85.624
114.157, 74.060

第一张图是昨晚的。第二张图才是今天的

CrLf

回复 23# 523066680


昨天刚好看到书上说可以把：

my $result;
$result = ($x0 * $y1) - ($y0 * $x1);
return $result;
复制代码

简化成：

($x0 * $y1) - ($y0 * $x1);
复制代码

523066680

回复 26# CrLf


　　谢谢提醒，昨天手工将C转Perl后BUG一堆，所以很谨慎地把句子分开了 =_=

就是这里有个取反…… 然后return cross > 0  真精简……

template<class T>
bool triangleIsCCW(
	T x0, T y0,
	T x1, T y1,
	T x2, T y2) {
	auto cross = -(Cross<T>(x1-x0,y1-y0,x2-x0,y2-y0));
	return cross > 0;
}
复制代码

523066680

#include <stdio.h>
#define bool int
#define false 0
#define true 1

typedef struct {
	float x;
	float y;
} Point;

Point poly[]={
    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,
};

float Cross(
    float x0, float y0, 
    float x1, float y1
) {
    return (x0 * y1) - (x1 * y0);
}

int triangleIsCCW( //判断三个点的顺序是否为逆时针
    Point P0, Point P1, Point P2
) {
    auto cross = (
        Cross(
            P1.x-P0.x, P1.y-P0.y,
            P2.x-P0.x, P2.y-P0.y
        )
    );
    return cross >= 0;
}

bool pointInPolygon(
    Point vip, Point poly[], int n_poly
) {
    // points represented by [(x0,y0), ... (xn,yn)]
    int low = 0,  high = n_poly;
    int mid;
    do {
        mid = (low + high) / 2;
        if ( 
            triangleIsCCW(poly[0], poly[mid], vip) 
        ) {
            low = mid;
        } else {
            high = mid;
        }
    } while (low + 1 < high);
    if (low == 0 || high == n_poly) return false;
    return triangleIsCCW(poly[low], poly[high], vip);
}

int main(int argc, char *argv[]) 
{
    FILE *fp = fopen("a.txt","r");
    FILE *wrt = fopen("inside.txt","w");
    Point vip;
    char s[1024];
	int n_poly = (sizeof(poly) / sizeof(poly[0].x)) / 2;
	int in_polygon;
    while ( ! feof(fp) ) {
        fgets(s, 1024, fp);
        if ( sscanf(s, "%f %f", &vip.x, &vip.y) < 2 ) {
            sscanf(s, "%f,%f", &vip.x, &vip.y);
        }
        in_polygon = pointInPolygon(vip, poly, n_poly);
        if ( in_polygon ) {
            printf("%.3f, %.3f\n", vip.x, vip.y);
            fprintf(wrt, "%.3f, %.3f\n", vip.x, vip.y);
        }
    }
    fclose(fp);
    fclose(wrt);
    return 0;
}
复制代码

算法来自《实时碰撞检测算法技术》5.4.1  点与多边形之间的测试  P139


这段C的处理结果和Perl又那么一两个点的误差，主要是有些点几乎就在边缘上，
零点零几的区别 和 0 判断产生不同的结果。
────────┐
100.477, 85.911 │
96.747, 84.002  │
96.817, 75.030  │
105.692, 67.907 │
97.253, 70.233  │
115.392, 61.864 │
111.950, 80.117 │
105.931, 76.600 │
111.138, 85.624 │
114.157, 74.060 │
120.702, 70.397 │
92.268, 64.808  │
115.391, 61.863 │
────────┘

DAIC

回复 3# tommytangtang


    vbs 就是 visual basic script

523066680

回复 29# DAIC


    少将，你为何有两颗太阳！