Архив рубрики: Математика

Положение двух точек относительно прямой

Поводом для написания этой статьи стала эта тема на форуме. Вопрос довольно простой, но мне показалось, что он заслуживает освещения в цикле, посвящённом применению математики в программировании.
Итак, дано: уравнение прямой, две точки, не лежащие на этой прямой. Требуется определить, лежат ли точки по одну сторону от прямой или по разные.

Где может понадобится решение подобной задачи? Представьте, вы пишите стратегическую игру. Два юнита находятся по разные стороны реки. Пользователь выделяет их обоих, и заставляет куда-то идти. И тут нужно определить, смогут ли оба юнита пройти туда, куда велит пользователь. Стало интереснее?
Итак, набросаем небольшой рисунок.

У нас есть точки A, B и C. B и C лежат по одну сторону от прямой, а A по другую.
Для того, чтобы проверить, лежат ли две точки по одну сторону от прямой или нет нужно спроецировать эти точки на прямую линией, параллельной оси OY. Затем сравнить ординаты определяемых точек с ординатами полученных. Если оба отношения будут идентичными, то точки лежат с одной стороны, иначе - с разных.
Поробуем это запрограммировать.

#include <iostream>

class CFunction
{
public:
    CFunction(double a, double b) :
        m_a(a),
        m_b(b)
    {
    }
    
    double Run(double x)
    {
        return m_a * x + m_b;
    }
    
private:
    double m_a;
    double m_b;
};

struct CPoint
{
    double m_x;
    double m_y;
};

int main()
{
    CPoint point_a;
    CPoint point_b;
    double a;
    double b;
    
    std::cout << "y = ax + b.nEnter the a value: ";
    std::cin >> a;
    std::cout << "Enter the b value: ";
    std::cin >> b;
    
    std::cout << "Point A.nEnter the X coord: ";
    std::cin >> point_a.m_x;
    std::cout << "Enter the Y coord: ";
    std::cin >> point_a.m_y;
    
    std::cout << "Point B.nEnter the X coord: ";
    std::cin >> point_b.m_x;
    std::cout << "Enter the Y coord: ";
    std::cin >> point_b.m_y;
    
    CFunction function(a, b);
    
    bool a_up = function.Run(point_a.m_x) > point_a.m_y;
    bool b_up = function.Run(point_b.m_x) > point_b.m_y;
    
    if(a_up == b_up)
    {
        std::cout << "Points lie on one siden";
    }
    else
    {
        std::cout << "Points lie on different sidesn";
    }
}

Здесь я ввёл класс, соответствующий линейной функции и структуру для описания точки. Ничего сложного. Далее, как уже говорилось, берём ординаты из функции, соответствующие абсциссам точкек и сравниваем их с ординатами точек. Проверяем результаты. Если они идентичны, выдаём сообщение о том, что точки лежат с одной стороны прямой, иначе сообщаем о том, что точки находятся по разные стороны прямой.

Определяем, лежит ли точка внутри полигона

Эта статья является продолжением цикла "Математика в программировании". На этот раз я хочу показать, как можно по координатам определить, лежит ли точка внутри замкнутого многоугольника или нет. Для решения этой задачи существует несколько способов. Оптимальный, для вычислительной машины, способ заключается в подсчёте количества пересечённых сторон лучём проведённым из проверяемой точки.

Как видно из рисунка 1, если точка принадлежит полигону, то луч пересечёт нечётное количество сторон. Если же луч пересечёт чётное количество сторон, или ниодной, то это значит, что точка лежит вне полигона.
У данного способа есть недостаток, связанный с случаем, когда точка проходит через вершину, но в большинстве случаев такой вероятностью можно пренебречь. Кроме того, можно выполнить дополнительные действия для изменения условия, например изменить направление луча, если последний проходит через одну из вершин.
Недавно я начать изучать язык программирования Java и в связи с этим решил реализовать пример к этой статье именно на нём. Это мой первый опус на Java, так что не обессудьте.
Итак, что должно получится в итоге:

