Хочешь чуда? Будь чудом!
Есть класс Polygon, в котором хранятся координаты вершин (с обходом против часовой стрелки).
Сам полигон по себе может быть выпуклым многоугольником, а может и не выпуклым. Но стороны его друг друга не пересекают, ну это понятное дело.
Есть класс Line, в котором хранятся два параметра, определяющие прямую (y=kx+b).
Нужно написать функцию:
Polygon* function(Poigon poly,Line* line),
в которую передается полигон и массив прямых.
И нужно вернуть массив полигонов, на которые исходный полигон поделится этими прямыми.
Я просто с геометрией не в ладах еще со школы, а с вычислительной геометрией и того =(
Пока что считаю, что полигон у меня изначально задан верно (то есть безо всяких проверок на пересечения и прочее).
Но проблема с алгоритмом.
Например полигон и одна прямая:
1) найти точки пересечения сторон полигона и прямой (тут маленькая проблема из разряда - точку пересечения прямых я найду без проблем, но мне нужна точка пересечения прямой и отрезка. как можно провести такое ограничение?)
2) беру первую точку пересечения. иду тоже с обходом против часовой. получается, что должна быть как минимум одна вершина между двумя точками пересечения.
но мне не понятно, как сделать условие того, что я беру именно нужную мне вершину нового полигона.
и не понятно, как сделать проверку на то, что полигон новый у меня получился и его можно передать в массив...
и в какой момент мне выделить память для массива, в который я передаю новые полигоны? я же не знаю их количество до того, пока не найду количество точек пересечения...
не то, чтобы в панике, но в растерянности...
Сам полигон по себе может быть выпуклым многоугольником, а может и не выпуклым. Но стороны его друг друга не пересекают, ну это понятное дело.
Есть класс Line, в котором хранятся два параметра, определяющие прямую (y=kx+b).
Нужно написать функцию:
Polygon* function(Poigon poly,Line* line),
в которую передается полигон и массив прямых.
И нужно вернуть массив полигонов, на которые исходный полигон поделится этими прямыми.
Я просто с геометрией не в ладах еще со школы, а с вычислительной геометрией и того =(
Пока что считаю, что полигон у меня изначально задан верно (то есть безо всяких проверок на пересечения и прочее).
Но проблема с алгоритмом.
Например полигон и одна прямая:
1) найти точки пересечения сторон полигона и прямой (тут маленькая проблема из разряда - точку пересечения прямых я найду без проблем, но мне нужна точка пересечения прямой и отрезка. как можно провести такое ограничение?)
2) беру первую точку пересечения. иду тоже с обходом против часовой. получается, что должна быть как минимум одна вершина между двумя точками пересечения.
но мне не понятно, как сделать условие того, что я беру именно нужную мне вершину нового полигона.
и не понятно, как сделать проверку на то, что полигон новый у меня получился и его можно передать в массив...
и в какой момент мне выделить память для массива, в который я передаю новые полигоны? я же не знаю их количество до того, пока не найду количество точек пересечения...
не то, чтобы в панике, но в растерянности...
-
-
09.10.2010 в 16:32отрезок - (x1,y1), (x2,y2).
пусть x1>x2
тогда тогда если точка пересечения лежит в отрезке, то x1>x0>x2
в случае если у отрезка x1=x2, то анологично сравнивается по y
2) не поняла, что точно хотите.
как понять вышел полигон или нет?
сделайте тестовую функцию, которая будет проверять все условия - я так понимаю - это олтсутствие пересечения отрезков сторон
вместо массива можно сделать список, ну а память выделять, как только у вас появится новый полигон. ну или плохой вариант - оценить больше скольки не может появиться полигонов и выделять для нужного кол-ва, тогда можно заранее.
-
-
09.10.2010 в 18:131) за это спасибо.
2) сейчас может попробую на примере...
картинки не грузятся, поэтому я попробую на пальцах.
Типа алгоритм для частного случая...
есть координаты вершин полигона в обходе против часовой: (0,0),(1,-1),(2,0),(2,1),(1,0),(1,1),(0,1)
и пересекаем его прямой у=0 (то есть k=0, b=0).
В итоге мы получаем три точки пересечения: (0,0),(1,0),(2,0)
берем первую точку пересечения: (0,0) - и обходим против часовой - (0,0),(1,-1),(2,0)
попадаем в еще одну точку пересечения.
здесь по идее заканчиваем - мы получили первый полигон.
берем вторую точку пересечения: (1,0).
Тоже обходим:
(1,0),(1,1),(0,1),(0,0)
вот и второй.
третий аналогично.
вот тут сразу проблемы у меня:
1) как мне выбрать именно нужную точку?
чтобы обход был против часовой.
в том смысле, что взяв точку (0,0) я могу взять или (0,1) или (1,-1).
и аналитически я не знаю, как это сделать.
а тем более перевести это на язык...
2) как сделать условие выхода, то есть когда полигон получился.
это олтсутствие пересечения отрезков сторон
я не понял вот этого. если можно - было бы хорошо мне пояснить...
у меня была идея того, что мы выходим, когда доходим до второй точки пересечения.
Это в принципе ИНОГДА работает, но не всегда.
Например в этом примере мне не нужно тогда будет делать полигон: (0,0),(1,-1),(2,0),(1,0)
Потому что до точки (1,0) мы как бы не доходим.
И в принципе получается верный ответ.
А пример, когда это не работает:
такой вот полигон:
(0,0),(0,3),(2,1),(2,3),(4,1),(4,0)
и прямая у=2
тогда то условие выхода уже не работает, потому что у нас получится один полигон
(0,0),(0,2),(1,2),(2,1),(2,2),(3,2),(4,1),(4,0)
и у нас четыре точки пересечения в нем.
если бы мы начинали с точек (1,2) или (3,2), то мы получим два хвостика этих
если с точки (0,2), то мы потеряем так кусок фигуры...
надеюсь я смог хоть как то внятно описать проблему...
в общем вот так.
нужен алгоритм...
-
-
09.10.2010 в 18:45а) пересечение - совпадает с концом отрезка(вершина полигона, как в примере) - точка следующая в массиве(задающей полигон), после этой
б) внутри отрезка - конец отрезка, который в массиве стоит дальше
у вас же полигон - это массив, который перебирает точки против часовой стрелке.
и еще вопрос - вы режете прямыми полигон или смотрете, какие с тем прямыми можно там найти полигоны(во втором случае сколько в ответе должно получиться полигонов - 3 или 6? или другое число?)
-
-
09.10.2010 в 19:37не получается...
Например
такой вот полигон:
(0,0),(4,0),(4,1),(2,3),(2,1),(0,3)
и прямая у=2
Беру первую точку (0,2) - она внутри отрезка, значит идем в (0,0).
Это вершина - идем в (4,0)
Это вершина - идем в 4,1
Это вершина - идем в 3,2
Это внутри отрезка - идем в конец отрезка, который в массиве стоит дальше и это 2,3
а надо попасть в 2,2...
если я неправильно понял, прошу меня поправить.
но мне кажется. что тут не так просто, как на первый взгляд...
я должен разрезать прямыми полигон на части, так словно это части мозаики.
чтобы склеив их можно было бы получить исходный полигон.
так что и там и там их три получается (в моих примерах)
-
-
09.10.2010 в 20:15если попадаем в точку, которая внутри отрезка, то у нас есть 2 направления куда пойти - первое, по стороне, второе по проведенной прямой. в случае, если проведенная прямая идет внутри полигона, тогда идем по ней, в случае, если снаружи, то идем по отрезку.
и в начале рекомендую взять вершину, которая не была получена прямой, там из 3х направлений тоже выбирать. понятно как, но замучаешься уравнения писать.
что бы разбить весь полигон нужно проверить: объеденение вершин всех полученных полигонов должно содержать все вершины изначального полигона, иначе пока можно бегать по начальным вершинам.
-
-
09.10.2010 в 20:20что бы разбить весь полигон нужно проверить: объеденение вершин всех полученных полигонов должно содержать все вершины изначального полигона, иначе пока можно бегать по начальным вершинам.
так хорошо. спасибо.
на словах разобрались.
но воплощение этого даже в устной форме на языке проще не стало...
потому что сравнивать множества точек я представляю себе только как сравнение двух объектов.
а проверка нахождения прямой внутри или снаружи полигона - это сравнение со всеми отрехками-сторонами полигона - то есть для этого тоже все проверки сделать...
если я правильно понял..
-
-
10.10.2010 в 00:15до кучи рассмотреть характерные случаи. например фигура: шестиугольник без одной шестой (а-ля пэкман), прямая проходит через две вершины и центр. Или ножовке отрезают концы зубов. если из рассмотрения выкинуть невыпуклые, то можно эти фигуры не рассматривать
определять с кем было пересечение - действительно проверить всех по-очереди. выходное отверстие, что характерно, можно искать по несмежным вершинам и исключив текущую сторону.
-
-
10.10.2010 в 01:41да, там много проверок. возможно это не самое краткое решение. ну лично я все задачами,с которыми сталкивалась в планиметрии, представлялись мне достаточно громоздкие и муторными для проверок. но с другой стороны я никогда не интересовалась этой темой и скорее всего там есть какие-нибудь быстрые и прикольные алгоритмы.
а то что выше - это первое, что в голову приходит.
-
-
10.10.2010 в 12:16вот сидел пять минут и не смог понять, что имелось в виду...
так. а в чем теперь проблема воплощения?
в том, что моего мозга не хватает, чтобы запихнуть туда все детали.
что то все время за край переливается.
мне нужно прямо четкое понимание по пунктам, пока такого нет.
сегодня посижу, может что и сочиню.
если что еще обращусь.
сейчас надо немного систематизировать
-
-
10.10.2010 в 18:39полигон (набор координат его вершин)
и отрезок (две точки по две координаты)
как проверить - отрезок лежит вне этого полигона, или внутри него?
-
-
10.10.2010 в 18:59Буду признателен, если кто-то это "протестирует".
В общем начинаю с класса:
class Ring{
int x; /координаты
int y;
int b; // датчик, b=0 - непройденная вершина, b=1 - точка пересечения, b=2 - пройденная вершина (пройденная - имеется в виду во время составления новых полигонов)
Ring* p; // указатель на следующую точку
}
class Poygon{
Ring ring;
void Input(); // ввод полигона
int Quantity(); // возвращает количество непройденных вершин
void Push(...); // втыканеие еще одной точки в нужное место в кольце
}
Сам алгоритм такой:
1) Составляе полигон в виде кольца. Замкнутого списка то есть.
Пока не знаю точно, как я это буду делать, но пока считаю, что он у меня есть.
2) Находим точки пересечения прямой со сторонами полигона.
Втыкаем их в кольцо в нужное место (если точка пересечения лежит на стороне)
или же меняем значение датчика b соответствующей точки с нуля на единицу (если точка пересечения совпадает с вершиной)
3) Берем первую непройденную вершину и передаем ее в новое кольцо, попутно меняем значение датчика с 0 на 2. Идем дальше до того момента, пока не наткнемся на точку пересечения. Если мы дошли до точки пересечения, то ищем первую следующую точку пересечения. Затем надо проверить, лежит ли этот отрезок внутри полигона или нет (ПОМОГИТЕ ЭТО СДЕЛАТЬ. была идея проверить принадлежит ли середина отрезка полигону, но это тоже не гарантирует принадлежность всего отрезка полигону... в общем - это пока самое большое пустое место в алгоритме).
Если этот отрезок лежит внутри полигона - тогда идем дальше, как и шли до этого.
Если он не лежит внутри полигона целиком, тогда ищем первую точку пересечения, но в обратную сторону. И дальше продолжаем идти в первоначальную сторону обхода.
Когда приходим в начальную вершину, то замыкаем новое кольцо и наш полигон готов.
4) Дальше берем следующую вершину и проделываем то же самое.
5) Выходим из всего этого тогда, когда количество непройденных вершин в исходном кольце равно нулю.
В общем как-то так.
Нужен свежий взгляд и небольшая помощь...
-
-
10.10.2010 в 21:26-
-
10.10.2010 в 22:04я не понимаю этого условия. можно объяснить его по-другому?
если середина отрезка принадлежит внутренности полигона, то и отрезок принадлежит внутренности полигона.
я бы не писал, что у меня по этому поводу сомнения, если бы не было примера.
Вот пример:
полигон в обходе против часовой:
(0,0),(5,0),(5,2),(4,2),(4,1),(3,1),(3,2),(2,2),(2,1),(1,1),(1,2),(0,2)
и отрезок: (0,1),(5,1)
Его середина: (2.5,1) принадлежит полигону, но сам отрезок нет.
поэтому я прошу объяснить, что значит: при условии, что этот длина этого отрезка минимальна при одном конце фиксированном, а втором - нет.
мне нужно именно как проверить, если у меня есть координаты вершин полигона и координаты концов отрезка.
я не знаю, как сделать это.
-
-
10.10.2010 в 22:14в случае если из точки (0,1), то минимальным по длине будет отрезок - ((0,1), (1,1))
-
-
10.10.2010 в 22:21Например я взял первой вершину: (0,3)
из нее попадаю в точку пересечения (0,2)
тогда следующая по порядку обхода точка пересечения - это (5,2)
тогда я проверяю лежит ли отрезок (0,2), (5,2) полигону целиком.
он не принадлежит, тогда я ищу точку пересечения с другой стороны - это точка (1,2) из нее иду дальше по порядку и отлично замыкаю новый полигон.
Но мне как воздух нужна в таком случае именно такая проверка.
вот я и хотел попросить помочь кого поделиться соображениями, как сделать именно такую проверку...
-
-
10.10.2010 в 22:23пример мой - говно.
я имел в виду полигон:
(0,0),(5,0),(5,3),(4,3),(4,1),(3,1),(3,3),(2,3),(2,1),(1,1),(1,3),(0,3)
и соответсвенно отрезок (0,2), (5,2)
уж простите...
я предыдущую запись сейчас отредактирую по новым данным...
-
-
10.10.2010 в 22:59порисуйте же.
там 6 точек пересечения: (0,2), (1,2), (2,2),(3,2),(4,2),(5,2)
вы дошли до точки (0,2) с ней 5 возможных отрезков. минимальная длина у ((0,2),(1,2)) его и надо брать. и точка следующая - это (1,2), а никак не (5,2)
-
-
11.10.2010 в 16:52Бжжж...
Я знаю, что нужна мне точка (1,2), а не (5,2)
Но у меня обход полигона против часовой стрелки, поэтому в массиве точек [вместе с точками пересечения!] (отсортированному в обходе против часовой)
(0,0),(5,0),(5,2),(5,3),(4,3),(4,2),(4,1),(3,1),(3,2),(3,3),(2,3),(2,2),(2,1),(1,1),(1,2),(1,3),(0,3),(0,2)
а поскольку у меня полигон в виде "кольца", то эти точки кхм... замкнутые в общем. Дощли до (0,3) и следующая будет (0,0).
Поэтому после точки пересечения (0,2) следующей точкой пересечения будет именно (5,2).
В общем дело не в этом.
Не буду грузить сильно своей ерундой - все-таки самому ее потом воплощать.
Одно только хочу спросить.
Вот такая вот проверка, принадлежит ли отрезок полигону (причем концы отрезка всегда лежат на сторонах или вершинах полигона):
1) если отрезок пересекает где-то сторону полигона, то не принадлежит.
2) если не пересекает смотрим принадлежит ли середина отрезка полигону
а) принадлежит - отрезок принадлежит
б) не принадлежит - отрезок не принадлежит.
Вот мне кажется, что это всегда выполняется.
Каковоо ваше мнение?
-
-
11.10.2010 в 17:08если пойдешь в точку (5,2) - по-любому полигон сразу же не правильный получается. то есть не разбивка. потому что он разобьется так максимум на 3 полигона, а надо бы на 4.
про проверку правда, но думаю это не поможет. сделаешь неправильно работающую программу и все.
-
-
11.10.2010 в 17:39ну почему же не поможет..
.Сам алгоритм такой:
1) Составляе полигон в виде кольца. Замкнутого списка то есть.
Пока не знаю точно, как я это буду делать, но пока считаю, что он у меня есть.
2) Находим точки пересечения прямой со сторонами полигона.
Втыкаем их в кольцо в нужное место (если точка пересечения лежит на стороне)
или же меняем значение датчика b соответствующей точки с нуля на единицу (если точка пересечения совпадает с вершиной)
3) Берем первую непройденную вершину и передаем ее в новое кольцо, попутно меняем значение датчика с 0 на 2. Идем дальше до того момента, пока не наткнемся на точку пересечения. Если мы дошли до точки пересечения, то ищем первую следующую точку пересечения. Затем надо проверить, лежит ли этот отрезок внутри полигона или нет
Если этот отрезок лежит внутри полигона - тогда идем дальше, как и шли до этого.
Если он не лежит внутри полигона целиком, тогда ищем первую точку пересечения, но в обратную сторону. И дальше продолжаем идти в первоначальную сторону обхода.
Когда приходим в начальную вершину, то замыкаем новое кольцо и наш полигон готов.
4) Дальше берем следующую вершину и проделываем то же самое.
5) Выходим из всего этого тогда, когда количество непройденных вершин в исходном кольце равно нулю.
Вот он же алгоритм.
Берем этот же пример, что был:
полигон:
(0,0),(5,0),(5,3),(4,3),(4,1),(3,1),(3,3),(2,3),(2,1),(1,1),(1,3),(0,3)
и соответсвенно отрезок (0,2), (5,2)
Нахожу точки пересечения и втыкаю их между точек в порядке прохождения, получаю:
(0,0)(0,0),(5,0),(5,2),(5,3),(4,3),(4,2),(4,1),(3,1),(3,2),(3,3),(2,3),(2,2),(2,1),(1,1),(1,2),(1,3),(0,3),(0,2)
Беру первую непройденную вершину и иду до точки пересечения:
(0,0),(5,0),(5,2)
иду дальше и ищу следующую точку пересечения: (4,2)
проверяю - она пересекает полигон только в двух точках и середина принадлежит полигону - значит эта точка нам и нужна. иду дальше:
(4,1),(3,1),(3,2)
аналогично получаю (2,2)
Далее (2,1),(1,1),(1,2)
аналогично иду в (0,2)
из (0,2) следующая идет (0,0), но это первая нами взятая точка => один полигон мы составили.
После первого обхода мы получаем такой список из непройденных вершин и точек пересечения (на самом деле пройденные вершины тоже остаются, но мы их не учитываем, потому что после прохождения у них меняется значение датчика с 0 на 2):
(5,2),(5,3),(4,3),(4,2),(3,2),(3,3),(2,3),(2,2),(1,2),(1,3),(0,3),(0,2)
Берем первую непройденную вершину:
(5,3) идем из нее в (4,3) и далее в (4,2)
следующая по порядку точка пересечения - (3,2)
проверяю - отрезок (4,2),(3,2) пересекает отрезок только в двух точках, но середина этого отрезка не принадлежит полигону.
значит мы ищем первую точку пересечения, но в другую сторону, то есть по часовой
это точка (5,2)
далее идем снова против часовой и попадаем в точку (5,3). это была первая точка обхода, поэтому и этот полигон сделан.
Остальные два аналогично получаются.
Если же брать за первую вершину (например) (0,3), то ничего не поменяется, потому что идёт: (0,3), (0,2), (1,2) [(5,2) не подходит, так как пересекает полигон более чем в одной точке] (1,3) и полигон замыкается.
Вот как-то так.
Если есть недочет, прошу ткнуть меня в него носом...
Единственное над чем я сейчас задумался - это что будет, если у отрезка и полигона бесконечно число точек пересечения...
тогда работать вроде не будет...
я задумался...
-
-
11.10.2010 в 18:03-
-
11.10.2010 в 18:15если оба конца отрезка принадлежат прямой, то весь отрезок принадлежит прямой и переписываем оба конца отрезка в точки пересечения.
если прямая пересекает наш отрезок в какой-то точке, совпадающей с вершиной, то переписываем эту вершину в точку пересечения.
если прямая пересекает наш отрезок в какой-то точке, не совпадающей ни с одной из двух вершин, то добавляем эту точку.
кажется ничего не упустил?
А по алгоритму замечания есть?
Есть ли пример того, когда он не будет работать?
PS: Вот подумал я...
Ну ни фига себе нам задачку на проге задали =(
апсет(
-
-
11.10.2010 в 22:37зы. задача на самом деле не сложная. просто надо сесть и разобраться, что делать.
но правда у меня в 9ом классе на первом городском туре по проге(он не очень сложный был и с него прошло более 100 людей, думаю окло 200), была одна из задач очень похожа на эту. но она из самых простых.
обычная задача на аккуратное составление условий.
-
-
11.10.2010 в 22:53и знание геометрии хоть какое-то, которое у меня в одном месте...
я не говорю, что она сложная, я говорю, что она громоздкая...
-
-
11.10.2010 в 23:00-
-
11.10.2010 в 23:03поэтому и хочу довести ее до конца.
нам сказали, что тем, кто не сделает, баллов меньше не поставят.
Но тут уже дело принципа...
К тому же я все задания по проге, что задали до ноября, уже сдал, и будет обидно как-то не сделать еще и это...
Просто всерьез проскакивали мысли заниматься прогой...
И не могу же я запороть такую задачу и не сделать ее?
Значит должен.
-
-
11.10.2010 в 23:10-
-
12.10.2010 в 08:47прога не моя специальность вообще-то...
я учусь тип на механика.
greetty , вот только хотел спросить, а ты сама как с программированием - работаешь уже, или еще нет?
-
-
12.10.2010 в 09:42-
-
12.10.2010 в 17:53А что дало знание моего вуза и курса?))