Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

torrvic, возможно, Вам нужно добавить -lGLU
Извините за тупой вопрос. У меня при сборке Вашего примера выходит ошибка: "undefined reference to gluLookAt". Не могу найти в какой библиотеке находится эта функция. У меня задано: -lGL -lglut ... Искал в /usr/lib таким образом: nm lib*so* | grep...
Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...

Счетчики и рейтинг

Рейтинг@Mail.ru
Скриншот к примеру
Среда программирования: 
CodeBlocks 13.12
Статья по теме: 

Вход : множество отрезков, заданных координатами концов отрезков.
Выход : множество отрезков, отсортированных на пересекающиеся и не пересекающиеся.

Использование:
Запустить пример, набросать левой клавишей мыши (ЛКМ) отрезки,
вид до проверки
проверка происходит по нажатию на правую клавишу мыши (ПКМ).
вид после проверки
Основная теоретическая часть описана в Определение точки пересечения двух отрезков, кроме того, что для даннрй задачи нет необходимости искать пересечение двух отрезков. Проверка основана на том, что если AB и CD пересекаются, то A и B лежат по разные стороны от CD, а также C и D лежат по разные стороны от AB.

Уточнение: использована библиотека SFML, не GTK.

Код программы: 

#include <SFML/Graphics.hpp>
#include <iostream>
 
struct DataAll {
    sf::Text mTip;                  // подсказка
    sf::Vector2f tempVectorf;
    sf::VertexArray mLineTemp;      // для временной линии
    sf::VertexArray mLines;         // для постоянной линии
    bool pointSecond;               // вторая точка временной линии
    bool checkedLines;              // флаг реинициализации
};
 
void handleMouseLeft(sf::Vector2i currPos, DataAll& data);
void handleMouseRight(DataAll& data);
float area2(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3);
bool leftVector(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3);
bool collinear(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3);
bool IntersectProp(const sf::Vertex& vert1, const sf::Vertex& vert2,
                   const sf::Vertex& vert3, const sf::Vertex& vert4);
 
int main()  // создание окна и обработчика событий
{
    // без кнопки максимизации
    sf::RenderWindow window(sf::VideoMode(640, 480), "is line intersect",
                            sf::Style::Close|sf::Style::Titlebar);
 
    DataAll myData;
    // инициализация
    sf::Font font;
    font.loadFromFile("Sansation.ttf");
    myData.mTip.setFont(font);
    myData.mTip.setCharacterSize(20);
    // ЛКМ - набрасывание точек;  ПКМ - построение
    myData.mTip.setString("LKM - nabrasyvaniye tochek;   PKM - postroeniye");
    myData.mTip.setPosition(5.f, 425.f);
    myData.mTip.setColor(sf::Color::Cyan);
    myData.mLineTemp.setPrimitiveType(sf::Lines); // каждые 2 точки - отрезок
    myData.mLines.setPrimitiveType(sf::Lines);
    myData.pointSecond = false;
    myData.checkedLines = false;
    myData.mLines.setPrimitiveType(sf::Lines);
 
    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) { // опрос событий
            if (event.type == sf::Event::Closed)
                window.close();
            // ЛКМ
            if ((event.type == sf::Event::MouseButtonPressed) &
                    (sf::Mouse::isButtonPressed(sf::Mouse::Left)) ) {
                sf::Vector2i iCurrPos = sf::Mouse::getPosition(window) ;
                handleMouseLeft(iCurrPos, myData);
            }
            // ПКМ
            if ((event.type == sf::Event::MouseButtonPressed) &
                    (sf::Mouse::isButtonPressed(sf::Mouse::Right)) )
                handleMouseRight(myData);
        }
 
        if (myData.pointSecond) {   // линия бежит за мышью
            float x = sf::Mouse::getPosition(window).x;
            float y = sf::Mouse::getPosition(window).y;
            myData.mLineTemp[1].position = sf::Vector2f(x, y);
        }
        window.clear();
        window.draw(myData.mTip);
        window.draw(myData.mLines);
        window.draw(myData.mLineTemp);
        window.display();
    }
    return EXIT_SUCCESS;
}
 