В окне можно "натыкать" левой кнопкой мыши точек, которые будут являться вершинами полигона. Во время рисования все линии будут отображаться. Закончить рисовать полигон нужно нажатием правой кнопки, после чего все щелчки левой кнопкой будут приводить к установке точки, вхождение которой нужно проверить. Для того, чтобы начать всё сначала нужно нажать Esc.
Итак, исходники:

Файл CPoints.java - это мой вспомогательный класс, который я использовал, для хранения массивов точек. Он динамически выделяет память под массивы блоками.

package polygon;


public class CPoints
{
    // Массив абсцисс.
    private int[] m_x;
    // Массив ординат.
    private int[] m_y;
    // Количество точек.
    private int m_count;
    // Вместимость.
    private int m_capacity;
    // Количество элементов, добавляемых при расширении.
    private final int m_block_size;
    // Минимальный размер m_block_size.
    private final int m_block_size_minimal = 10;
    
    // Устанавливает размер блока в значение по умолчанию.
    public CPoints()
    {
        m_block_size = m_block_size_minimal;
        m_count = 0;
        m_capacity = 0;
        increase();        
    }

    // default_block_size - размер блока, если меньше чем
    // m_block_size_minimal,то игнорируется.
    public CPoints(int default_block_size)
    {
        if(default_block_size < m_block_size_minimal)
            default_block_size = m_block_size_minimal;
        m_block_size = default_block_size;
        m_count = 0;
        m_capacity = 0;
        increase();
    }

    // Добавляет точку в конец массива.
    public void push(final int x, final int y)
    {
        // Если добавлять некуда, то увеличиваем размер массивов.
        if(m_count == m_capacity)
            increase();

        m_x[m_count] = x;
        m_y[m_count] = y;
        m_count++;
    }

    // Удаляет последнюю точку.
    public void pop()
    {
        if(m_count > 0)
            m_count--;
    }

    /// Возвращает размер массива.
    public int count()
    {
        return m_count;
    }

    // Возвращает массив X'ов.
    public final int[] getXArray()
    {
        return m_x;
    }

    // Возвращает массив Y'ов.
    public final int[] getYArray()
    {
        return m_y;
    }
    
    // Увеличевает размер массивов на m_block_size.
    private void increase()
    {
        int new_capasity = m_capacity + m_block_size;
        if(m_capacity != 0)
        {
            int[] tempx = new int[new_capasity];
            int[] tempy = new int[new_capasity];
            
            for(int i = 0; i < m_capacity; i++)
            {
                tempx[i] = m_x[i];
                tempy[i] = m_y[i];
            }
            
            m_x = tempx;
            m_y = tempy;
        }
        else
        {
            m_x = new int[new_capasity];
            m_y = new int[new_capasity];
        }
        m_capacity = new_capasity;
    }
}

Непосредственно сам определитель, модуль CDeterminant.java

package polygon;


public class CDeterminant
{
    public static boolean determine(final CPoints points, int x, int y)
    {

        boolean result = false;
        int count = points.count();
        int[] xp = points.getXArray();
        int[] yp = points.getYArray();


        for (int i = 0, j = count - 1; i < count; j = i++)
        {
            if(xp[j] == xp[i] || yp[j] == yp[i]) // Деление на ноль.
                continue;

            if(((yp[i] <= y && y < yp[j]) || (yp[j] <= y && y < yp[i])))
            {
                float x1 = xp[i];
                float y1 = yp[i];
                float x2 = xp[j];
                float y2 = yp[j];

                float k = (y2 - y1) / (x2 - x1);
                float b = y1 - k * x1;
                float cross_x = (y - b) / k;

                if((float)x > cross_x)
                    result = !result;
            }
        }
        return result;
    }
}

Здесь я нарочно не стал оптимизировать, даже наоборот, написал всё более подробно для того, чтобы было проще понять. Мы в цикле берём каждую пару смежных точек полигона и находим точку пересечения с лучём f(x) = y, где y - ордината определяемой точки. Луч проводим в левую сторону. Сначала определяем, пересекутся ли вообще отрезки. Затем находим абсциссу пересечения (ордината известна исходя из того, что наш луч параллелен оси абсцисс). Так как все вычисления выполняются в числах с плавающей точкой, то я привёл сразу всё к типу float. Далее восстанавливаем уравнение прямой стороны полигона, находя тангенс угла наклона - коэффициент при x и точку пересечения с осью ординат. Затем вычисляем точку пересечения с лучём. Если точка пересечения оказывается левее точки, то мы получили необходимое пересечение и отмечаем его инвентированием результирующего флага.
Оптимизированную версию этого алгоритма можно найти здесь.

