Просто в теории, тяжело на деле +14



Небольшая предыстория

Учусь на втором курсе СПО, квалификация программист. Преподаватель по программированию (C#) дал на новогодние каникулы эту задачку. Решил написать статью с подробным описанием, так как многие из моей параллели её не "выкупили". 

Условие

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

Условия разработки

Так как обучение проходит только на 2 курсе, использовать можно только пройденные темы, которые включают в себя все базовые конструкции, а также структуры "коробки" для данных.


Перед написанием кода

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

Непосредственно код

Для работы с точками на плоскости хорошо было бы сделать некоторую сущность, описывающую точку:

struct Point
{
    public readonly double X;
    public readonly double Y;

    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }
}

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

Я посчитал, что удобно представить многоугольник как массив отрезков, а потом просто искать между ними пересечения с лучом, отправленным из точки куда-либо (в моей реализации луч летит вверх параллельно Oy). Для этого следует реализовать структуру отрезка:

struct Segment
{
    public Point P1;
    public Point P2;

    private double Length =>
        Math.Sqrt(Math.Pow(P2.X - P1.X, 2) + Math.Pow(P2.Y - P1.Y, 2));

    public Segment(Point p1, Point p2)
    {
        P1 = p1;
        P2 = p2;
    }
}

Тогда еще необходима функция для построения многоугольника из полученного ранее массива точек:

private static Segment[] CreatePolygon(Point[] points)
{
  var polygon = new List<Segment>();
  for (int i = 0; i < points.Length - 1; ++i)
  {
    polygon.Add(new Segment(
      new Point(points[i].X + 1e-7, points[i].Y),
      new Point(points[i + 1].X + 1e-7, points[i + 1].Y)));
  }

  polygon.Add(new Segment(new Point(points[0].X + 1e-7, points[0].Y),
                          new Point(points[points.Length - 1].X + 1e-7,
                                    points[points.Length - 1].Y)));

  return polygon.ToArray();
}

Второй абзац статьи на Вики выбранной в качестве метода для решения подсказывает, что в будущем поджидает проблема того, что луч может проходить через вершины многоугольника, что повлечет за собой проблемы (одна вершина принадлежит сразу двум отрезкам, программа засчитает сразу два пересечения), поэтому заранее добавляется та самая "бесконечно малая" (1e-7)величина к абсциссам вершин многоугольника (так как луч пойдет вертикально, то малый сдвиг по оси Oxсможет гарантировать, что луч встретит на своем пути именно ребро, а не вершину).

Луч, улетающий в бесконечность в рамках этой программы можно реализовать, как отрезок с началом в нужной точке и с концом в точке (p.X; int.MaxValue)Напишем основу для функции, которую от нас требуется написать:

public static bool IsInside(Point p, Segment[] polygon)
{
  // Vertical line towards positive Y (x = p.X, y >= p.Y)
  Segment verticalSegment = new Segment(p, new Point(p.X, int.MaxValue));

  int intersectionsCount = 0;
  foreach (var segment in polygon)
  {
  }

  return intersectionsCount % 2 != 0;
}

Внутри цикла необходимо реализовать проверку пересечения некоторого отрезка многоугольника с нашим лучом. Для этого следует реализовать метод Intersects структуры Segment. Именно на этом моменте начинаются проблемы у людей, которые плохо понимают в математике и в координатой плоскости (например, как я).

Условие пересчения двух отрезков

Пусть у нас есть два отрезка - s1 и s2. По двум точкам каждого из них мы можем получить уравнение прямой вида Ax + By + C = 0.

Каноническое уравнение прямой на плоскости
Каноническое уравнение прямой на плоскости

Если две эти прямые параллельны (A1 * B2 == B1 * A2), то и точки пересечения у них не будет, ровно как и у отрезков. В ином случае найти точку пересечения можно, решив систему уравнений:

Решение системы уравнений методом Крамера
Решение системы уравнений методом Крамера

Тогда если эта точка с координатами (x; y)принадлежит обоим отрезкам s1 и s2, то эти отрезки пересекаются. Условие принадлежности точки отрезку:

Сумма растояний от некоторой точки C до точек отрезка равна длине отрезка
Сумма растояний от некоторой точки C до точек отрезка равна длине отрезка

Дальше к написанию кода

Для начала необходимо реализовать структуру прямой вида Ax + By + C = 0, а также метод поиска точки пересечения двух таких прямых:

struct Line
{
    public readonly double A;
    public readonly double B;
    public readonly double C;

