Inoltre, perché la cosa funzioni, la stessa verifica deve essere fatta a parti invertite. Infatti (come si può notare nell'immagine di seguito) la sola verifica del segmento $AB$ rispetto ai vertici di $CD$ non è sufficiente. Quindi lo stesso deve valere per il segmento $CD$ rispetto ai vertici di $AB$.
Dal punto di vista computazionale si può sfruttare quanto in visto in [5] e [6]. Infatti il determinante delle componenti delle coordinate omogenee di tre vertici $a, b, c$ è l'area con segno del parallelogramma descritto dai due vettori $(b - a)$ e $(c - a)$. Se il segno è positivo i tre vertici sono in ordine antiorario, altrimenti, se il segno è negativo, saranno in ordine orario. Quindi, prendendo ancora come esempio i due segmenti visti nella prima figura, se l'area di $\triangle ABC$ ha segno positivo $C$ si trova a sinistra di $AB$ altrimenti, se l'area ha segno negativo, si troverà a destra.
Infine non resta che valutare il caso in cui uno qualsiasi dei vertici di uno dei due segmenti si trova sull'altro segmento. In questo caso è sufficiente verificare che ognuno dei due vertici di uno dei due segmenti si trovi sulla retta descritta dai due vertici dell'altro segmento.
Per quanto riguarda l'implementazione in codice C/C++ l'unica reale difficoltà è rappresentata dal possibile uso di numeri floating point. Per la comparazione di numeri in virgola mobile si può optare per uno dei metodi presentati in [3] o [4], scelto in base alle proprie esigenze e al livello di robustezza richiesto dal contesto applicativo. Il resto del codice è relativamente intuitivo.
/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono una maggiore semplificazione.*/ #include <iostream> #include <cfloat> #include <cmath> typedef float Vertex_Coord[2]; struct vertex_node { int vnum; Vertex_Coord pos; }; bool left(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); bool left_on(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); bool collinear(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); bool AlmostEqual(float, float, float); bool proper_intersect(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); bool between(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); bool intersect(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); float area2(const Vertex_Coord, const Vertex_Coord, const Vertex_Coord); inline float max_3(float a, float b, float c) { return ((a > b) ? ((a > c) ? a : c) : (b > c) ? b : c); } int main(int argc, char* argv[], char* env[]) { // segmenti che si intersecano propriamente Vertex_Coord AB[] = { {-1.0, -1.0}, {1.0, 1.0} }; Vertex_Coord CD[] = { {1.0, -1.0}, {-1.0, 1.0} }; std::cout << "I due segmenti " << (intersect(AB[0], AB[1], CD[0], CD[1]) ? "si" : "non si") << " intersecano." << std::endl; // segmenti che non si intersecano AB[0][0] = -1.0; AB[0][1] = -1.0; AB[1][0] = 1.0; AB[1][1] = 1.0; CD[0][0] = 1.5; CD[0][0] = -1.5; CD[1][0] = 0.0; CD[1][1] = 3.0; std::cout << "I due segmenti " << (intersect(AB[0], AB[1], CD[0], CD[1]) ? "si" : "non si") << " intersecano." << std::endl; // segmenti che si intersecano in punto che è vertice di uno dei due segmenti AB[0][0] = -1.0; AB[0][1] = -1.0; AB[1][0] = 1.0; AB[1][1] = 1.0; CD[0][0] = 0.0; CD[0][0] = -0.0; CD[1][0] = -1.0; CD[1][1] = 1.0; std::cout << "I due segmenti " << (intersect(AB[0], AB[1], CD[0], CD[1]) ? "si" : "non si") << " intersecano." << std::endl; // segmenti che si intersecano in punto che è vertice di entrambi i segmenti AB[0][0] = -1.0; AB[0][1] = -1.0; AB[1][0] = 1.0; AB[1][1] = 1.0; CD[0][0] = 1.0; CD[0][0] = -1.0; CD[1][0] = -0.0; CD[1][1] = 3.0; std::cout << "I due segmenti " << (intersect(AB[0], AB[1], CD[0], CD[1]) ? "si" : "non si") << " intersecano." << std::endl; return 0; } bool intersect(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c, const Vertex_Coord d) { if (proper_intersect(a, b, c, d)) return true; else if (between(a, b, c) || between(a, b, d) || between(c, d, a) || between(c, d, b)) return true; else return false; return (left(a, b, c) xor left(a, b, d)) && (left(c, d, a) xor left(c, d, b)); } bool between(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c) { if (!collinear(a, b, c)) return false; if (a[0] != b[0]) return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0])); else return ((a[1] <= c[1]) && (c[1] <= b[1])) || ((a[1] >= c[1]) && (c[1] >= b[1])); } bool proper_intersect(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c, const Vertex_Coord d) { if (collinear(a, b, c) || collinear(a, b, d) || collinear(c, d, a) || collinear(c, d, b)) return false; return (left(a, b, c) xor left(a, b, d)) && (left(c, d, a) xor left(c, d, b)); } bool AlmostEqual(float a, float b, float epsilon = FLT_EPSILON) { if (fabs(a - b) <= epsilon * max_3(1.0f, fabs(a), fabs(b))) return true; return false; } bool left(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c) { return area2(a, b, c) > 0.0f; } bool left_on(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c) { return area2(a, b, c) >= 0.0f; } bool collinear(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c) { return AlmostEqual(area2(a, b, c), 0.0f); } float area2(const Vertex_Coord a, const Vertex_Coord b, const Vertex_Coord c) { return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]); }
Riferimenti:
[1] Computational Geometry in C - O'Rourke
[2] Elementi di Geometria Computazionale
[3] Real-time Collision Detection - Ericson
[4] Comparing Floating Point Numbers, 2012 Edition
[5] Area di un poligono
[6] Collinearità di tre punti in 2D
Nessun commento:
Posta un commento