Ну и далее я приведу остальные части программы.
Файл CMainWindow.java с главным окном

package polygon;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Graphics;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import javax.swing.JPanel;
import javax.swing.JFrame;
import javax.swing.JOptionPane;

class CPanel
    extends JPanel
{
    // Флаг того, что полигон был замкнут.
    private boolean m_polygon_end;
    // Вершины полигона.
    private CPoints m_points;
    // Абсциса определяемой точки.
    private int m_x;
    // Ордината определяемой точки.
    private int m_y;
    // Флаг того, что точка была установлена.
    private boolean m_point_end;

    public CPanel()
    {
        m_points = new CPoints();
        m_polygon_end = false;
        m_point_end = false;

        CMouseHandler mouse_handler = new CMouseHandler();
        addMouseListener(mouse_handler);
        addMouseMotionListener(mouse_handler);
        addKeyListener(new CKeyHandler());
        setFocusable(true); // Для обработки клавиатурных сообщений.
        setBackground(Color.white);
    }

    @Override public void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        Graphics2D graphics = (Graphics2D)g;

        if(m_polygon_end)
        {
            graphics.drawPolygon(m_points.getXArray(),
                m_points.getYArray(), m_points.count());
            if(m_point_end)
                graphics.fillOval(m_x - 5, m_y - 5, 10, 10);
        }
        else
        {
            graphics.drawPolyline(m_points.getXArray(),
                m_points.getYArray(), m_points.count());
        }
    }


    private class CMouseHandler
        extends MouseAdapter
    {
        @Override public void mouseClicked(MouseEvent event)
        {
            if(!m_polygon_end)
            {
                if(event.getButton() == MouseEvent.BUTTON1)
                {
                    m_points.push(event.getX(), event.getY());
                    repaint();
                }
                else if(event.getButton() == MouseEvent.BUTTON3)
                {
                    // В полигоне не может быть меньше трёх точек.
                    if(m_points.count() >= 4)
                    {
                        m_points.pop(); // Убираем хвост.
                        m_polygon_end = true;
                        repaint();
                    }
                }
            }
            else if(event.getButton() == MouseEvent.BUTTON1)
            {
                m_x = event.getX();
                m_y = event.getY();
                m_point_end = true;
                repaint();
                String msg = CDeterminant.determine(m_points, m_x, m_y) ?
                    "Точка лежит внутри полигона" :
                    "Точка лежит вне полигона";
                JOptionPane.showMessageDialog(null, msg, "Положение точки",
                    JOptionPane.INFORMATION_MESSAGE);
            }
        }

        @Override public void mouseMoved(MouseEvent event)
        {
            if(!m_polygon_end)
            {
                m_points.pop();
                m_points.push(event.getX(), event.getY());
                repaint();
            }
        }
    } // private class CMouseHandler

    private class CKeyHandler
        extends KeyAdapter
    {
        @Override public void keyPressed(KeyEvent event)
        {
            if(event.getKeyCode() == KeyEvent.VK_ESCAPE)
            {
                m_points = new CPoints();
                m_point_end = false;
                m_polygon_end = false;
                repaint();
            }
        }
    } // private class CKeyHandler
} // class CPanel

public class CMainWindow
    extends JFrame
{
    public CMainWindow()
    {
        setTitle("Определение принадлежности точки полигону");
        setSize(800, 600);
        setBackground(Color.white);

        getContentPane().add(new CPanel());
    }
}

И файл, запускающий всё это добро - CMain.java:

package polygon;

public class CMain
{
    public static void main(String params[])
    {
        CMainWindow wnd = new CMainWindow();
        wnd.setDefaultCloseOperation(CMainWindow.EXIT_ON_CLOSE);
        wnd.setVisible(true);
    }
}

Пишем часы со стрелками

Цель этой статьи - показать практическое использование некоторых тригонометрических функций в программировании.

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

