Определение точки пересечения двух отрезков (высокой точности)

  1. ...
  2. #include <math.h>
  3. ...
  4.  
  5. enum IntersectResult {  PARALLEL , COINCIDENT ,NOT_INTERESECTING, INTERESECTING  };
  6.  
  7. /** Определение координат точки пересечения двух отрезков.
  8. Метод возврашает :
  9.     PARALLEL - если парралельны
  10.     COINCIDENT - если совпали (один из отрезков лежит на другом)
  11.     NOT_INTERESECTING - если непересеклись в отрезках
  12.     INTERESECTING - если пересеклись
  13.     в x и y передаётся координата пересечения
  14. **/
  15. int LineIntersection(
  16.     double begin_x_, double begin_y_,
  17.     double end_x_, double end_y_,
  18.     double other_line_begin_x_, double other_line_begin_y_,
  19.     double other_line_end_x_, double other_line_end_y_,
  20.     double &x, double &y) {
  21.  
  22.         double denom = ((other_line_end_y_ - other_line_begin_y_)*(end_x_ - begin_x_)) -
  23.                       ((other_line_end_x_ - other_line_begin_x_)*(end_y_ - begin_y_));
  24.         double nume_a = ((other_line_end_x_ - other_line_begin_x_)*(begin_y_ - other_line_begin_y_)) -
  25.                        ((other_line_end_y_ - other_line_begin_y_)*(begin_x_ - other_line_begin_x_));
  26.         double nume_b = ((end_x_ - begin_x_)*(begin_y_ - other_line_begin_y_)) -
  27.                         ((end_y_ - begin_y_)*(begin_x_ - other_line_begin_x_));
  28.  
  29.         if (abs(denom) <= 0.00001) {
  30.             if (abs(nume_a) <= 0.00001 && abs(nume_b) <= 0.00001) {
  31.                 return COINCIDENT;
  32.             }
  33.             return PARALLEL;
  34.         }
  35.  
  36.         double ua = nume_a / denom;
  37.         double ub = nume_b / denom;
  38.  
  39.         if (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0) {
  40.             // получаем точку пересечения
  41.             x = begin_x_ + ua*(end_x_ - begin_x_);
  42.             y = begin_y_ + ua*(end_y_ - begin_y_);
  43.             return INTERESECTING;
  44.         }
  45.         return NOT_INTERESECTING;
  46.     }
Если не нужна высокая точность,то сравнивать числители и знаменатели с нулём:
  1. if (denom == 0) {
  2.     if (nume_a == 0 && nume_b == 0)
  3. ...
Ещё можно посмотреть про уравнения линий здесь:
http://algolist.manual.ru/maths/geom/intersect/lineline2d.php

Реклама

Мы в соцсетях

tw tg yt gt