Вычислить пересечение двух ребер

Что вам нужно, так это модульные тесты для ваших 4 методов и их тщательное тестирование. В частности, в случае пересечений отрезков и линий существует множество конечных случаев, таких как параллельные уклоны, совпадающие конечные точки, полное или частичное перекрытие, в дополнение ко всем обычным проблемам с допусками (например, что именно делает " равный наклон "значит?).

Не разбивая вещи на более мелкие, более тестируемые единицы, вам будет сложно сузить его.

Хотя трудно сказать, не имея возможности увидеть ваш код, я подозреваю, что вы сталкиваетесь с проблемами устойчивости с вашими значениями с плавающей запятой. Рассматривали ли вы использование целочисленных точек или повышение надежности, например, удаление общих битов в значениях с плавающей запятой?

Существует библиотека геометрии с открытым исходным кодом GEOS (http://trac.osgeo.org/geos/), что может быть полезно для проверки ваших данных. В GEOS также есть алгоритмы для выполнения округления с привязкой к целочисленной сетке и исключения общих битов, чтобы помочь вам определить, сталкиваетесь ли вы с проблемой устойчивости. Также следует отметить, как GEOS вычисляет пересечение с использованием дуальности точка-линия в однородном пространстве (что я не могу точно сказать, математически эквивалентна описываемая вами техника проекции скалярного произведения).

В стороне, мое любимое решение для вычисления пересечений в графе ребер - это использование прямой линии в сочетании с монотонной цепочкой ребер. Когда вы используете монотонные цепи, вы можете исключить множество тестов на пересечение ребер, поскольку цепи никогда не пересекаются сами по себе. Это то, что делает GEOS.

Зачем изобретать колесо?

Если вы умеете полагаться на Boost, я бы посмотрел библиотеку GTL в песочница. Инструкции по загрузке см. В wiki (инструкции прямо на лицевой стороне страница).

Библиотека GTL подходит для любой реализации вашей структуры данных (т.е. она разработана в духе STL, где структуры данных и алгоритмы ортогональны). Код одновременно быстрый и правильный. Проверьте это, если сможете.

Вы можете попробовать Boost.Geometry (также известную как Generic Geometry Library).

Я использую линию развертки на монотонных ребрах, когда вычисляю пересечение (у меня есть функция сортировки, которая сортирует ребра внутри конструктора, и я проверяю их, они хорошо упорядочены), хотя я получаю в качестве пересечения некоторые точки, которые являются вершинами для некоторые края, хотя у меня есть много тестов для устранения этих случаев.

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

//4 method
double* QSweep::findIntersection(edge_t edge1,edge_t edge2) {  
    point_t p1=myPoints_[edge1[0]];
    point_t p2=myPoints_[edge1[1]];
    point_t p3=myPoints_[edge2[0]];
    point_t p4=myPoints_[edge2[1]];

    double xD1,yD1,xD2,yD2,xD3,yD3,xP,yP,h,denom;
    double* pt=new double[3];

    // calculate differences  
    xD1=p2[0]-p1[0];  
    xD2=p4[0]-p3[0];  
    yD1=p2[1]-p1[1];  
    yD2=p4[1]-p3[1];  
    xD3=p1[0]-p3[0];  
    yD3=p1[1]-p3[1];    

    xP=-yD1;
    yP=xD1;
    denom=xD2*(-yD1)+yD2*xD1;
    if (denom==0) {
        return NULL;
    }
    else{
    h=(xD3*(-yD1)+yD3*xD1)/denom;
    }
    std::cout<<"h is"<<h<<endl;
    if ((h>0)&&(h<1)){
        pt[0]=p3[0]+xD2*h;  
        pt[1]=p3[1]+yD2*h;
        pt[2]=0.00;
    }
    else{
        return NULL;
    }

    // return the valid intersection  
    return pt;  
}

void QSweep:: intersection(){
    nbIntersections=0;
    double* vector;
    for (int i=2;i<myEdges_.size()-1;i++){
        vector=findIntersection(myEdges_[i-1],myEdges_[i]);
        if (vector!=NULL){
                nbIntersections++;
                myIntersections.push_back(vector);
                swap(myEdges_[i-1], myEdges_[i]);
        }
    }
}

Функция пересечения всегда одна и та же, поэтому я просто нахожу функцию findIntersection.

Для метода 1 и 2 я использую следующую версию функции findIntersection:

double* QSweep::computeIntersection(double m1, double b1, double m2, double b2){
    double* v=new double[3];

    v[0]= (b2-b1)/(m1-m2);
    v[1]= (m1*b2-m2*b1)/(m1-m2);
    v[2]=0.00;
    return v;
    }

    double* QSweep::findIntersection(edge_t edge1, edge_t edge2){


    //equation for the support line of the first edge

    double a=myPoints_[edge1[0]][0];
    double b=myPoints_[edge1[0]][1];
    double c=myPoints_[edge1[1]][0];
    double d=myPoints_[edge1[1]][1];
    double m1=getSlope(a,b,c,d);
    double b1=getYIntercept(a,b,c,d);

    double x=myPoints_[edge2[0]][0];
    double y=myPoints_[edge2[0]][1];
    double s=myPoints_[edge2[1]][0];
    double t=myPoints_[edge2[1]][1];
    double m2=getSlope(x,y,s,t);
    double b2=getYIntercept(x,y,s,t);
    double* vector;

    double line2InLine1=evalEqnLineD(myPoints_[edge2[0]],edge1);
    double line2InLine1New=evalEqnLineD(myPoints_[edge2[1]],edge1);
    double line1InLine2=evalEqnLineD(myPoints_[edge1[0]],edge2);
    double line1InLine2New=evalEqnLineD(myPoints_[edge1[1]],edge2);

    if (m1==m2){
        return NULL;
    }
    else{

            if ((line1InLine2*line1InLine2New)<0 &&   (line2InLine1*line2InLine1New)<0){
            vector=computeIntersection(m1,b1,m2,b2);

            if ((vector[0]>a && vector[0]<c)&&(vector[0]>x && vector[0]<s)){
                return vector;
            }
            else{
                return NULL;
            }
        }
        else{
            return NULL;
        }
    }
    return vector;
}

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

Вы только что сказали: алгоритм развертки ... Я использовал усиленный алгоритм Майерса 1985 года, в то время этот алгоритм был лучшим.

Что я сделал: работал с целыми числами, т.е. фиксированными точками. - числа, чтобы иметь дело с проблемами точности.

Что касается алгоритма пересечения двух сегментов: первые очевидные тесты для диапазонов и параллельности сегментов. Затем я вычислил ожидаемую точку пересечения в двойном размере и угол между двумя сегментами. Всякий раз, когда угол между двумя сегментами был «маленьким», я вычислял расстояние от точки пересечения, где расстояние между двумя линейными сегментами становится больше единицы в моем целочисленном пространстве. Затем я разделил каждый из двух сегментов на 3, например> ------- ‹с общей частью, так сказать, расширив точку пересечения до отдельного сегмента, и удалил первые два сегмента. Я не стал беспокоиться, если лежащие ниже полигоны станут вогнутыми.

Поскольку сегменты были вычислены для вычисления графа разбиения многоугольников, граф разбиения имел вместо двух почти параллельных сегментов всего 3 сегмента с более правильными углами.

Повышение также содержало распределительную сортировку слиянием точек событий (в настоящее время: такой алгоритм сильно распараллеливается !!!), тем самым уменьшая сложность сортировки от ожидаемого O (n log n) до ожидаемого O (n), но O (n log n) худший случай. Я настоятельно рекомендую пересмотреть алгоритм развертки (однопоточный) к некоторым методам «разделяй и властвуй», распараллелив его.