Чтобы наглядно представить функции нужно взять произвольную окружность, поместить её в декартову систему координат, совместив центр окружности с нулём, и принять радиус этой окружности за единицу в этой системе координат.

На рисунке 1 показана окружность радиуса r = 1 с центром в точке O. Произвольная точка A заданная на окружности образует дугу AB и угол α, численно (в радианах) равных друг другу.
Проекция точки A на ось абсцисс (x) называется косинусом угла α или дуги AB.
Проекция точки A на ось ординат (y) называется синусом угла α или дуги AB.
Если рассматривать полученные треугольники AxOA или AyOA, то можно говорить о следующих отношениях.
Косинусом острого угла называется отношение прилежащего катета к гипотенузе.
Синусом острого угла называется отношение противолежащего катета к гипотенузе.
Углы в системе координат откладываются против часовой стрелки.
Так как длина всей окружности равна 2πr, а радиус нашей окружности равен единице, то длина окружности в нашем случае равна 2π. То есть, угол в 180 градусов соответствует π радиан. Из этого мы можем вывести формулу: 1 радиан = 180 / π.
Более подробную информацию Вы можете получить, например, здесь.

Результатом нашего проекта должны стать часы, показанные на рисунке 2.

Итак, далее я приведу полный исходный текст программы, а затем прокомментирую непонятные моменты. Программа написана с использованием библиотеки Qt.

Файл Clock.h

#ifndef CLOCK_H
#define CLOCK_H

#include <QtGui/QWidget>
#include <QtCore/QPoint>

class CClock : public QWidget
{
Q_OBJECT
public:
    explicit CClock(QWidget *parent = 0);

public slots:
    void onTimer();

protected:
    virtual void paintEvent(QPaintEvent * event);

private:
    QPoint rotatePoint(const QPoint & point, int degree, double radius);
};

#endif // CLOCK_H

Файл Clock.cpp

#include "Clock.h"
#include <QtGui/QPainter>
#include <QtCore/QTime>
#include <QtCore/QTimer>
#include <cmath>
//===================================================================

CClock::CClock(QWidget *parent) :
    QWidget(parent)
{
    setMinimumSize(500, 500);
    QTimer * timer = new QTimer(this);
    connect(timer, SIGNAL(timeout()), this, SLOT(onTimer()));
    timer->start(1000);
}
//===================================================================

void CClock::onTimer()
{
    QWidget::update();
}
//===================================================================

