|
|
#include "stdafx.h"
|
|
|
#include "topologicalanalysis.h"
|
|
|
|
|
|
|
|
|
TopologicalAnalysis::TopologicalAnalysis(void)
|
|
|
{
|
|
|
}
|
|
|
|
|
|
|
|
|
TopologicalAnalysis::~TopologicalAnalysis(void)
|
|
|
{
|
|
|
}
|
|
|
|
|
|
|
|
|
bool TopologicalAnalysis::isPointInLine(double* point, double* startPoint, double* endPoint,float tolerance)
|
|
|
{
|
|
|
double AX = startPoint[0];
|
|
|
double AY = startPoint[1];
|
|
|
double BX = endPoint[0];
|
|
|
double BY = endPoint[1];
|
|
|
double PX = point[0];
|
|
|
double PY = point[1];
|
|
|
|
|
|
double dx_AB = AX - BX;
|
|
|
double dy_AB = AY - BY;
|
|
|
double dx_PA = PX - AX;
|
|
|
double dy_PA = PY - AY;
|
|
|
double dx_PB = PX - BX;
|
|
|
double dy_PB = PY - BY;
|
|
|
|
|
|
double AB = sqrt(dx_AB*dx_AB + dy_AB*dy_AB);
|
|
|
double PA = sqrt(dx_PA*dx_PA + dy_PA*dy_PA);
|
|
|
double PB = sqrt(dx_PB*dx_PB + dy_PB*dy_PB);
|
|
|
double rate = abs(PA + PB - AB) / AB;
|
|
|
if (rate < tolerance)
|
|
|
{
|
|
|
return true;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//判断线是否在折线上
|
|
|
int TopologicalAnalysis::isPointInPolyLine(double* point, vector<double>& lineX,vector<double>& lineY,float tolerance)
|
|
|
{
|
|
|
int lineNum = lineX.size();
|
|
|
double startPoint[2],endPoint[2];
|
|
|
for (int i=0;i<lineNum-1;i++)
|
|
|
{
|
|
|
startPoint[0] = lineX.at(i);
|
|
|
startPoint[1] = lineY.at(i);
|
|
|
endPoint[0] = lineX.at(i+1);
|
|
|
endPoint[1] = lineY.at(i+1);
|
|
|
bool b_in = isPointInLine(point,startPoint,endPoint,tolerance);
|
|
|
if(b_in)
|
|
|
{
|
|
|
return (i+1);
|
|
|
}
|
|
|
}
|
|
|
//判断收尾点线段
|
|
|
startPoint[0] = lineX.at(lineNum-1);
|
|
|
startPoint[1] = lineY.at(lineNum-1);
|
|
|
endPoint[0] = lineX.at(0);
|
|
|
endPoint[1] = lineY.at(0);
|
|
|
bool b_end = isPointInLine(point,startPoint,endPoint,tolerance);
|
|
|
if (b_end)
|
|
|
{
|
|
|
return lineNum;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
return 0;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//根据两点求出垂线过第三点的直线的交点
|
|
|
bool TopologicalAnalysis::GetPointToLineVerticalCross(double* linePt1,double* linePt2,double* pt,double* crossPt)
|
|
|
{
|
|
|
//垂直线
|
|
|
if (linePt1[0] == linePt2[0])
|
|
|
{
|
|
|
crossPt[0] = linePt1[0];
|
|
|
crossPt[1] = pt[1];
|
|
|
return true;
|
|
|
}
|
|
|
//水平线
|
|
|
if (linePt1[1] == linePt2[1])
|
|
|
{
|
|
|
crossPt[0] = pt[0];
|
|
|
crossPt[1] = linePt1[1];
|
|
|
return true;
|
|
|
}
|
|
|
float A = (linePt1[1]- linePt2[1]) * 1.0 / (linePt1[0]- linePt2[0]);
|
|
|
float B = (linePt1[1] - A * linePt1[0]);
|
|
|
float m = pt[0] + A * pt[1];
|
|
|
|
|
|
/// 求两直线交点坐标
|
|
|
crossPt[0] = (m - A * B) * 1.0f / (A * A + 1);
|
|
|
crossPt[1] = A * crossPt[0] + B;
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
//判断点是否在(简单)多边形内
|
|
|
//polygon: 首尾相同的Cpoint1列表
|
|
|
bool TopologicalAnalysis::isPointInPolygon(CPoint1 point, vector<CPoint1> polygon){
|
|
|
if (polygon.size()<=3) return false; // 一个有效多边形顶点数应大于3
|
|
|
|
|
|
int LineNum = polygon.size();
|
|
|
CPoint1 leftP = point;
|
|
|
CPoint1 rightP;
|
|
|
rightP.SetX(getMaxX(polygon) + 1);
|
|
|
rightP.SetY(point.GetY());
|
|
|
int count = 0, yPrev = polygon[LineNum - 2].GetY();
|
|
|
CPoint1 v1, v2;
|
|
|
v1 = polygon[LineNum - 1];
|
|
|
for (int i = 0; i < LineNum; i++)
|
|
|
{
|
|
|
v2 = polygon[i];
|
|
|
|
|
|
if (isPointInLine(leftP, v1, v2))
|
|
|
return true;
|
|
|
|
|
|
if (v1.GetY() != v2.GetY())
|
|
|
{
|
|
|
if (isLineIntersect(v1, v2, leftP, rightP))
|
|
|
{
|
|
|
if (isPointInLine(v1, leftP, rightP))
|
|
|
{
|
|
|
if (v1.GetY()<v2.GetY()) { if (v1.GetY()>yPrev) count++; }
|
|
|
else { if (v1.GetY() < yPrev) count++; }
|
|
|
}
|
|
|
else if (!isPointInLine(v2, leftP, rightP))
|
|
|
{
|
|
|
count++;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
yPrev = v1.GetY();
|
|
|
|
|
|
v1 = v2;
|
|
|
}
|
|
|
return (count % 2 == 1);
|
|
|
}
|
|
|
|
|
|
double TopologicalAnalysis::getMaxX(vector<CPoint1> points){
|
|
|
if (points.size()==0)
|
|
|
return -1;
|
|
|
else if(points.size()==1)
|
|
|
return points[0].GetX();
|
|
|
else{
|
|
|
double maxx = points[0].GetX();
|
|
|
for (unsigned i=1; i<points.size();i++)
|
|
|
{
|
|
|
if(points[i].GetX()>maxx){
|
|
|
maxx = points[i].GetX();
|
|
|
}
|
|
|
}
|
|
|
return maxx;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
bool TopologicalAnalysis::isPointInLine(CPoint1 point, CPoint1 startPoint, CPoint1 endPoint)
|
|
|
{
|
|
|
long AX = startPoint.GetX();
|
|
|
long AY = startPoint.GetY();
|
|
|
long BX = endPoint.GetX();
|
|
|
long BY = endPoint.GetY();
|
|
|
long PX = point.GetX();
|
|
|
long PY = point.GetY();
|
|
|
|
|
|
double dx_AB = AX - BX;
|
|
|
double dy_AB = AY - BY;
|
|
|
double dx_PA = PX - AX;
|
|
|
double dy_PA = PY - AY;
|
|
|
double dx_PB = PX - BX;
|
|
|
double dy_PB = PY - BY;
|
|
|
|
|
|
double AB = sqrt(dx_AB*dx_AB + dy_AB*dy_AB);
|
|
|
double PA = sqrt(dx_PA*dx_PA + dy_PA*dy_PA);
|
|
|
double PB = sqrt(dx_PB*dx_PB + dy_PB*dy_PB);
|
|
|
double rate = abs(PA + PB - AB) / AB;
|
|
|
if (rate < 0.001)
|
|
|
{
|
|
|
return true;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
// 叉积
|
|
|
double mult(CPoint1 a, CPoint1 b, CPoint1 c)
|
|
|
{
|
|
|
return (a.GetX()-c.GetX())*(b.GetY()-c.GetY())-(b.GetX()-c.GetX())*(a.GetY()-c.GetY());
|
|
|
}
|
|
|
|
|
|
//判断两条直线段是否相交
|
|
|
bool TopologicalAnalysis::isLineIntersect(CPoint1 line1Start, CPoint1 line1End, CPoint1 line2Start, CPoint1 line2End){
|
|
|
double l1sx = line1Start.GetX();
|
|
|
double l1sy = line1Start.GetY();
|
|
|
double l1ex = line1End.GetX();
|
|
|
double l1ey = line1End.GetY();
|
|
|
double l2sx = line2Start.GetX();
|
|
|
double l2sy = line2Start.GetY();
|
|
|
double l2ex = line2End.GetX();
|
|
|
double l2ey = line2End.GetY();
|
|
|
if ( max(l1sx, l1ex)<min(l2sx, l2ex) )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
if ( max(l1sy, l1ey)<min(l2sy,l2ey) )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
if ( max(l2sx, l2ex)<min(l1sx, l1ex) )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
if ( max(l2sy,l2ey)<min(l1sy, l1ey) )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
if ( mult(line2Start, line1End, line1Start)*mult(line1End, line2End, line1Start)<0 )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
if ( mult(line1Start, line2End, line2Start)*mult(line2End, line1End, line2Start)<0 )
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
|
|
|
bool TopologicalAnalysis::GetBoundingBoxVertices(const vector<double>& polygonX,const vector<double>& polygonY,vector<double>& rectangleX,vector<double>& rectangleY)
|
|
|
{
|
|
|
if (polygonX.size()<3 || polygonY.size()<3) return false;
|
|
|
|
|
|
//计算最大最小x和y
|
|
|
double minX = polygonX[0];
|
|
|
double minY = polygonY[0];
|
|
|
double maxX = polygonX[0];
|
|
|
double maxY = polygonY[0];
|
|
|
|
|
|
for (int i=0;i<polygonY.size();++i) {
|
|
|
if (polygonX[i] < minX) minX = polygonX[i];
|
|
|
if (polygonY[i] < minY) minY = polygonY[i];
|
|
|
if (polygonX[i] > maxX) maxX = polygonX[i];
|
|
|
if (polygonY[i] > maxY) maxY = polygonY[i];
|
|
|
}
|
|
|
|
|
|
rectangleX.push_back(minX);
|
|
|
rectangleX.push_back(maxX);
|
|
|
rectangleX.push_back(maxX);
|
|
|
rectangleX.push_back(minX);
|
|
|
|
|
|
rectangleY.push_back(maxY);
|
|
|
rectangleY.push_back(maxY);
|
|
|
rectangleY.push_back(minY);
|
|
|
rectangleY.push_back(minY);
|
|
|
}
|
|
|
|
|
|
//计算直线与多边形的交点
|
|
|
int TopologicalAnalysis::linePolygonIntersections(const Point2D& linePt1,const Point2D& linePt2,const vector<double>& polygonX,const vector<double>& polygonY, vector<Point2D>& result)
|
|
|
{
|
|
|
|
|
|
Line2D line1;
|
|
|
line1.p1 = linePt1;
|
|
|
line1.p2 = linePt2;
|
|
|
line1.is_seg = false;
|
|
|
Point2D intersectionPt;
|
|
|
vector<Point2D> resPoints;
|
|
|
for (int i=0;i<polygonX.size()-1;++i)
|
|
|
{
|
|
|
Point2D pt1,pt2;
|
|
|
pt1.x = polygonX[i];
|
|
|
pt1.y = polygonY[i];
|
|
|
pt2.x = polygonX[i+1];
|
|
|
pt2.y = polygonY[i+1];
|
|
|
Line2D line2;
|
|
|
line2.p1 = pt1;
|
|
|
line2.p2 = pt2;
|
|
|
line2.is_seg = false;
|
|
|
|
|
|
/*
|
|
|
int type = isLineIntersecting(line1,line2,intersectionPt);
|
|
|
if (type == 1 || type == 2) //相交或重合
|
|
|
{
|
|
|
resPoints.push_back(intersectionPt);
|
|
|
}*/
|
|
|
|
|
|
/*
|
|
|
if (isSegIntersect(line1,line2,intersectionPt))
|
|
|
{
|
|
|
line2.is_seg = true;
|
|
|
if (isponl(intersectionPt,line2))
|
|
|
{
|
|
|
resPoints.push_back(intersectionPt);
|
|
|
}
|
|
|
//resPoints.push_back(intersectionPt);
|
|
|
}*/
|
|
|
|
|
|
|
|
|
if (findIntersection(linePt1.x,linePt1.y,linePt2.x,linePt2.y,pt1.x,pt1.y,pt2.x,pt2.y,intersectionPt))
|
|
|
{
|
|
|
resPoints.push_back(intersectionPt);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
if (resPoints.size()>1)
|
|
|
{
|
|
|
//获取最左或者最右的两个点,忽略凹多边形中间交点
|
|
|
double minX = resPoints[0].x;
|
|
|
double maxX = resPoints[0].x;
|
|
|
int minIndex = 0;
|
|
|
int maxIndex = 0;
|
|
|
|
|
|
for (int i=0;i<resPoints.size();++i) {
|
|
|
if (resPoints[i].x < minX) minIndex = i;
|
|
|
if (resPoints[i].x > maxX) maxIndex = i;
|
|
|
}
|
|
|
result.push_back(resPoints[minIndex]);
|
|
|
result.push_back(resPoints[maxIndex]);
|
|
|
}
|
|
|
|
|
|
return resPoints.size();
|
|
|
|
|
|
}
|
|
|
|
|
|
// 判断两条线段是否相交
|
|
|
int TopologicalAnalysis::isLineIntersecting(const Line2D& l1, const Line2D& l2, Point2D& intersection) {
|
|
|
float numera = (l2.p2.x-l2.p1.x) * (l1.p1.y-l2.p1.y) - (l2.p2.y-l2.p1.y) * (l1.p1.x-l2.p1.x);
|
|
|
float numerb = (l1.p2.x-l1.p1.x) * (l1.p1.y-l2.p1.y) - (l1.p2.y-l1.p1.y) * (l1.p1.x-l2.p1.x);
|
|
|
|
|
|
float denom = (l2.p2.y-l2.p1.y) * (l1.p2.x-l1.p1.x) - (l2.p2.x-l2.p1.x) * (l1.p2.y-l1.p1.y);
|
|
|
|
|
|
if(denom == 0.0f)
|
|
|
{
|
|
|
if(numera == 0.0f && numerb == 0.0f)
|
|
|
{
|
|
|
intersection.x = l2.p2.x;
|
|
|
intersection.y = l2.p2.y;
|
|
|
return 2; //重合
|
|
|
}
|
|
|
return 3; //平行
|
|
|
}
|
|
|
|
|
|
float ua = numera / denom;
|
|
|
float ub = numerb / denom;
|
|
|
|
|
|
if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f)
|
|
|
{
|
|
|
intersection.x = l1.p1.x + ua*(l1.p2.x - l1.p1.x);
|
|
|
intersection.y = l1.p1.y + ua*(l1.p2.y - l1.p1.y);
|
|
|
|
|
|
/*
|
|
|
double a1 = l1.p2.y - l1.p1.y;
|
|
|
double b1 = l1.p1.x - l1.p2.x;
|
|
|
double c1 = l1.p2.x * l1.p1.y - l1.p1.x * l1.p2.y;
|
|
|
|
|
|
double a2 = l2.p2.y - l2.p1.y;
|
|
|
double b2 = l2.p1.x - l2.p2.x;
|
|
|
double c2 = l2.p2.x * l2.p1.y - l2.p1.x * l2.p2.y;
|
|
|
double det = a1 * b2 - a2 * b1;
|
|
|
|
|
|
intersection.x = (b2 * c1 - b1 * c2) / det;
|
|
|
intersection.y = (a1 * c2 - a2 * c1) / det;*/
|
|
|
|
|
|
return 1; //相交
|
|
|
}
|
|
|
|
|
|
return 0; //不相交
|
|
|
}
|
|
|
|
|
|
//计算多边形最小宽度
|
|
|
int TopologicalAnalysis::getLineWithPolygonMinWidth(const vector<double>& polygonX,const vector<double>& polygonY)
|
|
|
{
|
|
|
int n = polygonX.size();
|
|
|
double minWidth = INT64_MAX;
|
|
|
int lineID = 0;
|
|
|
|
|
|
for (int i=0;i<n-1;++i) //遍历每一条边
|
|
|
{
|
|
|
int startID = i;
|
|
|
int endID = i + 1;
|
|
|
double width = 0;
|
|
|
for (int j=0;j<n-1;++j) //计算除边两个顶点外多边形其他顶点到直线的距离
|
|
|
{
|
|
|
if(startID == j || endID == j || (endID== n-1 && j==0)) continue;
|
|
|
//计算垂足点
|
|
|
double linePt1[2] = {polygonX[startID],polygonY[startID]};
|
|
|
double linePt2[2] = {polygonX[endID],polygonY[endID]};
|
|
|
double targetPt[2] = {0.0,0.0};
|
|
|
double pt[2] = {polygonX[j],polygonY[j]};
|
|
|
GetPointToLineVerticalCross(linePt1,linePt2,pt,targetPt);
|
|
|
//计算距离
|
|
|
double dist;
|
|
|
CalculateTwoPtsDistance(dist,pt[0],pt[1],targetPt[0],targetPt[1],3);
|
|
|
if(dist > width) width = dist;
|
|
|
}
|
|
|
if(width < minWidth)
|
|
|
{
|
|
|
minWidth = width;
|
|
|
lineID = startID;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return lineID;
|
|
|
}
|
|
|
|
|
|
//判断点与直线的位置关系
|
|
|
int TopologicalAnalysis::pointPosition(const Point2D& pt,const Line2D& line)
|
|
|
{
|
|
|
double cross = crossProduct(line.p1, line.p2, pt);
|
|
|
if (cross > 0) {
|
|
|
return 1; //左侧
|
|
|
} else if (cross < 0) {
|
|
|
return -1; //右侧
|
|
|
} else {
|
|
|
return 0; //线上
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
|
|
// 判断点P是否在多边形polygon内
|
|
|
bool TopologicalAnalysis::isPointInPolygon(const Point2D& P, vector<double>& regionLons,vector<double>& regionLats) {
|
|
|
int n = regionLons.size();
|
|
|
bool inside = false;
|
|
|
double xints;
|
|
|
for(int i=0, j=n-1; i<n; j=i++) {
|
|
|
double xi = regionLons[i], yi = regionLats[i];
|
|
|
double xj = regionLons[j], yj = regionLats[j];
|
|
|
|
|
|
// 点在多边形的顶点上也是一种特殊情况，这里简化处理未包含
|
|
|
// 检查射线是否与当前边相交
|
|
|
if(((yi > P.y) != (yj > P.y)) && // 边的两端点在射线两侧
|
|
|
(P.x < (xj - xi) * (P.y - yi) / (yj - yi) + xi)) { // 射线与边相交的条件
|
|
|
inside = !inside; // 交点数加一，改变inside状态
|
|
|
}
|
|
|
}
|
|
|
return inside;
|
|
|
}
|
|
|
|
|
|
//直线与线段的交点
|
|
|
bool TopologicalAnalysis::findIntersection(double x1, double y1, double x2, double y2, // 直线1的两个点
|
|
|
double x3, double y3, double x4, double y4,Point2D& intersection) { // 线段的两个端点
|
|
|
// 计算直线1的方向向量
|
|
|
double dx1 = x2 - x1;
|
|
|
double dy1 = y2 - y1;
|
|
|
|
|
|
// 计算线段的方向向量
|
|
|
double dx2 = x4 - x3;
|
|
|
double dy2 = y4 - y3;
|
|
|
|
|
|
// 计算向量积，判断是否平行（即无交点）
|
|
|
double cross = -dx1 * dy2 + dy1 * dx2;
|
|
|
if (cross == 0) return false;
|
|
|
|
|
|
// 计算参数t1（直线1上的点）和t2（线段上的点）
|
|
|
double t1 = (dx2 * (y3 - y1) - dy2 * (x3 - x1)) / cross;
|
|
|
double t2 = (dx1 * (y3 - y1) - dy1 * (x3 - x1)) / cross;
|
|
|
|
|
|
// 判断t2是否在线段上
|
|
|
if (t2 >= 0 && t2 <= 1) {
|
|
|
// 计算并返回交点坐标
|
|
|
intersection.x = x1 + t1 * dx1;
|
|
|
intersection.y = y1 + t1 * dy1;
|
|
|
return true;
|
|
|
} else {
|
|
|
// 如果t2不在[0, 1]区间内，说明不相交于线段上
|
|
|
return false;
|
|
|
}
|
|
|
} |