Пересечение линии - PullRequest
Новая
       9

Пересечение линии

3 голосов
/ 07 мая 2009

Как узнать, перехвачена ли линия в многоугольнике

Ответы [ 4 ]

3 голосов
/ 21 мая 2009

Вы можете прочитать разумный ответ из этой реализации, найденный на некоторой веб-странице 

Point  * intersection2(Point * _line1, Point * _line2) {

Point  p1,p2,p3,p4;
p1=_line1[0]; p3=_line2[0];
p2=_line1[1]; p4=_line2[1];

// Store the values for fast access and easy
// equations-to-code conversion
double x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
double y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

double A1 = y2-y1;
double B1 = x1-x2;
double C1 = (A1*x1)+(B1*y1);

double A2 = y4-y3;
double B2 = x3-x4;
double C2 = A2*x3+B2*y3;

double det = A1*B2 - A2*B1;

if (det==0){
    return NULL;
}else{
    // Return the point of intersection
    Point  * ret = new CvPoint2D64f ();
    ret->x = (B2*C1 - B1*C2)/det;
    ret->y = (A1*C2 - A2*C1)/det;
    return ret;

}

}

Reference. Пример C ++: геометрические понятия Пересечение линий и их применение, 2D рисование От lbackstrom с сайта ucancode

3 голосов
/ 08 мая 2009

Вопрос немного двусмысленный, но давайте все равно попробуем:

Предположим, что точки (x, y) на прямой определяются уравнением Ax + By + C = 0. Тогда мы, очевидно, можем определить, находится ли точка (x, y) на прямой, оценивая Ax + By + C. Если точка не находится на прямой, то знак Ax + By + C говорит нам, на какой стороне линии находится точка. Следовательно, проверяя знаки выражения Ax + By + C для каждой вершины (x, y) многоугольника, мы можем определить, все ли точки многоугольника находятся на одной стороне линии или нет.

(Немного другая проблема - определить, пересекает ли многоугольник отрезок.)

0 голосов
/ 08 мая 2009

В зависимости от того, что именно вы хотите (я предполагаю сегмент строки, как я только что написал этот код на этой неделе), вы можете получить его в двух частях:

прежде всего я бы предложил кодировать строки как 

a*X + b*Y - c = 0

потому что эта форма не имеет угловых регистров для таких строк, как X=5, Y=4 или X=3*Y.

  • Проверка, пересекает ли линия любую сторону многоугольника.
    • Проверьте, находятся ли концы обеих линий на противоположных сторонах другой линии. Предлагаемая форма облегчает это, просто проверяя полярность LHS
  • Проверка, находится ли точка на линии внутри многоугольника
    • Проверьте, не пересекает ли линия от какой-либо точки на вашей входной линии за пределами полигона нечетное количество точек. Имейте в виду, что вам нужно будет проверить наличие одной и той же точки в нескольких местах, и из-за ошибок FP это невозможно сделать с помощью теста на точное совпадение.
0 голосов
/ 07 мая 2009

Вам нужны точки многоугольника на координатном графике, а также наклон и точка пересечения x и y линии, чтобы найти эту информацию. Оттуда просто математика.

...