admin 发表于 2024-6-21 17:02:47

计算几何-求线段交点算法和代码(C++语言)

//跨立判断
bool isLineSegmentCross(const Point &P1,const Point &P2,const Point &Q1,const Point &Q2)
{
    if(
      ((Q1.x-P1.x)*(Q1.y-Q2.y)-(Q1.y-P1.y)*( Q1.x-Q2.x)) * ((Q1.x-P2.x)*(Q1.y-Q2.y)-(Q1.y-P2.y)*(Q1.x-Q2.x)) < 0 &&
      ((P1.x-Q1.x)*(P1.y-P2.y)-(P1.y-Q1.y)*(P1.x-P2.x)) * ((P1.x-Q2.x)*(P1.y-P2.y)-(P1.y-Q2.y)*( P1.x-P2.x)) < 0
    )
      return true;
    else
       return false;
}







#include<stdio.h>
#define N 10002

/**
算法适用于整形点,不适用于浮点型
**/

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

double min(int x, int y)
{
    return x<y?x:y;
}

double max(int x, int y)
{
    return x>y?x:y;
}

//排斥实验
bool IsRectCross(const Point &p1,const Point &p2,const Point &q1,const Point &q2)
{
    bool ret = min(p1.x,p2.x) <= max(q1.x,q2.x)    &&
                min(q1.x,q2.x) <= max(p1.x,p2.x) &&
                min(p1.y,p2.y) <= max(q1.y,q2.y) &&
                min(q1.y,q2.y) <= max(p1.y,p2.y);
    return ret;
}

/**这段代码不能得到正确答案,故注释
//跨立判断
bool IsLineSegmentCross(const Point &pFirst1,const Point &pFirst2,const Point &pSecond1,const Point &pSecond2)
{
    long line1,line2;
    line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
      pFirst2.x * (pFirst1.y - pSecond1.y) +
      pSecond1.x * (pFirst2.y - pFirst1.y);
    line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
      pFirst2.x * (pFirst1.y - pSecond2.y) +
      pSecond2.x * (pFirst2.y - pFirst1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
      return false;

    line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
      pSecond2.x * (pSecond1.y - pFirst1.y) +
      pFirst1.x * (pSecond2.y - pSecond1.y);
    line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
      pSecond2.x * (pSecond1.y - pFirst2.y) +
      pFirst2.x * (pSecond2.y - pSecond1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
      return false;
    return true;
}
**/

//跨立判断
bool IsLineSegmentCross(const Point &P1,const Point &P2,const Point &Q1,const Point &Q2)
{
    if(
      ((Q1.x-P1.x)*(Q1.y-Q2.y)-(Q1.y-P1.y)*( Q1.x-Q2.x)) * ((Q1.x-P2.x)*(Q1.y-Q2.y)-(Q1.y-P2.y)*(Q1.x-Q2.x)) < 0 ||
      ((P1.x-Q1.x)*(P1.y-P2.y)-(P1.y-Q1.y)*(P1.x-P2.x)) * ((P1.x-Q2.x)*(P1.y-P2.y)-(P1.y-Q2.y)*( P1.x-P2.x)) < 0
    )
      return true;
    else
       return false;
}

/**
求线段P1P2与Q1Q2的交点。
先进行快速排斥实验和跨立实验确定有交点再进行计算。
交点(x,y)使用引用返回。
没有验证过
**/
bool GetCrossPoint(const Point &p1,const Point &p2,const Point &q1,const Point &q2,long &x,long &y)
{
    if(IsRectCross(p1,p2,q1,q2))
    {
      if (IsLineSegmentCross(p1,p2,q1,q2))
      {
            //求交点
            long tmpLeft,tmpRight;
            tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
            tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);

            x = (int)((double)tmpRight/(double)tmpLeft);

            tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
            tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
            y = (int)((double)tmpRight/(double)tmpLeft);
            return true;
      }
    }
    return false;
}