void CClock::paintEvent(QPaintEvent * /*event*/)
{
    //
    // константы для отрисовки.
    //

    // цвет окружности.
    static const QColor circle_color(88, 88, 88, 255);
    // цвет засечек часов.
    static const QColor stroke_hour_color(19, 66, 91, 255);
    // цвет засечек минут.
    static const QColor stroke_min_color(100, 120, 120, 255);
    // цвет часовой стрелки.
    static const QColor hour_hand_color(60, 65, 65, 255);
    // цвет минутной стрелки.
    static const QColor min_hand_color(90, 105, 105, 255);
    // цвет секундной стрелки.
    static const QColor sec_hand_color(125, 150, 150, 255);

    //
    // константы метрик и координат.
    //

    // ширина линии для отрисовки окружности.
    static const int circle_line_width = 5;
    // ширина линии штриха (деление).
    static const int stroke_line_width = 3;
    // длина штриха часов.
    static const int stroke_hour_length = 10;
    // длина штриха минут.
    static const int stroke_min_length = 5;

    // зазор меду окружностью и засечками.
    static const int spacing = 10;
    // абсцисса центра окружности в оконных координатах.
    const double circle_center_x = width() / 2;
    // ордината центра окружности в оконных координатах.
    const double circle_center_y = height() / 2;
    // радиус окружности.
    const double circle_radius = (circle_center_x < circle_center_y ?
        circle_center_x : circle_center_y) - spacing - circle_line_width;

    // радиус, описываемый часовой стрелкой.
    const double hour_hand_radius = circle_radius / 2;
    // радиус, описываемый минутной стрелкой.
    const double min_hand_radius = hour_hand_radius + circle_radius / 6;
    // радиус, описываемый секундной стрелкой.
    const double sec_hand_radius = hour_hand_radius + circle_radius / 4;

    static const double hour_hand_tail = 20.0; // длина хвоста часовой стрелки.
    static const double min_hand_tail = 30.0; // длина хвоста минутной стрелки.
    static const double sec_hand_tail = 40.0; // длина хвоста секундной стрелки.

    // половина основания часовой стрелки.
    static const double hour_hand_half_found = 15.0;
    // половина основания минутной стрелки.
    static const double min_hand_half_found = 10.0;
    // половина основания секундной стрелки.
    static const double sec_hand_half_found = 5.0;

    // радиус, описываемый крайними точками хвоста часовой стрелки.
    const double hour_hand_tail_radius = ::sqrt(::pow(hour_hand_tail, 2) +
        ::pow(hour_hand_half_found, 2));
    // радиус, описываемый крайними точками хвоста минутной стрелки.
    const double min_hand_tail_radius = ::sqrt(::pow(min_hand_tail, 2) +
        ::pow(min_hand_half_found, 2));
    // радиус, описываемый крайними точками хвоста секундной стрелки.
    const double sec_hand_tail_radius = ::sqrt(::pow(sec_hand_tail, 2) +
        ::pow(sec_hand_half_found, 2));


    // координаты часовой стрелки в начальном состоянии (указывает на 3).
    //
    // конец стрелки.
    const QPoint hour_hand_a0(hour_hand_radius, 0);
    // координаты первой точки основания часовой стрелки.
    const QPoint hour_hand_b0(-hour_hand_tail, hour_hand_half_found);
    // координаты второй точки основания часовой стрелки.
    const QPoint hour_hand_c0(-hour_hand_tail, -hour_hand_half_found);

    // координаты минутной стрелки в начальном состоянии (указывает на 3).
    //
    // конец стрелки.
    const QPoint min_hand_a0(min_hand_radius, 0);
    // координаты первой точки основания минутной стрелки.
    const QPoint min_hand_b0(-min_hand_tail, min_hand_half_found);
    // координаты второй точки основания минутной стрелки.
    const QPoint min_hand_c0(-min_hand_tail, -min_hand_half_found);

    // координаты секундной стрелки в начальном состоянии (указывает на 3).
    //
    // конец стрелки.
    const QPoint sec_hand_a0(sec_hand_radius, 0);
    // координаты первой точки основания секундной стрелки.
    const QPoint sec_hand_b0(-sec_hand_tail, sec_hand_half_found);
    // координаты второй точки основания секундной стрелки.
    const QPoint sec_hand_c0(-sec_hand_tail, -sec_hand_half_found);


    //
    // рисуем.
    //

    QPainter painter(this);
    painter.setRenderHint(QPainter::Antialiasing, true);

    // устанавливаем новое начало координат.
    painter.translate(circle_center_x, circle_center_y);

    // копируем перо из устройства рисования.
    QPen pen = painter.pen();

    // рисуем окружность.
    //
    // устанавливаем ширину и цвет линии пера.
    pen.setWidth(circle_line_width);
    pen.setColor(circle_color);
    // устанавливаем перо в устройство рисования.
    painter.setPen(pen);
    // рисуем.
    painter.drawEllipse(QPoint(0, 0), static_cast<int>(circle_radius),
        static_cast<int>(circle_radius));

    // рисуем 60 засечек.
    //
    // крайняя к окружности точка.
    const QPoint p1(circle_radius - circle_line_width - spacing, 0);
    // вторая точка для штрихов часов.
    const QPoint p2(p1.x() - stroke_min_length, 0);
    // вторая точка для штрихов минут.
    const QPoint p3(p1.x() - stroke_hour_length, 0);
    pen.setWidth(stroke_line_width);
    pen.setColor(stroke_min_color);
    painter.setPen(pen);
    for(int i = 0; i < 60; i++)
    {
        if(i % 5 == 0)
        {
            pen.setColor(stroke_hour_color);
            painter.setPen(pen);
            painter.drawLine(p1, p3);
            pen.setColor(stroke_min_color);
            painter.setPen(pen);
        }
        else
        {
            painter.drawLine(p1, p2);
        }
        painter.rotate(6.0);
    }

    // рисуем стрелки.
    //
    QPoint points[3]; // точки для рисования.
    // узнаём текущее время.
    QTime cur_time = QTime::currentTime();
    // часовая стрелка.
    //
    // угол часовой стрелки от начального состояния (3 часа).
    const int hour_beta = 90 - (cur_time.hour() * 30
                          + cur_time.minute() / 2);
    points[0] = rotatePoint(hour_hand_a0, hour_beta, hour_hand_radius);
    points[1] = rotatePoint(hour_hand_b0, hour_beta, -hour_hand_tail_radius);
    points[2] = rotatePoint(hour_hand_c0, hour_beta, -hour_hand_tail_radius);
    painter.setPen(Qt::NoPen);
    painter.setBrush(hour_hand_color);
    painter.drawConvexPolygon(points, 3);
    // минутная стрелка.
    //
    // угол минутной стрелки от начального состояния (3 часа).
    const int min_beta = 90 - cur_time.minute() * 6;
    points[0] = rotatePoint(min_hand_a0, min_beta, min_hand_radius);
    points[1] = rotatePoint(min_hand_b0, min_beta, -min_hand_tail_radius);
    points[2] = rotatePoint(min_hand_c0, min_beta, -min_hand_tail_radius);
    painter.setBrush(min_hand_color);
    painter.drawConvexPolygon(points, 3);
    // секундная стрелка.
    //
    // угол секундной стрелки от начального состояния (3 часа).
    const int sec_beta = 90 - cur_time.second() * 6;
    points[0] = rotatePoint(sec_hand_a0, sec_beta, sec_hand_radius);
    points[1] = rotatePoint(sec_hand_b0, sec_beta, -sec_hand_tail_radius);
    points[2] = rotatePoint(sec_hand_c0, sec_beta, -sec_hand_tail_radius);
    painter.setBrush(sec_hand_color);
    painter.drawConvexPolygon(points, 3);

    // переварачиваем всё вверх ногами, так как на экране направление
    // оси ординат сверху вниз.
    painter.rotate(180);
}
//===================================================================

