Рассмотрим потенциально самопересекающийся многоугольник, определенный списком вершин в двумерном пространстве. Например
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Есть несколько способов определить площадь такого многоугольника, но наиболее интересным является правило четного нечетного. Взяв любую точку на плоскости, проведите линию от точки до бесконечности (в любом направлении). Если эта линия пересекает многоугольник нечетное число раз, точка является частью области многоугольника, если она пересекает многоугольник четное число раз, точка не является частью многоугольника. Для приведенного выше примера многоугольника здесь представлены как его контур, так и четно-нечетная область:
Многоугольник в общем случае не будет ортогональным. Я выбрал только такой простой пример, чтобы было легче подсчитать площадь.
Область этого примера 17
(нет 24
или 33
как могут дать другие определения или область).
Обратите внимание, что согласно этому определению площадь многоугольника не зависит от порядка его намотки.
Соревнование
Учитывая список вершин с целочисленными координатами, определяющими многоугольник, определите его площадь по четно-нечетному правилу.
Вы можете написать функцию или программу, используя ввод через STDIN или ближайшую альтернативу, аргумент командной строки или аргумент функции, и либо вернуть результат, либо распечатать его в STDOUT или ближайшую альтернативу.
Вы можете принимать ввод в любом удобном формате списка или строки, если он не был предварительно обработан.
Результатом должно быть либо число с плавающей запятой с точностью до 6 значащих (десятичных) цифр, либо рациональный результат, представление которого с плавающей запятой с точностью до 6 значащих цифр. (Если вы дадите рациональные результаты, они, вероятно, будут точными, но я не могу требовать этого, поскольку у меня нет точных результатов для справки.)
Вы должны быть в состоянии решить каждый из приведенных ниже тестовых случаев в течение 10 секунд на подходящем настольном компьютере. (В этом правиле есть некоторая свобода действий, поэтому примите во внимание свое мнение. Если на моем ноутбуке это займет 20 секунд, я извлеку выгоду из сомнений, если это займет минуту, я не буду.) Я думаю, что это ограничение должно быть очень щедрым, но предполагается исключить подходы, в которых вы просто дискретизируете многоугольник на достаточно тонкой сетке и рассчитываете, или используете вероятностные подходы, такие как Монте-Карло. Будьте хорошим спортсменом и не пытайтесь оптимизировать эти подходы так, чтобы вы все равно могли уложиться в сроки. ;)
Вы не должны использовать какие-либо существующие функции, связанные непосредственно с полигонами.
Это код гольф, поэтому выигрывает самое короткое представление (в байтах).
Предположения
- Все координаты являются целыми числами в диапазоне
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Там будет хотя бы
3
и не больше50
вершин. - Повторных вершин не будет. Ни одна из вершин не будет лежать на другом ребре. ( Хотя в списке могут быть коллинеарные точки.)
Тестовые случаи
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
источник
upath
оператора. (На самом деле это чрезвычайно простое преобразование 1: 1 между разделителями.}, {
Просто становитсяlineto
, и запятая между x и y удаляется, а открывающие и закрывающие скобки заменяются статическимupath
иlineto
звучит так, будто вы на самом деле предварительно обрабатываете ввод. Т.е. вы берете не список координат, а фактический многоугольник.CrossingPolygon
.Ответы:
Mathematica,
247225222Сначала добавьте точки пересечения к многоугольнику, затем поменяйте местами некоторые ребра, затем его площадь можно рассчитать так же, как простой многоугольник.
Пример:
источник
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Вы должны выйти с 3.433333333333309. Я посмотрел на использование аналогичной логики.103/30
, и числовое значение равно3.43333
.Python 2,
323319 байтПринимает список вершин через STDIN как комплексные числа в следующем виде
и записывает результат в STDOUT.
Тот же код после замены строки и некоторый интервал:
объяснение
Для каждой точки пересечения двух сторон входного многоугольника (включая вершины) пропустите вертикальную линию через эту точку.
(На самом деле, из-за игры в гольф программа пропускает еще несколько линий; это не имеет значения, если мы проходим хотя бы эти линии.) Тело многоугольника между любыми двумя последовательными линиями состоит из вертикальных трапеций ( и треугольники, и отрезки, как особые случаи). Это должно быть так, поскольку, если бы у какой-либо из этих фигур была дополнительная вершина между двумя основаниями, через эту точку была бы другая вертикальная линия между двумя рассматриваемыми линиями. Сумма площадей всех таких трапеций представляет собой площадь многоугольника.
Вот как мы находим эти трапеции: для каждой пары последовательных вертикальных линий мы находим сегменты каждой стороны многоугольника, которые (должным образом) лежат между этими двумя линиями (которые могут не существовать для некоторых сторон). На приведенном выше рисунке это шесть красных сегментов при рассмотрении двух красных вертикальных линий. Обратите внимание, что эти сегменты не пересекаются должным образом (т. Е. Они могут встречаться только в конечных точках, полностью совпадать или вообще не пересекаться, поскольку, опять же, если они правильно пересекаются, между ними будет другая вертикальная линия;) и поэтому имеет смысл поговорить о порядке их сверху вниз, что мы и делаем. Согласно четно-нечетному правилу, когда мы пересекаем первый сегмент, мы находимся внутри многоугольника; как только мы пересекаем второй, мы уходим; третий снова; четвертый, вне; и так далее...
В целом, это алгоритм O ( n 3 log n ).
источник
Хаскелл, 549
Не похоже, что я могу сыграть в эту игру достаточно далеко, но концепция отличалась от двух других ответов, поэтому я решил, что все равно поделюсь этим. Он выполняет O (N ^ 2) рациональных операций для вычисления площади.
Пример:
Идея состоит в том, чтобы заново соединить многоугольник при каждом пересечении, что приведет к объединению многоугольников без пересекающихся ребер. Затем мы можем вычислить (подписанную) область каждого из многоугольников, используя формулу Гаусса для шнурков ( http://en.wikipedia.org/wiki/Shoelace_formula ). Четно-нечетное правило требует, чтобы при пересечении пересечения площадь нового многоугольника считалась отрицательно относительно старого многоугольника.
Например, рассмотрим многоугольник в исходном вопросе. Пересечение в верхнем левом углу преобразуется в два пути, которые встречаются только в точке; оба пути ориентированы по часовой стрелке, поэтому области каждого будут положительными, если мы не объявим, что внутренний путь взвешен на -1 относительно внешнего пути. Это эквивалентно изменению пути альфаальфы.
В качестве другого примера рассмотрим многоугольник из комментария MickyT:
Здесь некоторые полигоны ориентированы по часовой стрелке, а некоторые против часовой стрелки. Правило «знак переворачивания» гарантирует, что области, ориентированные по часовой стрелке, получают дополнительный коэффициент -1, что приводит к тому, что они вносят положительный вклад в площадь.
Вот как работает программа:
источник