    public Line(Segment s)
    {
        var p1 = s.P1;
        var p2 = s.P2;
        A = p2.Y - p1.Y;
        B = -(p2.X - p1.X);
        C = A * -p1.X + B * -p1.Y;
    }

    public Point FindIntersectionPoint(Line line)
    {
        double determinant = A * line.B - line.A * B;
        double x = -(C * line.B - line.C * B) / determinant;
        double y = -(A * line.C - line.A * C) / determinant;

        return new Point(x, y);
    }
}

Внутри структуры Segment необходимо написать метод проверки пересечения отрезков, а также метод, проверяющий принадлежность точки отрезку:

public bool Intersects(Segment segment)
{
  var line1 = new Line(this);
  var line2 = new Line(segment);
  // if lines are not parallel
  if (Math.Abs(line1.A * line2.B - line1.B * line2.A) > 1e-9)
  {
    var intersectionPoint = line1.FindIntersectionPoint(line2);
    return this.ContainsPoint(intersectionPoint) &&
      segment.ContainsPoint(intersectionPoint);
  }

  return false;
}

public bool ContainsPoint(Point p)
{
  return Math.Abs(p.DistanceToPoint(P1) + p.DistanceToPoint(P2) -
                  Length) < 1e-9;
}

Почти финал

Все, что осталось сделать - реализовать тело цикла в искомом методе IsInside:

foreach (var segment in polygon)
{
  if (segment.ContainsPoint(p))
    return false;

  if (segment.Intersects(verticalSegment))
    intersectionsCount++;
}

Первое условие зависит от задачи - в нем проверяется, принадлежит ли искомая точка какому-то из отрезков многоугольника. В каких-то случаях необходимо возвращать true, в каких-то false. Для себя я решил, что точка на границе многоугольника не лежит непосредственно в многоугольнике, поэтому возвращаю false.

Заключение

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

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




