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 */
复制代码

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;
}
复制代码

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

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

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;
}
复制代码

#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;
}
复制代码

1、出现与射线平行的边线时，在线上的点应视为不在区域内才能避免被多次计算
2、有两个角点重合时，会计算两次而导致误判
复制代码

　　图为：凸多边形顶点的二分搜索使得点P的包含测试的时间复杂度为O(log n)（这里测试了4条边：A~D）

　　另外，预计算函数TriangleIsCCW()将计算三角形顶点是否为逆时针方向排列。该测试的高效实现

方法如下列代码所示：

　　该点包含测试方法类似[Preparata85]中所描述的相关算法结构，其中n边多边形内部也存在一个与

此处的顶点V0对应。

－－－－－－－－－以下内容可能造成不适，请[跳过]或者[对上面内容进行消化]后再访问－－－－－－－－

   该算法通过多边形的一个原点和其他顶点，对多边形进行划分（二分），通过TriangleIsCCW()函数

逐渐找到最靠近点P的两个边界，在示例中最后找到为：V0->V5 和 V0->V6 。这个过程手工演算一

次就知道原理了。

　　最后一步 return TriangleIsCCW(v[low], v[high], p); 即为判断：如果V5->V6->P 呈逆时针顺序，

则点P在多边形内部。

TriangleIsCCW() 函数判断传入的三个顶点数据是否呈逆时针排列，书中没有给出，但是在网上找到：
─────────────────────────────┐
    template<class T>                                     │
    T Cross(T x0, T y0, T x1, T y1) {                     │
        //|x0 y0| = |a b|                                 │
        //|x1 y1|   |c d|                                 │
                                                          │
        //ad * bc                                         │
        //x0 * y1 - x1 * y0                               │
                                                          │
        return (x0 * y1) - (y0 * x1);                     │
    }                                                     │
                                                          │
    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;                                 │
    }                                                     │
─────────────────────────────┘

　　原理就是对传入的三个顶点坐标进行向量运算（以P为原点，计算出另外两个点

的相对坐标，视为向量ａ、ｂ，计算这两个向量的向量积（cross product））

（高等数学第一章有介绍这个计算和性质，或者在网上搜索：叉积……）

计算向量积得到的是垂直于ａ和ｂ所在平面的向量V，遵循右手法则：右手握住V

向量（垂直于ａ和ｂ），手指从ａ向ｂ环绕，大拇指的方向和向量方向一致。

也就是如果ａ-> ｂ->原点p 是逆时针方向则V>0 ，是反方向则V<0，如果ａｂ平

行或者其中一方为0，则V=0

• Point in polygon
• Point in spline polygon
• Point left of ray
• Shortest path through polygon
• Polygon area
• Polygon fill
• Polygon hatchline fill
• Polygon perimeter
• Polygon inset
• Smallest enclosing polygon
• Spline bounding rect
• Spline polygon area
• Line-line intersection
• Calculus without calculus
• Area of a circle
• Pi — diameter vs. radius
• Mandelbrot slideshow
• Non-Euclidean geometry         (blog)
• Fifth-order polynomials        (blog)
• Perspective photo distortion
• Collatz Conjecture analysis    (blog)
• Infinite Sets                  (blog)
• Only even prime                (blog)
• Century name vs. year number   (blog)
• Four-Color Theorem analysis    (blog)