平面内，線與線兩條線找交點兩條線段的位置關系(相交)判定與交點求解 C#

個人親自編寫、測試，可以正常使用

道理看原文，這裡不多說

網上找到的幾篇基本都不能用的

C#代碼

bool Equal(float f1, float f2)
{
return (Math.Abs(f1 - f2) < 1f);
}
bool dayu(Point p1, Point p2)////比較兩點坐标大小，先比較x坐标，若相同則比較y坐标
{
return (p1.X > p2.X || (Equal(p1.X , p2.X) && p1.Y > p2.Y));
}
bool dengyu(Point p1, Point p2)////判斷兩點是否相等
{
return (Equal(p1.X, p2.X) && Equal(p1.Y, p2.Y));
}
float ji(Point p1, Point p2)////計算兩向量外積
{
return (p1.X * p2.Y - p1.Y * p2.X);
}

//判定兩線段位置關系，并求出交點(如果存在)。傳回值列舉如下：
//[有重合] 完全重合(6)，1個端點重合且共線(5)，部分重合(4)
//[無重合] 兩端點相交(3)，交于線上(2)，正交(1)，無交(0)，參數錯誤(-1)
int Intersection(Point p1, Point p2, Point p3, Point p4, ref Point point) {
//保證參數p1!=p2，p3!=p4
if (p1 == p2 || p3 == p4) {
return -1; //傳回-1代表至少有一條線段首尾重合，不能構成線段
}
//為友善運算，保證各線段的起點在前，終點在後。
if (dayu(p1,p2))
{
Point pTemp = p1;
p1 = p2;
p2 = pTemp;
// swap(p1, p2);
}
if (dayu(p3, p4)) {
Point pTemp = p3;
p3 = p4;
p4 = pTemp;
//swap(p3, p4);
}
//判定兩線段是否完全重合
if (p1 == p3 && p2 == p4) {
return 6;
}
//求出兩線段構成的向量
Point v1 = new Point(p2.X - p1.X, p2.Y - p1.Y), v2 = new Point(p4.X - p3.X, p4.Y - p3.Y);
//求兩向量外積，平行時外積為0
float Corss = ji(v1, v2);
//如果起點重合
if (dengyu(p1,p3))
{
point = p1;
//起點重合且共線(平行)傳回5；不平行則交于端點，傳回3
return (Equal(Corss, 0) ? 5 : 3);
}
//如果終點重合
if (dengyu(p2,p4)) {
point = p2;
//終點重合且共線(平行)傳回5；不平行則交于端點，傳回3
return (Equal(Corss, 0) ? 5 : 3);
}
//如果兩線端首尾相連
if (dengyu(p1,p4)) {
point = p1;
return 3;
}
if (dengyu(p2, p3)) {
point = p2;
return 3;
}//經過以上判斷，首尾點相重的情況都被排除了
//将線段按起點坐标排序。若線段1的起點較大，則将兩線段交換
if(dayu(p1,p3))
{
Point pTemp = p1;
p1 = p3;
p3 = pTemp;

pTemp = p2;
p2 = p4;
p4 = pTemp;

pTemp = v1;
v1 = v2;
v2 = pTemp;
//swap(p1, p3);
//swap(p2, p4);
//更新原先計算的向量及其外積
//swap(v1, v2);
Corss= ji(v1, v2);
}
//處理兩線段平行的情況
if(Equal(Corss,0)){
//做向量v1(p1, p2)和vs(p1,p3)的外積，判定是否共線
Point vs =newPoint(p3.X - p1.X, p3.Y - p1.Y);
//外積為0則兩平行線段共線，下面判定是否有重合部分
if(Equal(ji(v1, vs),0)){
//前一條線的終點大于後一條線的起點，則判定存在重合
if(dayu(p2, p3)){
point = p3;
return4;//傳回值4代表線段部分重合
}
}//若三點不共線，則這兩條平行線段必不共線。
//不共線或共線但無重合的平行線均無交點
return0;
}//以下為不平行的情況，先進行快速排斥試驗
//x坐标已有序，可直接比較。y坐标要先求兩線段的最大和最小值
float ymax1 = p1.Y, ymin1 = p2.Y, ymax2 = p3.Y, ymin2 = p4.Y;
if(ymax1 < ymin1){
float fTemp = ymax1;
ymax1 = ymin1;
ymin1 = fTemp;
//swap(ymax1, ymin1);
}
if(ymax2 < ymin2){
//swap(ymax2, ymin2);
float fTemp = ymax2;
ymax2 = ymin2;
ymin2 = fTemp;
}
//如果以兩線段為對角線的矩形不相交，則無交點
if(p1.X > p4.X || p2.X < p3.X || ymax1 < ymin2 || ymin1 > ymax2)
{
return0;
}//下面進行跨立試驗
Point vs1 =newPoint(p1.X - p3.X, p1.Y - p3.Y), vs2 =newPoint(p2.X - p3.X, p2.Y - p3.Y);
Point vt1 =newPoint(p3.X - p1.X, p3.Y - p1.Y), vt2 =newPoint(p4.X - p1.X, p4.Y - p1.Y);
float s1v2, s2v2, t1v1, t2v1;
//根據外積結果判定否交于線上
if(Equal(s1v2 = ji(vs1, v2),0)&& dayu(p4, p1)&& dayu(p1, p3)){
point = p1;
return2;
}
if(Equal(s2v2 = ji(vs2 ,v2),0)&& dayu(p4 ,p2)&& dayu(p2 , p3)){
point = p2;
return2;
}
if(Equal(t1v1 = ji(vt1 , v1),0)&& dayu(p2 , p3)&& dayu(p3, p1)){
point = p3;
return2;
}
if(Equal(t2v1 = ji(vt2 , v1),0)&& dayu(p2 , p4)&& dayu(p4 , p1)){
point = p4;
return2;
}//未交于線上，則判定是否相交
if(s1v2 * s2v2 >0|| t1v1 * t2v1 >0){
return0;
}//以下為相交的情況，算法詳見文檔
//計算二階行列式的兩個常數項
floatConA= p1.X * v1.Y - p1.Y * v1.X;
floatConB= p3.X * v2.Y - p3.Y * v2.X;
//計算行列式D1和D2的值，除以系數行列式的值，得到交點坐标
point.X =(int)((ConB* v1.X -ConA* v2.X)/Corss);
point.Y =(int)((ConB* v1.Y -ConA* v2.Y)/Corss);
//正交傳回1
return1;
}

參考

http://www.cnblogs.com/devymex/archive/2010/08/19/1803885.html

概念

平面内兩條線段位置關系的判定在很多領域都有着廣泛的應用，比如遊戲、CAD、圖形處理等，而兩線段交點的求解又是該算法中重要的一環。本文将盡可能用通俗的語言詳細的描述一種主流且性能較高的判定算法。

外積，又稱叉積，是向量代數（解析幾何）中的一個概念。兩個二維向量v1(x1, y1)和v2(x2, y2)的外積v1×v2=x1y2-y1x2。如果由v1到v2是順時針轉動，外積為負，反之為正，為0表示二者方向相同（平行）。此外，文中涉及行例式和方程組的概念，請參閱線性代數的相關内容。

為友善計算，對坐标點的大小比較作如下定義：x坐标較大的點為大，x坐标相等但y坐标較大的為大，x與y都相等的點相等。一條線段中較小的一端為起點，較大的一端為終點。

問題

給定兩條線段的端點坐标，求其位置關系，并求出交點（如果存在）。

分析

兩條線段的位置關系大體上可以分為三類：有重合部分、無重合部分但有交點（相交）、無交點。為避免精度問題，首先要将所有存在重合的情況排除。

重合可分為：完全重合、一端重合、部分重合三種情況。顯然，兩條線段的起止點都相同即為完全重合；隻有起點相同或隻有終點相同的為一端重合（注意：坐标較小的一條線段的終點與坐标較大的一條線段的起點相同時應判定為相交）。要判斷是否部分重合，必須先判斷是否平行。設線段L1(p1->p2)和L2(p3->p4)，其中p1(x1, y1)為第一條線段的起點，p2(x2, y2)為第一條線段的終點，p3(x3, y3)為第二條線段的起點，p4(x4, y4)為第二段線段的終點，由此可構造兩個向量：

v1(x2-x1, y2-y1)，v2(x4-x3, y4-y3)

若v1與v2的外積v1×v2為0，則兩條線段平行，有可能存在部分重合。再判斷兩條平行線段是否共線，方法是用L1的一端和L2的一端構成向量vs并與v2作外積，如果vs與v2也平行則兩線段共線（三點共線）。在共線的前提下，若起點較小的線段終點大于起點較大的線段起點，則判定為部分重合。

沒有重合，就要判定兩條線是否相交，主要的算法還是依靠外積。然而外積的計算開銷比較大，如果不相交的情況比較多，可先做快速排斥實驗：将兩條線段視為兩個矩形的對角線，并構造出這兩個矩形。如果這兩個矩形沒有重疊部分（x坐标相離或y坐标相離）即可判定為不相交。

然後執行跨立試驗。兩條相交的線段必然互相跨立，簡單的講就是p1和p2兩點位于L2的兩側且p3和p4兩點位于L1的兩側，這樣就可利用外積做出判斷了。分别構造向量s1(p3, p1), s2(p3, p2)，如果s1×v2與s2×v2異号(s1->v2與s2->v2轉動的方向相反），則說明p1和p2位于L2的兩側。同理可判定p3和p4是否跨立L1。如果上述四個叉積中任何一個等于0，則說明一條線段的端點在另一條線上。

當判定兩條線段相交後，就可以進行交點的求解了。當然，求交點可以用平面幾何方法，列點斜式方程來完成。但這樣作會難以處理斜率為0的特殊情況，且運算中會出現多次除法，很難保證精度。這裡将使用向量法求解。

設交點為(x0, y0)，則下列方程組必然成立：

x0-x1=k1(x2-x1)
y0-y1=k1(y2-y1)
x0-x3=k2(x4-x3)
y0-y3=k2(y4-y3)

其中k1和k2為任意不為0的常數（若為0，則說明有重合的端點，這種情況在上面已經被排除了）。1式與2式聯系，3式與4式聯立，消去k1和k2可得：

x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)
x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3)

将含有未知數x0和y0的項移到左邊，常數項移動到右邊，得：

(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1
(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3

設兩個常數項分别為b1和b2：

b1=(y2-y1)x1+(x1-x2)y1
b2=(y4-y3)x3+(x3-x4)y3

系數行列式為D，用b1和b2替換x0的系數所得系數行列式為D1，替換y0的系數所得系數行列式為D2，則有：

|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)
|D1|=b2(x2-x1)-b1(x4-x3)
|D2|=b2(y2-y1)-b1(y4-y3)

由此，可求得交點坐标為：

x0=|D1|/|D|, y0=|D2|/|D|

解畢。

C++/STL實作

#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
    return (abs(f1 - f2) < 1e-4f);
}
//判斷兩點是否相等
bool operator==(const POINTF &p1, const POINTF &p2) {
    return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
//比較兩點坐标大小，先比較x坐标，若相同則比較y坐标
bool operator>(const POINTF &p1, const POINTF &p2) {
    return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
//計算兩向量外積
float operator^(const POINTF &p1, const POINTF &p2) {
    return (p1.x * p2.y - p1.y * p2.x);
}
//判定兩線段位置關系，并求出交點(如果存在)。傳回值列舉如下：
//[有重合] 完全重合(6)，1個端點重合且共線(5)，部分重合(4)
//[無重合] 兩端點相交(3)，交于線上(2)，正交(1)，無交(0)，參數錯誤(-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
    //保證參數p1!=p2，p3!=p4
    if (p1 == p2 || p3 == p4) {
        return -1; //傳回-1代表至少有一條線段首尾重合，不能構成線段
    }
    //為友善運算，保證各線段的起點在前，終點在後。
    if (p1 > p2) {
        swap(p1, p2);
    }
    if (p3 > p4) {
        swap(p3, p4);
    }
    //判定兩線段是否完全重合
    if (p1 == p3 && p2 == p4) {
        return 6;
    }
    //求出兩線段構成的向量
    POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
    //求兩向量外積，平行時外積為0
    float Corss = v1 ^ v2;
    //如果起點重合
    if (p1 == p3) {
        Int = p1;
        //起點重合且共線(平行)傳回5；不平行則交于端點，傳回3
        return (Equal(Corss, 0) ? 5 : 3);
    }
    //如果終點重合
    if (p2 == p4) {
        Int = p2;
        //終點重合且共線(平行)傳回5；不平行則交于端點，傳回3
        return (Equal(Corss, 0) ? 5 : 3);
    }
    //如果兩線端首尾相連
    if (p1 == p4) {
        Int = p1;
        return 3;
    }
    if (p2 == p3) {
        Int = p2;
        return 3;
    }//經過以上判斷，首尾點相重的情況都被排除了
    //将線段按起點坐标排序。若線段1的起點較大，則将兩線段交換
    if (p1 > p3) {
        swap(p1, p3);
        swap(p2, p4);
        //更新原先計算的向量及其外積
        swap(v1, v2);
        Corss = v1 ^ v2;
    }
    //處理兩線段平行的情況
    if (Equal(Corss, 0)) {
        //做向量v1(p1, p2)和vs(p1,p3)的外積，判定是否共線
        POINTF vs = {p3.x - p1.x, p3.y - p1.y};
        //外積為0則兩平行線段共線，下面判定是否有重合部分
        if (Equal(v1 ^ vs, 0)) {
            //前一條線的終點大于後一條線的起點，則判定存在重合
            if (p2 > p3) {
                Int = p3;
                return 4; //傳回值4代表線段部分重合
            }
        }//若三點不共線，則這兩條平行線段必不共線。
        //不共線或共線但無重合的平行線均無交點
        return 0;
    } //以下為不平行的情況，先進行快速排斥試驗
    //x坐标已有序，可直接比較。y坐标要先求兩線段的最大和最小值
    float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
    if (ymax1 < ymin1) {
        swap(ymax1, ymin1);
    }
    if (ymax2 < ymin2) {
        swap(ymax2, ymin2);
    }
    //如果以兩線段為對角線的矩形不相交，則無交點
    if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
        return 0;
    }//下面進行跨立試驗
    POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
    POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
    float s1v2, s2v2, t1v1, t2v1;
    //根據外積結果判定否交于線上
    if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
        Int = p1;
        return 2;
    }
    if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
        Int = p2;
        return 2;
    }
    if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
        Int = p3;
        return 2;
    }
    if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
        Int = p4;
        return 2;
    } //未交于線上，則判定是否相交
    if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
        return 0;
    } //以下為相交的情況，算法詳見文檔
    //計算二階行列式的兩個常數項
    float ConA = p1.x * v1.y - p1.y * v1.x;
    float ConB = p3.x * v2.y - p3.y * v2.x;
    //計算行列式D1和D2的值，除以系數行列式的值，得到交點坐标
    Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
    Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
    //正交傳回1
    return 1;
}
//主函數
int main(void) {
    //随機生成100個測試資料
    for (int i = 0; i < 100; ++i) {
        POINTF p1, p2, p3, p4, Int;
        p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
        p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
        p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
        p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
        int nr = Intersection(p1, p2, p3, p4, Int);
        cout << "[(";
        cout << (int)p1.x << ',' << (int)p1.y << "),(";
        cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
        cout << (int)p3.x << ',' << (int)p3.y << "),(";
        cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
        cout << nr;
        if (nr > 0) {
            cout << '(' << Int.x << ',' << Int.y << ')';
        }
        cout << endl;
    }
    return 0;
}

作者：王雨濛；新浪微網誌：@吉祥村碼農；來源：《程式控》部落格 -- http://www.cnblogs.com/devymex/

此文章版權歸作者所有（有特别聲明的除外)，轉載必須注明作者及來源。您不能用于商業目的也不能修改原文内容。

平面内，線與線兩條線找交點兩條線段的位置關系(相交)判定與交點求解 C#

概念

問題

分析

C++/STL實作

繼續閱讀

Unity3D中背景音樂和相關音效的添加，背景音樂暫停、停止和播放的設定

Unity遊戲開發背景知識

vs編譯完提示不支援嘗試的執行操作

【C# MySQL】第一次使用C#對MySQL進行操作的心得

C#基礎——與C#的第一次邂逅聲明：IDE：第一個C#果實：Console淺析：總結：

英文月日年日期格式的實作

C# 位元組數組 byte[] 快速比較算法

C# 位元組數組、字元串轉化位元組數組轉字元串字元串轉位元組數組位元組數組轉整數整數轉位元組數組字元串轉位元組字元串轉數值數值轉字元串

C#用Zlib壓縮或解壓縮位元組數組

C# 比較兩個位元組數組是否相等

對于VS中scanf報錯永久解決，建立源檔案自動添加#define _CRT_SECURE_NO_WARNINGS 1

《C#進階程式設計》讀書筆記 -索引

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

C#多線程——前台線程和背景線程

C#+ArcEngine代碼檢測ArcEngine Runtime是否安裝以及是否授權

七牛雲-C#SDK-上傳-前期準備

平面内，線與線 兩條線找交點 兩條線段的位置關系(相交)判定與交點求解 C#

概念

問題

分析

C++/STL實作

繼續閱讀

平面内，線與線兩條線找交點兩條線段的位置關系(相交)判定與交點求解 C#