Комментарии (63):

  1. FD4A
    /#23933547 / +1

    Случай когда отрезок лежит на луче не потеряли?

  2. MeOwn
    /#23933581 / +2

    Сработает на чём-то, вроде такого?

    • FD4A
      /#23933607

      На глаз ту всегда 2-4 пересечения, так что по идее да.

    • robesper
      /#23933649 / +1

      когда-то решал эту задачу. Все оказалось куда сложнее, так как много частных случаев: кольцо, подкова и пр. У меня также были сегменты-дуги, что еще больше затрудняло выполнение. Решение по объему могло бы стать если не дипломной, то курсовой работой точно.

      • abutorin
        /#23933833 / +1

        Общий алгоритм простой. Все сводится к определению количества пересечений с гранями. Для каждого вида грани (прямая, кривая) просто нужно реализовать свою процедуру опредения количества пересечений с лучом.

        • robesper
          /#23937711 / -1

          да, алгоритм простой, но не отрабатывает некоторых случаев. Я общался с профессиональным математиком. Он знал эту и несколько других методик (сейчас не вспомню каких). Ни одна не покрывала 100% случаев.

    • ViacheslavNk
      /#23935047

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

  3. abutorin
    /#23933687 / +6

    что повлечет за собой проблемы (одна вершина принадлежит сразу двум
    отрезкам, программа засчитает сразу два пересечения), поэтому заранее
    добавляется та самая "бесконечно малая" (1e-7)величина к абсциссам вершин многоугольника

    Кажется что "прибавлять" бесконечно малые отклонения не лучший вариант. Ведь вся сложность с в случае "попадания" в вершину в выбраном алгоритме определения факта пересечения грани. Чтобы исключить двойное "засчитывание" при попадании в вершину, достаточно проверять не вовпадает ли точка пересечения луча и ребра с одной из вершин многогранника, если сопадает, то просто вычитать 1 из числа пересечений.

    • ShadowTheAge
      /#23933787 / +4

      можно еще проще. Считать попаданием в начальную точку отрезка, но не считать в конечную. Т.е. для одной из точек условие будет что то типа >= а для второй строго >

      • t13s
        /#23933873

        Нельзя :)

        Во-первых, в реальной жизни полное равенство двух double - штука маловероятная. Собственно, поэтому тут везде дельта.

        Во-вторых, а что такое "начало отрезка"?
        И пока вы не ответили, спрошу еще: а что мешает иметь два отрезка, заданные как (A, B) и (A, C)?

        • ShadowTheAge
          /#23933961 / +1

          Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)


          Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого


          Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)


          Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.


          Последний вопрос я не понял

          • avdx
            /#23934133

            Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.

            • ShadowTheAge
              /#23934389 / +1

              Поэтому и "второй вариант".

              • avdx
                /#23934625 / +1

                Из описания сначала не понял суть "второго варианта". Ну так да, он будет правильно обрабатывать. Наверное это самый простой и эффективный способ корректной реализации данного алгоритма.

          • t13s
            /#23934179

            Точка, из которой луч попадает в вершину, может являться результатом каких-то других вычислений. То есть в совсем общем случае я бы не гарантировал совпадения хотя бы одной из координат побитово (хотя в вашем продакшен случае это вполне может быть именно так).

            А в случае обхода полигона надо тогда добавить шаг фильтрации, который будет выкидывать отрезки, длина которых сравнима с дельтой.

            Про последний вопрос: видимо, тут разница в понимании того, как может быть задан полигон. Вы подразумеваете, что он задается подряд идущими сегментами: (A, B), (B, C), (C, D), ..., (Z, A). Но в общем случае полигон может быть задан как попало: (C, B), (A, B), ..., (A, Z), (D, C).

            • ShadowTheAge
              /#23934401 / +1

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


              Полигон это массив точек а не отрезков. В отрезки уже превращаем его мы в алгоритме, и мы можем это сделать аккуратно.


              Ну и "второму варианту" на порядок пофиг, а он все равно лучше первого

      • wataru
        /#23935653

        Нет, правильно — считать нижнюю точку отрезка, а горизонтальные можно тупо игнорировать. Тогда нормально обработаются случаи, когда многоугольник касается луча сверху или снизу вершиной (будет 0 или 2 пересечений). И случай, когда луч проходит через вершину (будет 1 пересечение от верхнего отрезка).

        • ShadowTheAge
          /#23936185

          В статье выпускаемый луч вертикальный поэтому правильно считать по Х а не по У

    • SlFed
      /#23934335 / +3

      Добалю про "бесконечно малую". Нас в институте на такой фразе сразу обрывали и посылали переделывать курсовик.... Тогда-то и приучили что нет просто малых или просто больших величин - они всегда малы или велики по сравнению с чем-то.

      Вы не знаете заранее насколько велики или малы будут координаты точек, соответственно абсолютное значение смещения может либо быть проигнорировано при сложении (координаты имеют порядок 1e+20 или больше), либо может привести к серьезному сдвигу всей фигуры (координаты порядка 1e-8 ).

      Минимально тут надо поправить на вычисление относительного сдвига, например 0,00001% от координаты проверяемой точки.

  4. t13s
    /#23933783 / +3

    Если слегка поревьювить:

    1. Почему точки отрезка (Segment) мутабельные?

    2. Массив отрезков, в общем случае, полигоном не является.

    3. Портить координаты дельтой, действительно, не хорошо.
      Должно быть достаточно ввести некий tolerance для сравнения вещественных чисел.
      Ну и само это сравнение вынести в отдельный метод, не размазывая по коду.

    4. Кстати, как эта "порча" должа помочь избежать двойного зачета точки, если портятся абсолютно все точки полигона?

  5. ShadowTheAge
    /#23933807 / +1

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

  6. Exclipt
    /#23933829

    Тоже давали такую задачу где-то в середине обучения в универе, только это было примерно в 2000-м году и задачу дали не преподаватели, а сотрудники фирмы Esma (картография), которые искали себе джунов. Решил примерно похожим способом на паскале, но с нюансами (с википедией тогда были некоторые проблемки).

    В кажестве теста тогда делали "заливку" цветом фигуры по этому алгоритму, наглядно было видно, какие нюансы не учел.

    • KongEnGe
      /#23933879 / +1

      Что задачу давал -- помню, а кому именно -- уже не помню :)

      • Exclipt
        /#23933989

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

        Еще помню там же упоминалась задача вида "как определить в какой последовательности рисовать стены домов на 3д карте".

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

  7. Andy_U
    /#23933861

    А учли ли в случаи, когда:

    1. Ваш луч из точки наружу пройдет через точку, определяющую границу многоугольника. Тут можно или два раза посчитать, или ноль. Координаты же вещественные?

    2. Ваш луч точно ляжет на ребро между двумя точками, определяющими многоугольник?

    • Exclipt
      /#23934059

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

      • Andy_U
        /#23935117

        Именно. Мне вообще кажется, что тут нужно переходить на квадратную (целочисленную, с точностью до масштаба сетку), точки в узлах, все (наклонные) линии превращаются в последовательности вертикальных и горизонтальных отрезков. Тогда никаких проблем с точностью вычисленией нет. Ну, пересечение луча и отрезка будет интереснее считать (это может быть не точка а отрезок). А, может, можно и наклоны с рациональными тангенсами разрешить? Но как бы тогда и арифметика с произвольной разрядностью не потребовалась?

        • ShadowTheAge
          /#23935531

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

  8. Gutt
    /#23934437

    Если многоугольник задан только точками, то зачастую существует несколько способов его построения, отличающихся порядком соединения точек:

    Поэтому получать на входе массив вершин -- так себе идея, нужно требовать сразу отрезки.

    • abutorin
      /#23934481 / +3

      нужно требовать сразу отрезки

      А затем сразу проверять что они имеют общие "концы"? А если нет?

      Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.

      • Gutt
        /#23934637 / +1

        А затем сразу проверять что они имеют общие "концы"? А если нет?

        Ну да. Это ведь будут просто общие координаты. А если нет -- то нет и многоугольника, и полные исходные данные отсутствуют. Потом придётся ещё проверить, что отрезки не пересекаются.

        Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.

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

        • abutorin
          /#23934755

          "внутри многоугольника" станет намного труднее определить

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

    • ShadowTheAge
      /#23935013 / +3

      Массив это не множество — массив уже имеет порядок. Массив точек однозначно задает многоугольник.


      Для данного конкретного алгоритма самопересечение многоугольника не играет роли.

  9. pyur
    /#23934623

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

    • abutorin
      /#23934741

      Треугольник по каким точкам вы хотите строить? От произвольной точки многогранника и 2-м другим? Этот вариант годится для выпукного многогранника, а например для "подковы" уже не подойдёт.

    • wataru
      /#23935683

      Можно, но это на порядки сложнее. Если многугольник невыпуклый, то его триангулировать — та еще задачка. И дальше проверки на принадлежность треугольнику будут дольше, чем проверка на пересечение с отрезком.


      Но есть особый случай, когда похожий на ваш метод — лучше. Если надо быстро определеять принадлежность многих точек к выпуклому многоугольнику. Тогда надо разбить многоугольник на трапеции горизонтальными линиями. Потом для каждого запроса бинпоиском найти тот срез, к которому точка может относится и дальше проверить, что она лежит между левой и правой границей трапеции.

  10. bullitufa
    /#23934643

    А есть тест кейсы?

    Я б поупражнялся бы)

  11. kovserg
    /#23934789

    А нельзя было как-то проще сделать?

    bool inside(Point t, Point[] p) {
      double d; int c=0, n=p.Length;
      for(int i=0;i<n;i++) {
        int a=i, b=i+1; if(b>=n) b-=n;
        if (p[a].y>p[b].y) { a=b; b=i; }
        if ((p[a].y<=t.y && t.y<=p[b].y)) {
          if (p[a].y!=p[b].y) {
            d=(p[a].x-p[b].x)*(t.y-p[a].y)-(p[a].y-p[b].y)*(t.x-p[a].x);
            if (d==0) { c=1; break; }
            if (d<0) c++;
          }
        }
      }
      return (c&1)==1;
    }
    

    • kovserg
      /#23935833 / +1

      Исправленый вариант

      bool inside(Point t, Point[] p) {
        double d; int c=0, n=p.Length;
        for(int i=0;i<n;i++) {
          int a=i, b=i+1; if(b>=n) b-=n;
          if (p[a].y>p[b].y) { a=b; b=i; }
          if (p[a].y<=t.y && t.y<=p[b].y) {
            if (p[a].y==p[b].y) {      
              if ((p[a].x-t.x)*(p[b].x-t.x)<=0) { c=1; break; }
            } else {
              d=(p[a].x-p[b].x)*(t.y-p[a].y)-(p[a].y-p[b].y)*(t.x-p[a].x);
              if (d==0) { c=1; break; } if (d<0) c++;
            }
          }
        }
        return (c&1)==1;
      }
      

  12. hfinn
    /#23934873 / +1

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

    • ShadowTheAge
      /#23934957 / +4

      Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)

      • hfinn
        /#23935045

        Искать не надо. Треугольник - это любые три последовательные точки в массиве.

        • Exclipt
          /#23935169 / +1

          а как определять, что площадь этого треугольника принадлежит фигуре, а не вне ее?

          • hfinn
            /#23935717

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

            • ShadowTheAge
              /#23936205 / +2

              Вы должны доказать что это работает, а не "не могу придумать варианта".


              Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.

              • hfinn
                /#23938739

                Вижу, что вы не поняли алгоритм. Перечитайте внимательнее. Я же про это как раз и написал. Аж два раза. Если точка лежит в треугольнике — мы этот треугольник не трогаем вообще, поскольку не знаем, принадлежит ли он (вместе с точкой) многоугольнику или нет. Но если точки там нет, то нам без разницы, уменьшаем мы площадь многоугольника или увеличиваем, удалив этот треугольник, — точка от этого не перескачет границу многоугольника и не перестанет принадлежать или не принадлежать ему.

                • ShadowTheAge
                  /#23941875

                  Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.


                  Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.


                  Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.

                  • hfinn
                    /#23943357

                    Та же история. Мы не можем ничего намотать вокруг точки по этому алгоритму. Но, действительно, должны выделить случаи, когда вокруг точки намотано изначально (как в звезде с точкой по центру), и сделать вывод о принадлежности точки многоугольнику при принадлежности её всем оставшимся треугольникам.

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

                    Насчёт O(N) надо смотреть. Вроде бы не должно быть сильно больше — нам же достаточно каждый треугольник просчитать только один раз, а пустые треугольники тут же удаляются.

        • DimPal
          /#23935289

          Если полигон выпуклый то триангулизация тривиальна. Но для вогнутого все сложно. Тут скорее BSP подход был бы эффективнее...

        • ShadowTheAge
          /#23935513

          В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)


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

  13. chnav
    /#23935937 / +2

    Небольшой читинг. Несколько лет назад понадобилось инжектировать подобную задачу в ARM-бинарник. Само собой был нужен максимально эффективный и простой алгоритм,нагуглил этот:

    A winding Number and Point-in-Polygon Algorythm, David G. Alciatore, Colorado State University (скан, PDF)

    Работает даже с некоторыми самопересекающимися полигонами (в документе есть пример пятиконечной звезды). Вкратце - считается количество оборотов, которое линия сделала вокруг указанной точки, т.е. можно нарисовать спираль, вернуться обратно, ткнуть точку - и алгоритм укажет попали или нет.

    После некоторых оптимизаций удалось полностью избавиться от деления и обойтись двумя операциями умножения на цикл (функция DotProduct). Фокус в том, что в основном интересуют знаки операций, а не их значения. Пример подобных оптимизаций в комментарии @kovserg выше.

    Проверку на нахождение точки точно на линии я тогда не рассматривал, ИМО это отдельный случай.

    • chnav
      /#23936247

      ...а может и не отдельный, если анализировать DotProduct на ноль... детально не помню...

  14. Nail_S
    /#23936349

    Согласен с автором что задача весьма не тривиальна.

    Для себя в свое время решил, что лучше уйти от Float вычислений на Int.

    Если интерессно нашел свой репозиторий с этим участком кода, как раз на C#

    https://github.com/iShapeUnity/Clipper/blob/master/Runtime/iShape/Clipper/Util/PolygonExt.cs

  15. skiedr
    /#23936809

    Можно площадь всех треугольников посчитать с этоц точкой, и без нее. И сравнить что больше.

  16. GooG2e
    /#23938145

    На олимпиаде была подобная задача - нужно было на SQL решать. Вот тут было веселье)

  17. Lyova5
    /#23940977

    Казалось бы, это задача на углы, а не на лучи-отрезки. Если просуммировать все углы, под которыми видно стороны многоугольника, для внешней точки должен получиться ноль, для внутренней - 2*Math.PI.

  18. AntZ_RU
    /#23940979

    В .NET есть стандартные средства для решения подобной задачи System.Drawing.Graphics.IsVisible

  19. RegressX
    /#23940981

    Еще можно попробовать таким образом: представить многоугольник в виде нескольких треугольников, затем проверить принадлежность точки каждому из треугольников.

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

  20. Vitya_Nikolayev
    /#23940983

    Лично я когда ещё был школьником всегда использовал метод учёта оборотов, по-моему он гибче и под микроусловия в олимпиадках подстроиться проще (и лично мне чуть более понятно): Самопересечения не входят? - Не вопрос - посчитаем сколько оборотов делает, а если входят - просто смотрим близка ли сумма к нулю

  21. VladPavlushin
    /#23940985

    Если площадь небольшая - Создаем массив пикселей, у каждой координаты, - проверяем принадлежит ли точка массиву. а если в процессе создания провера идет, можем сократить до совпадения.

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

  22. Kyselov1
    /#23940987

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

  23. oleg1977
    /#23942329

    Интересно, это в условии задачи оговорено явно, что координаты вещественные или автор так решил?

  24. oleg1977
    /#23942345

    MaxInt может оказаться меньше координат полигона