SegmentIntersection/main.cpp at dev · igor-240340/SegmentIntersection · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <vector>
#include <format>

#include "Vector3D.h"
#include "Segment3D.h"

int main() {
    std::vector<std::pair<Segment3D, Segment3D>> segment_pairs = { {
        //==========================================================================================================
        // Тестовый набор 1.
        //==========================================================================================================

        // Пересекаются.
        {{{3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378}},
         { {2.170290141320, 1.785736786724, -1.507768340365}, {-2.603739909326, 1.304588882860, 0.6068038707405} }},

        // Не пересекаются: CD целиком слева от AB.
        {{ {3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378} },
         { {6.313001564211, -2.091419462791, 2.942417242347}, {3.844839865637, -2.273521682871, 3.938105551464} }},

        // Не пересекаются: CD целиком снизу от AB.
        {{ {3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378} },
         { {-2.902738434974, 0.1844306756534, 2.334455941611}, {-4.963179777883, 1.094860157023, 1.610802213140} }},

        // Не пересекаются: лежат в разных плоскостях.
        {{ {3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378} },
         { {-8.321139238615, 2.436207175776, 7.634355077367}, {4.883365336783, -2.000000000000, -2.329341504218} }},

        // Пересекаются: CD перпендикулярен AB и проходит через точку B.
        {{ {3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378} },
         { {-1.286807011043, 4.852262803808, -2.364058234497}, {-1.917683054172, 1.727176561628, -4.499454632517} }},

        // Не пересекаются: CD лежит на одной прямой с AB и частично его перекрывает.
        {{ {3.785300280541, -1.130879193217, 2.283474013466}, {-1.525618163490, 3.669295951413, -3.172388936378} },
         { {-0.7605308233908, 2.977785947613, -2.386420988229}, {-2.328674509787, 4.395123537330, -3.997362133118} }},

        //==========================================================================================================
        // Тестовый набор 2.
        //==========================================================================================================

        // Не пересекаются: CD целиком сверху от AB.
        {{{3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714}},
         { {3.847829614693, 1.736948682494, 1.244100488943}, {1.685074501792, 2.047950199457, 2.411585585131} }},

        // Не пересекаются: CD целиком слева от AB.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {3.922341267448, 1.052104877598, 5.181979154610}, {3.201590631663, 1.049752517056, 6.196539480613} }},

        // Не пересекаются: CD целиком справа от AB.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {0.8983410534874, 2.374608771720, 1.576230100719}, {-0.5226936532978, 2.570727193611, 2.391858524502} }},

        // Не пересекаются: CD лежит на одной прямой с AB и частично его перекрывает.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {1.068980808088, 2.094804248415, 2.990470085499}, {0.07281663659392, 2.504850830843, 1.953804209388} }},

        // Пересекаются.
        {{{3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714}},
         { {2.056499677082, 1.836018849904, 3.146532100538}, {0.8156761120671, 2.013745953817, 3.820487160905} }},

        // Пересекаются.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {1.794117525956, 1.955664779483, 2.804777150453}, {-0.5125719584192, 2.530292687059, 2.616413653290} }},

        // Пересекаются: точка C лежит на AB, точка D лежит сверху от AB.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {2.022007496052, 1.702514154527, 3.982244608923}, {2.858304270535, 1.558157263857, 3.673007313696} }},

        // Пересекаются: точка C лежит на AB, точка D лежит снизу от AB.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {1.861022450712, 1.768779705481, 3.814714288276}, {1.174930042567, 1.777856164110, 4.713713111154} }},

        // Не пересекаются.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {0.4397302456305, 2.208264977324, 3.194568920376}, {0.5016925807770, 2.395911843553, 2.001219101122} }},

        // Пересекаются: CD перпендикулярен AB и проходит через точку A.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {1.774011320976, 1.383174905217, 6.211010356544}, {3.503606870708, 1.265759661039, 4.502545866460} }},

        //==========================================================================================================
        // Экстремальные случаи.
        //==========================================================================================================

        // Пересекаются: C и D лежат по разные стороны от AB на расстоянии близком к epsilon, но больше его.
        {{{3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714}},
         { {2.070247088639, 1.682657155061, 4.032447591784}, {1.561924925692, 1.891896285205, 3.503453742559} }},

        // Пересекаются: точки C и D лежат по разные стороны от AB на расстоянии от прямой меньше epsilon.
        // При этом векторное произведение оказывается не меньше epsilon.
        {{ {3, 1.299947493971, 5}, {0.6190385850161073, 2.280011944234971, 2.5222342643087714} },
         { {1.263401343741, 2.014775575953, 3.192796608513}, {1.033828003850, 2.109274215344, 2.953887011585} }},

        // Не пересекаются: расстояние между точками близко к epsilon, векторное произведение меньше epsilon.
        {{ {-0.1566433139811, 1.861043990594, -3.932079211389}, {-0.1566399964113, 1.861051608668, -3.932084246738} },
         { {-0.1566415810587, 1.861050003168, -3.932078538843}, {-0.1566420440209, 1.861044536974, -3.932084988262} }},

        // Пересекаются: точка пересечения вычисляется с большой абсолютной погрешностью.
        // Граничные значения взяты из диапазона float, а не double.
        {{ {std::pow(2, -126), 0.0, -std::pow(2, -126)}, {std::pow(2, 127), 0.0, std::pow(2, 127)}},
         { {std::pow(2, 127), 0.0, std::pow(2, -126)}, {std::pow(2, -126), 0.0, std::pow(2, 127)} }},
    } };

    for (const auto& segment_pair : segment_pairs) {
        std::optional<Vector3D> intersection_point = Segment3D::Intersect(segment_pair.first, segment_pair.second);
        if (intersection_point) {
            double x = (*intersection_point).X;
            double y = (*intersection_point).Y;
            double z = (*intersection_point).Z;
            std::cout << std::format("segments intersect at ({},{},{})\n", x, y, z);
        }
        else {
            std::cout << "segments does not intersect\n";
        }
    }

    return 0;
}