#include <stdio.h>
#include <math.h>
const int N = 100010;
int mark;
struct Point
{
    double x,y;
};
struct stline
{
    Point a,b;
} line1,line2, p;

int dblcmp(double a,double b)
{
    if (fabs(a-b)<=1E-6) return 0;
    if (a>b) return 1;
    else return -1;
}
//***************点积判点是否在线段上***************
double dot(double x1,double y1,double x2,double y2) //点积
{
    return x1*x2+y1*y2;
}

int point采用on采用line(Point a,Point b,Point c) //求a点是不是在线段bc上,>0不在,=0与端点重合,<0在。
{
    return dblcmp(dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y),0);
}
//**************************************************
double cross(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}
double ab采用cross采用ac(Point a,Point b,Point c) //ab与ac的叉积
{
    return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int ab采用cross采用cd (Point a,Point b,Point c,Point d) //求ab是否与cd相交,交点为p。1规范相交,0交点是一线段的端点,-1不相交。
{
    double s1,s2,s3,s4;
    int d1,d2,d3,d4;
    Point p;
    d1=dblcmp(s1=ab采用cross采用ac(a,b,c),0);
    d2=dblcmp(s2=ab采用cross采用ac(a,b,d),0);
    d3=dblcmp(s3=ab采用cross采用ac(c,d,a),0);
    d4=dblcmp(s4=ab采用cross采用ac(c,d,b),0);

//如果规范相交则求交点
    if ((d1^d2)==-2 && (d3^d4)==-2)
    {
      p.x=(c.x*s2-d.x*s1)/(s2-s1);
      p.y=(c.y*s2-d.y*s1)/(s2-s1);
      return 1;
    }

//如果不规范相交
    if (d1==0 && point采用on采用line(c,a,b)<=0)
    {
      p=c;
      return 0;
    }
    if (d2==0 && point采用on采用line(d,a,b)<=0)
    {
      p=d;
      return 0;
    }
    if (d3==0 && point采用on采用line(a,c,d)<=0)
    {
      p=a;
      return 0;
    }
    if (d4==0 && point采用on采用line(b,c,d)<=0)
    {
      p=b;
      return 0;
    }
//如果不相交
    return -1;
}

admin 发表于 2024-6-21 17:03:24

Point getCrossPoint(Segment s1, Segment s2) {
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1));
    double d2 = abs(cross(base, s1.p2 - s2.p1));
    double t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}

admin 发表于 2024-6-21 17:03:33

#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {//Point类,点
    public:
      double x, y;
      
      Point(double x = 0, double y = 0): x(x), y(y) {}

      Point operator + (Point p) { return Point(x + p.x, y + p.y); }
      Point operator - (Point p) { return Point(x - p.x, y - p.y); }
      Point operator * (double a) { return Point(a * x, a * y); }
      Point operator / (double a) { return Point(x / a, y / a); }

      double abs() { return sqrt(norm()); }
      double norm() { return x * x + y * y; }
      
      bool operator < (const Point &p) const {
            return x != p.x ? x < p.x : y < p.y;
      }

      bool operator == (const Point &p) const {
            return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
      }
};

typedef Point Vector;//Vector类,向量

struct Segment{//Segment 线段
    Point p1, p2;
};
double dot(Vector a, Vector b) {//内积
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {//外积
    return a.x*b.y - a.y*b.x;
}

Point getCrossPoint(Segment s1, Segment s2) {
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1));
    double d2 = abs(cross(base, s1.p2 - s2.p1));
    double t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}

int main(){
    int q;
    cin>>q;
   
    Segment s1, s2;
    Point p;
   
    while(q--){
      cin>>s1.p1.x>>s1.p1.y>>s1.p2.x>>s1.p2.y>>s2.p1.x>>s2.p1.y>>s2.p2.x>>s2.p2.y;
      p = getCrossPoint(s1, s2);
      printf("%.10f %.10f\n", p.x, p.y);
    }
}
页: [1]
查看完整版本: 计算几何-求线段交点算法和代码(C++语言)