Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Categories:

Попадание точки в многоугольник. Количество заныриваний не равно количеству выныриваний.

Есть точка O, есть многоугольник A[n] на плоскости. Надо выяснить, попадает ли точка в многоугольник.

Основа алгоритма описывается очень просто: давайте возмём бесконечный горизонтальный луч из точки направо. Если луч пересекает границу четное число раз (в том числе 0 раз) , то точка вне многоугольника. Если нечетное число раз - то внутри.



Затем программист пытается обработать хитрые случаи: луч проходит через вершину многоугольника, сторона многоугольника совпадает с лучом. В коде возникают какие-то if, какие-то EPSILON..., молитвы о том, что редкие случаи когда две точки на расстоянии EPSILON но луч между ними - не существуют, насильно изгонясь из сознания

Надо так: надо работать не со сторонами, а с вершинами. Для каждой вершины A[n] - вычисляем булевский флажок, находится точка над или под лучом, то есть просто сравниваем координату y вершины с нулем, flag[n] = A[n] < 0. Затем идем по парам точек (A[n-1],A[n]) и считаем пересечения когда этот флажок меняется с true на false и наоборот. При этом проверяем, что отрезок проходит справа от точки O, для этого сравниваем знак определителя |A[n-1]-A[n], A[n]-O| с 0. Определитель получается не из божественного откровения, а из выражения для x-координаты пересечения отрезка и луча.

Алгоритм устойчив к дрожанию вершины на любой epsilon, к случаю когда она попадает почти на луч или ровно на луч. Например, на картинке 1) ниже - будет засчитано или ровно два пересечения, или ровно ноль. Даже если точка попадает ровно на луч. Благодаря дискретной природе булевского значения в точке - оно или true, или false, и количество их переключений - строго дискретно. Или меняется сразу на 2, но никак на 1. На картинке 2) - будет зачитано ровно одно пересечение, или на отрезке AB или на отрезке BC. Ни в коем случае не на двух сразу, и ни в коем случае не будет случайно пропущен один из двух отрезков.



Функция целиком, 30 строчек, никакой лапши из epsilon и особых случаев:

bool IsPointInside(Array<const Point2f> polygon, Point2f point)
{
    if (polygon.size <= 1)
        return false;

    int intersections_num = 0;
    int prev = polygon.size - 1;
    bool prev_under = polygon[prev].y < point.y;

    for (int i = 0; i < polygon.size; ++i)
    {
        bool cur_under = polygon[i].y < point.y;

        Point2f a = polygon[prev] - point;
        Point2f b = polygon[i]  - point;

        float t = (a.x*(b.y - a.y) - a.y*(b.x - a.x));
        if (cur_under && !prev_under)
        {
            if (t > 0)
                intersections_num += 1;
        }
        if (!cur_under && prev_under)
        {
            if (t < 0)
                intersections_num += 1;
        }

        prev = i;        
        prev_under = cur_under;        
    }

    return (intersections_num&1) != 0;
}
_Winnie C++ Colorizer



Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Пересечение двух отрезков
Tags: geom-prog, math, paint mad skilz, release, soft-dev
Subscribe

  • CR LF

    В некоторых файлах в некоторых контекстах надо байты '\r\n' интерпретировать так же, как как байт '\n' (например, чтение значения из рукописного…

  • Что такое оттенок цвета.

    Матовый объект, который отражает падающий свет во все стороны, не меняя его спектральный состав - белый, т.е. бесцветный. Если свет отражается…

  • mspaint circles

    По ходу работы скриптов рисовал в задумчивости кружочки по-быстрому (под рукой оказался mspaint), внезапно вылезло вот такое:

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 25 comments

  • CR LF

    В некоторых файлах в некоторых контекстах надо байты '\r\n' интерпретировать так же, как как байт '\n' (например, чтение значения из рукописного…

  • Что такое оттенок цвета.

    Матовый объект, который отражает падающий свет во все стороны, не меняя его спектральный состав - белый, т.е. бесцветный. Если свет отражается…

  • mspaint circles

    По ходу работы скриптов рисовал в задумчивости кружочки по-быстрому (под рукой оказался mspaint), внезапно вылезло вот такое: