Обнаружение пересекающихся линий после грубого преобразования

Question

Используя преобразование Хафа в Matlab, обнаружил несколько строк. Используя конечные точки этих линий, я нанес их на карту. Я не могу понять, как я могу найти пересекающиеся линии, когда у меня есть все переменные.

Line7
Point1 [50,66]
Point2 [11,106]
theta,rho [45,81]


Line9
Point1 [19,83]
Point2 [53,79]
theta,rho [82,84]

Поскольку параметрические уравнения имеют следующий вид

  rho = xCos(theta) + ySin(theta)

Я не уверен, как решить это. Со всей этой информацией должен быть быстрый способ определить, пересекаются ли линии, если да, то и точки.

Любое руководство высоко ценится.

function FindHoughLines(I,filename)
[H,T,R] = hough(I);
rotI = imrotate(I,0,'crop');
imshow(H,[],'XData',T,'YData',R,...
            'InitialMagnification','fit');
xlabel('\theta'), ylabel('\rho');
axis on, axis normal, hold on;
P  = houghpeaks(H,10,'threshold',ceil(0.1*max(H(:))));
x = T(P(:,2)); y = R(P(:,1));
 plot(x,y,'s','color','white');
% Find lines and plot them
lines = houghlines(I,T,R,P,'FillGap',5,'MinLength',7);
 figure, imshow(rotI), hold on
max_len = 0;
for k = 1:length(lines)
    if(isField(lines,'point1') ~= 0)               
   xy = [lines(k).point1; lines(k).point2];
    plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');

   % Plot beginnings and ends of lines
   plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
   plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');
   text(xy(1,1),xy(1,2),[ num2str(k)],'HorizontalAlignment','center','BackgroundColor',[.7 .9 .7]);
   % Determine the endpoints of the longest line segment
   len = norm(lines(k).point1 - lines(k).point2);
   if ( len > max_len)
      max_len = len;
      xy_long = xy;
   end
    end
end

Answer 1

Самый простой способ, который приходит на ум, - преобразовать все обнаруженные линии в декартовы координаты, используя

y = -ctg(theta) + r/sin(theta)

Затем используйте стандартную процедуру обнаружения, например, http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

Answer 2

Вы хотите пересечения линий или отрезков? Например, предположим, что один из ваших сегментов линии имеет конечные точки (1,0) и (2,0), а другой имеет конечные точки (0,1) и (0,2); Вы хотите пересечение в (0,0) посчитано или нет?

Нужно ли вам эффективно справляться со случаем, когда существует множество линий и найти все их пересечения, или можно рассмотреть все пары линий и проверить их одну за другой?

Самый простой случай, если все в порядке, если рассматривать пары линий, и если пересечения линий (в отличие от отрезка) достаточно хороши. Тогда для каждой пары линий вы просто решаете два одновременных линейных уравнения: aX+bY=c, dX+eY=f. Это очень стандартная вещь; это равносильно инверсии матрицы 2х2.

Если вам нужно заметить, что пересечение на самом деле не лежит внутри заданных отрезков, вот несколько подходов. (1) Сначала сначала пересечение, как указано выше, затем проверьте, что оно находится в каждом данном сегменте. Вы можете сделать это, выбрав одну координату (скажем, x-координату) и увидев, находится ли она между x-координатами двух конечных точек. Конечно, вы не можете использовать x-координату для вертикальных линий и не должны использовать ее для почти вертикальных линий; Лучше выбрать ту координату, которая имеет больший коэффициент. (2) Запишите линии параметрически как (x,y)=(x1,y1)+t(dx1,dx1) и (x,y)=(x2,y2)+u(dx2,dy2); теперь вместо одновременных уравнений для x, y у вас есть одновременные уравнения для t,u; решить их и проверить, что 0 <= t,u <= 1.

Если вам нужно эффективно справляться, когда у вас много строк, есть алгоритмы для этого; Google "Line Sweep", чтобы найти стандартный, который довольно легко понять.