QPoint CClock::rotatePoint(const QPoint & point, int degree, double radius)
{
    static const double pi     = 3.14159265359;     // число Пи.

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

    // старый угол.
    double old_degree_rad = ::asin(point.y() / radius);
    // переводим угол в радианы.
    double degree_rad = degree * pi / 180.0;
    // новый угол.
    double new_degree_rad = old_degree_rad - degree_rad;

    return QPoint(::cos(new_degree_rad) * radius, ::sin(new_degree_rad) * radius);
}
//===================================================================

Ну, и использование класса для отображения в простейшем случае выглядит так

#include <QtGui/QApplication>
#include "Clock.h"

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    CClock w;
    w.show();
    return a.exec();
}

Весь необходимый код помещён в методе paintEvent класса CClock. В начале мы определяем множество констант, которые обуславливают цвет и размеры наших часов. О них я говорить не буду, так как они достаточно подробно закомментированны.

Мы определяем координаты для всех стрелок в начальном состоянии. За начальное состояние
я принял угол равный 0 градусов. На рисунке 3 показано начальное состояние стрелки, соответствующее треугольнику AoBoCo. Стрелку мы условно разделяем на две части: собственно стрелку и хвост. Хвост - это та часть, которая находится с обратной стороны точки вращения стрелки. Более подробно хвостовая часть показана на рисунке 4.

На рисунке 4 мы видим треугольники OBoDo и OCoDo. Из любого из них мы можем легко найти радиус окружности по теореме Пифагора.

Итак, координаты стрелки в начальном состоянии таковы:
Ao: x равен длине отрезка OAo, у равен нулю.
Bo: x равен длине отрезка ODo, взятой с отрицательным знаком, y равен длине отрезка DoBo, взятой с отрицательным знаком.
Co: x равен длине отрезка ODo, взятой с отрицательным знаком, y равен длине отрезка DoCo.

Так как нас больше всего интересуют стрелки, то засечки я нарисовал самым простым образом - поворачивая холст. Следует отметить, что не все библиотеки предоставляют удобные методы поворота холста.

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