линия пересечение

Question

Как найти ли строки перехвачены в многоугольнике

Answer 1

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

Answer 2

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

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

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

Answer 3

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

первую очередь я хотел бы предложить, кодирующим линии, как

a*X + b*Y - c = 0 

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

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

Answer 4

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

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