// добавление отрезков в массив
void handleMouseLeft(sf::Vector2i currPos, DataAll& data)
{
    // реинициализация
    if (data.checkedLines) {
        data.mLines.clear();
        data.mLineTemp.clear();
        data.pointSecond = false;
        data.checkedLines = false;
    }
    sf::Color aqua(0, 255, 255);
    // если уже брошена первая точка
    if (data.pointSecond) {     // вторая точка
        // занести в постоянный, очистить временный
        sf::Vertex mVertex(data.tempVectorf,aqua);
        data.mLines.append(mVertex);
 
        mVertex.position.x = 0.0 + currPos.x;
        mVertex.position.y = 0.0 + currPos.y;
        mVertex.color = aqua;
        data.mLines.append(mVertex);
 
        data.mLineTemp.clear();
        data.pointSecond = false;
    } else {                    // первая точка
        // положить первую,
        data.tempVectorf.x = 0.0 + currPos.x;
        data.tempVectorf.y = 0.0 + currPos.y;
        data.mLineTemp.append(data.tempVectorf);
        data.mLineTemp.append(data.tempVectorf);
        data.pointSecond = true;
    }
 
};
 
// вход   : массив точек, представляющих попарно отрезок
//          стандартной раскраски
// выход  : массив точек, представляющих попарно отрезок
//          различных раскрасок
void handleMouseRight(DataAll& data)
{
    data.pointSecond = false;
    data.mLineTemp.clear();
    // если 2 линии пересекаются, покрасить в красный, иначе в зеленый
    // по первому отрезку
    bool intersect = false;
    // красим все в зеленый
    for (unsigned int i = 0; i < data.mLines.getVertexCount(); ++i) {
        data.mLines[i].color = sf::Color::Green;
    }
    // отрезки - [0]-[1], [2]-[3]
    for (unsigned int i = 0; i < data.mLines.getVertexCount()-2; i+=2) {
        // со вторым отрезком
        for (unsigned int n = i+2; n < data.mLines.getVertexCount(); n+=2) {
            intersect = IntersectProp(data.mLines[i], data.mLines[i+1],
                                      data.mLines[n], data.mLines[n+1]);
//            std::cout << i/2 + 1 << " c " << n/2+1 << " : " << intersect << std::endl;
            if (intersect) {
                data.mLines[i].color = sf::Color::Red;
                data.mLines[i+1].color = sf::Color::Red;
                data.mLines[n].color = sf::Color::Red;
                data.mLines[n+1].color = sf::Color::Red;
            }
        }
    }
    data.checkedLines = true;
};
 
 
// источник: O`Rourke
 
// вход  : a, b, c
// площадь на векторах ab и ac;  знак - указатель на поворот
float area2(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3)
{
    return ( (vert2.position.x - vert1.position.x) * (vert3.position.y - vert1.position.y) -
             (vert3.position.x - vert1.position.x) * (vert2.position.y - vert1.position.y) );
}
 
bool leftVector(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3)
{
    return area2(vert1, vert2, vert3) > 0;
}
 
bool collinear(const sf::Vertex& vert1, const sf::Vertex& vert2, const sf::Vertex& vert3)
{
    return area2(vert1, vert2, vert3) == 0;
}
 
// вход  : 4 точки, представляющие попарно отрезки
bool IntersectProp(const sf::Vertex& vert1, const sf::Vertex& vert2,
                   const sf::Vertex& vert3, const sf::Vertex& vert4)
{
    // некорректные случаи
    if (    collinear(vert1, vert2, vert3) or
            collinear(vert1, vert2, vert4) or
            collinear(vert3, vert4, vert1) or
            collinear(vert3, vert4, vert2)
       )
        return false;
    // все просто: если углы в обоих случаях с разными знаками -
    // пересекаются отрезки, а не линии
    return (leftVector(vert1, vert2, vert3) xor leftVector(vert1, vert2, vert4)) and
           (leftVector(vert3, vert4, vert1) xor leftVector(vert3, vert4, vert2));
}

Прикрепленный файлРазмер
source_is_line.rar13.9 кб
is_line.rar476.12 кб