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

Как видно из рисунка 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);
    }
}