//
|
// Created by Scheaven on 2020/5/31.
|
//
|
|
#include "geometry_util.h"
|
using namespace std;
|
|
|
SPoint::_Point() {}
|
SPoint::_Point(float x, float y)
|
{
|
this->x = x;
|
this->y = y;
|
}
|
|
float calDistance(SPoint A, SPoint B)
|
{
|
float x_d, y_d;
|
x_d = A.x - B.x;
|
y_d = A.y - B.y;
|
float len = sqrt(x_d * x_d + 4*y_d * y_d);
|
return len;
|
}
|
|
/*
|
如果从点P作水平向左的射线的话，假设P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序（顺时针或逆时针）考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，
|
1) 如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况
|
2) 如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。
|
3) 如果射线竖直，而P的横坐标小于P1,P2的横坐标，则必然相交。
|
4) 再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。
|
* */
|
//bool Pt_in_Polygon(SPoint point, RegInfo* polygon)
|
//{
|
// int nCross = 0;
|
// for (int i = 0; i < polygon->count; ++i)
|
// {
|
// SPoint p1 = polygon[i];
|
// SPoint p2 = polygon[(i+1)%polygon->count];
|
//
|
// if ( p1.y == p2.y )
|
// continue;
|
// if ( p.y < min(p1.y, p2.y) )
|
// continue;
|
// if ( p.y >= max(p1.y, p2.y) )
|
// continue;
|
//
|
// // 求交点的x坐标（由直线两点式方程转化而来）
|
// float x = (float)(p.y - p1.y) * (float)(p2.x - p1.x) / (float)(p2.y - p1.y) + p1.x;
|
//
|
// // 只统计p1p2与p向右射线的交点
|
// if ( x > p.x )
|
// {
|
// nCross++;
|
// }
|
//
|
// }
|
//
|
// // 交点为偶数，点在多边形之外
|
// // 交点为奇数，点在多边形之内
|
// if ((nCross % 2) == 1)
|
// {
|
// return true; //在内部
|
// }
|
// else
|
// {
|
// return false; //在外部
|
// }
|
|
//}
|
|
|
/*
|
* 多边形部分，判断多边形重叠率的计算
|
*/
|
|
float computeArea(const SPoint * pt,int n ) {
|
float area0 = 0.f;
|
for (int i = 0 ; i < n ; i++ )
|
{
|
int j = (i+1)%n;
|
area0 += pt[i].x * pt[j].y;
|
area0 -= pt[i].y * pt[j].x;
|
}
|
return 0.5f * fabs(area0);
|
}
|
|
struct PointAngle{
|
SPoint p;
|
float angle;
|
};
|
|
float Polygon::area() const {
|
return computeArea(pt,n);
|
}
|
|
static inline int cross(const SPoint* a,const SPoint* b) {
|
return a->x * b->y - a->y * b->x;
|
}
|
|
static inline SPoint* vsub(const SPoint* a,const SPoint* b, SPoint* res) {
|
res->x = a->x - b->x;
|
res->y = a->y - b->y;
|
return res;
|
}
|
|
|
static int line_sect(const SPoint* x0,const SPoint* x1,const SPoint* y0,const SPoint* y1, SPoint* res) {
|
SPoint dx, dy, d;
|
vsub(x1, x0, &dx);
|
vsub(y1, y0, &dy);
|
vsub(x0, y0, &d);
|
float dyx = (float)cross(&dy, &dx);
|
if (!dyx) return 0;
|
dyx = cross(&d, &dx) / dyx;
|
if (dyx <= 0 || dyx >= 1) return 0;
|
res->x = int(y0->x + dyx * dy.x);
|
res->y = int(y0->y + dyx * dy.y);
|
return 1;
|
}
|
|
static int left_of(const SPoint* a,const SPoint* b,const SPoint* c) {
|
SPoint tmp1, tmp2;
|
int x;
|
vsub(b, a, &tmp1);
|
vsub(c, b, &tmp2);
|
x = cross(&tmp1, &tmp2);
|
return x < 0 ? -1 : x > 0;
|
}
|
|
static void poly_edge_clip(const Polygon* sub,const SPoint* x0,const SPoint* x1, int left, Polygon* res) {
|
int i, side0, side1;
|
SPoint tmp;
|
const SPoint* v0 = sub->pt+ sub->n - 1;
|
const SPoint* v1;
|
res->clear();
|
|
side0 = left_of(x0, x1, v0);
|
if (side0 != -left) res->add(*v0);
|
|
for (i = 0; i < sub->n; i++) {
|
v1 = sub->pt + i;
|
side1 = left_of(x0, x1, v1);
|
if (side0 + side1 == 0 && side0)
|
/* last point and current straddle the edge */
|
if (line_sect(x0, x1, v0, v1, &tmp))
|
res->add(tmp);
|
if (i == sub->n - 1) break;
|
if (side1 != -left) res->add(*v1);
|
v0 = v1;
|
side0 = side1;
|
}
|
}
|
|
static int poly_winding(const Polygon* p) {
|
return left_of(p->pt, p->pt + 1, p->pt + 2);
|
}
|
|
|
void intersectPolygonSHPC(const Polygon * sub, const Polygon* clip, Polygon* res)
|
{
|
int i;
|
Polygon P1,P2;
|
Polygon *p1 = &P1;
|
Polygon *p2 = &P2;
|
Polygon *tmp;
|
|
int dir = poly_winding(clip);
|
poly_edge_clip(sub, clip->pt + clip->n - 1, clip->pt, dir, p2);
|
for (i = 0; i < clip->n - 1; i++) {
|
tmp = p2; p2 = p1; p1 = tmp;
|
if(p1->n == 0) {
|
p2->n = 0;
|
break;
|
}
|
poly_edge_clip(p1, clip->pt + i, clip->pt + i + 1, dir, p2);
|
}
|
res->clear();
|
for (i = 0 ; i < p2->n ; i++) res->add(p2->pt[i]);
|
}
|
|
void intersectPolygonSHPC(const Polygon & sub,const Polygon& clip,Polygon& res) {
|
intersectPolygonSHPC(&sub, &clip, &res);
|
}
|
|
|
