Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] Динамические массивы

Автор: KasMP 7.5.2008, 18:26

Цитата Разработать модуль «Многоугольник» на основе динамического массива вершин. Реализовать  вычисление периметра;  вычисление площади;  проверку на выпуклость;  овыпукление многоугольника (т. е. построение наименьшего по площади выпуклого многоугольника, содержащего заданный);  пересечение двух выпуклых многоугольников, проверку принадлежности точки многоугольнику (возможно, невыпуклому). Input/Output в/из файл(а). С первым пунктом (вычисление периметра) все очевидно: идем по списку (состоящему из записей с тремя полями: x, y, next), накапливаем значение периметра (используя формулу расстояния между двумя точками с известными координатами: d^2=(x1-x2)^2+(y1-y2)^2); упростить процесс у меня не получилось (там же сумма корней получается, ничего с ней не сделаешь…). По части второго пункта (вычисление площади) есть тупая мысль просто взять лежащую внутри многоугольника точку, соединить ее со всеми вершинами, накапливать значение площади (складывая площади получившихся треугольников). Мне эта тупая мысль не нравится, но придумать что-то более элегантное пока не удалось. Третий пункт, проверка на выпуклось. Можно, конечно, исходить из геометрического определения выпуклости и проверять, лежит ли многоугольник по одну сторону от каждой из линий, соединяющих соседние вершины. Но интуиция мне подсказывает, что это слишком долго, нерационально и имеет мало общего с программированием  . Четвертый и пятый пункт меня пугают   . Помогите, пожалуйста  . Не бросайте студентку на произвол судьбы  !!

Автор: Akina 10.5.2008, 22:08

1) да. 2) не сработает, ибо ошибочно. Использовать разбиение на треугольники. 3) проверка внешних углов при каждой вершине. 4) ликвидация "впуклых" вершин по одной. 5) непонятно, о чем речь

Автор: maxim1000 10.5.2008, 22:32

вычислять площадь можно по такой формуле (то ли это формула Грина, то ли из неё выводится): s=sum[i=1..N]( (x[i+1]-x[i])*(y[i+1]+y[i])/2 ) (ну ещё модуль взять)

Автор: KasMP 11.5.2008, 00:01

Цитата(Akina @  10.5.2008,  22:08 ) 3) проверка внешних углов при каждой вершине. Скажем, есть у нас три пары координат: вершины А1, А2, А3.     А3     / А2     \      А1 Как посчитать угол - понятно (через скалярное произведение векторов). А вот как определить, будет посчитанный угол внешним или внутренним? Ведь возможны обе ситуации: Цитата(Akina @  10.5.2008,  22:08 ) 4) ликвидация "впуклых" вершин по одной. Для этого надо уметь определять "впуклые" вершины  (а мы пока этому комп не научили). Цитата(Akina @  10.5.2008,  22:08 ) 5) непонятно, о чем речь  Пока можно подумать о "проверке принадлежности точки многоугольнику (возможно, невыпуклому)". А про пересечение я уточню  . Цитата(maxim1000 @  10.5.2008,  22:32 ) вычислять площадь можно по такой формуле (то ли это формула Грина, то ли из неё выводится): s=sum[i=1..N]( (x[i+1]-x[i])*(y[i+1]+y[i])/2 ) (ну ещё модуль взять) Если я правильно поняла, то вершина 1 и вершина (i+1) совпадают. Т.е. если смотреть со стороны периметра и площади, то нам больше всего подходит циклический способ организации динамического массива (проще говоря, мы должны указатель последней записи направить на первую). Да  ?! (большое спасибо за хорошую, очень удобную формулу  !)

Автор: maxim1000 11.5.2008, 15:41

Цитата(KasMP @  11.5.2008,  00:01 ) Т.е. если смотреть со стороны периметра и площади, то нам больше всего подходит циклический способ организации динамического массива (проще говоря, мы должны указатель последней записи направить на первую). да, просто забыл уточнить по смыслу там просто идёт суммирование по отрезкам, ну а т.к. последний отрезок соединяет последнюю и первую вершины, то и получается циклический доступ Цитата(KasMP @  11.5.2008,  00:01 ) А вот как определить, будет посчитанный угол внешним или внутренним? Ведь возможны обе ситуации рассматривая отдельно взятый угол, определить внешний он или внутренний не получится нужно выбрать направление обхода вершин (вполне естественно взять то, в котором задан многоугольник) и для каждого угла выяснить, вправо он поворачивает или влево если везду происходит поворот в одну и ту же сторону - многоугольник выпуклый, иначе - нет Добавлено через 1 минуту и 53 секунды ну а вообще, в будущем я бы советовал создавать по одной теме на каждый вопрос, тогда и заголовок можно точнее написать, что увеичит вероятность захода в тему человека, которому это интересно ну а кроме того, по этим вопросам можно поискать, что уже есть на форуме если мне не изменяет память, то определение площади и выпуклости уже где-то проскакивало

Автор: KasMP 11.5.2008, 19:07

Цитата(maxim1000 @  11.5.2008,  15:41 ) нужно выбрать направление обхода вершин (вполне естественно взять то, в котором задан многоугольник) и для каждого угла выяснить, вправо он поворачивает или влево Определить это через скалярное произведение не получается: его знак говорит о том, что угол острый/прямой/тупой, а направление никак не задействовано. Если считать угол между векторами, то тоже не получается: arccos(x) - мы можем повернуть на x в любу сторону. Если считать изменение координат (например, абсцисса увеличилась и ордината уменьшилась, абсцисса и ордината увеличились, т.п.), то придется сначала искать крайние точки (нижнюю, левую, верхнюю, правую), потому что при переходе через эти точки изменение координат меняют значение: находимся между крайней левой и крайней верхней точками, увеличение абсциссы и ординаты - поворот вправо; находимся между крайней правой и крайней левой точками, увеличение абсциссы и ординаты - поворот влево. Как это определить?   Цитата(maxim1000 @  11.5.2008,  15:41 ) ну а вообще, в будущем я бы советовал создавать по одной теме на каждый вопрос, тогда и заголовок можно точнее написать, что увеичит вероятность захода в тему человека, которому это интересно Учту на будущее  . Цитата(maxim1000 @  11.5.2008,  15:41 ) ну а кроме того, по этим вопросам можно поискать, что уже есть на форуме если мне не изменяет память, то определение площади и выпуклости уже где-то проскакивало  Уже пробовала  . Попробую еще  .

Автор: maxim1000 11.5.2008, 21:57

Цитата(KasMP @  11.5.2008,  19:07 ) Определить это через скалярное произведение не получается: его знак говорит о том, что угол острый/прямой/тупой, а направление никак не задействовано. для этого можно использовать векторное произведение точнее - определитель, т.к. векторное произведение определяется в 3d ax*by-ay*bx будет иметь разный знак в зависимости от того, в какую сторону направлен угол между a и b

Автор: KasMP 11.5.2008, 22:04

Цитата(maxim1000 @  11.5.2008,  21:57 ) для этого можно использовать векторное произведение точнее - определитель, т.к. векторное произведение определяется в 3d ax*by-ay*bx будет иметь разный знак в зависимости от того, в какую сторону направлен угол между a и b  Точно! Да и я сама вспомнила про векторное произведение, хотела открыть тетрадку и проверить, а вместо этого пошла на кухню делать ужин и так и забыла  . Спасибо еще раз  .

Автор: KasMP 13.5.2008, 11:16

Цитата(Akina @  10.5.2008,  22:08 ) 5) непонятно, о чем речь Итак, мы уточнили  . Пересечение двух выпуклых многоугольников. Пересечение - часть, принадлежащая обоим многоугольникам, вершины которых задаются с помощью двух координат. Например, 1) ((-5,-1),(2,7),(2,-1))*((-1,-1),(-1,2),(2,2),(4,0),(2,-3)) = ((-1,-1),(-1,2),(2,2),(2,-1))- многоугольник; 2) ((0,0),(0,1),(1,1),(1,0))*(0,0) = (0,0)- точка; 3) ((0,0),(0,1),(1,1),(1,0))*(5,5) = пустое множество; 4) ((0,0),(0,1),(1,1),(1,0))*((0,0),(0,5),(5,5),(5,0)) = ((0,0),(0,1),(1,1),(1,0))- первый многоугольник. Проверка принадлежности точки многоугольнику (возможно, невыпуклому). Тут все понятно  . (в смысле, задание понятно... а как делать - нефига непонятно!!!)

Автор: KasMP 18.5.2008, 16:18

Люди, ну помогите, пожалуйста, с принадлежностью точки многоугольнику! Если с определением выпуклости я как-то справлюсь (примерно понятно, что и как делать), то с принадлежностью вообще все очень туго!!!

Автор: Fortop 18.5.2008, 16:34

Подожди, почему туго. Принадлежность точки треугольнику ты можешь определить? Добавлено через 1 минуту и 52 секунды Да, вот тебе статья навскидку http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%B2_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B5 Добавлено через 2 минуты и 52 секунды Вот тебе вторая статья http://algolist.manual.ru/maths/geom/belong/poly2d.php

Автор: KasMP 18.5.2008, 16:37

Цитата(Fortop @  18.5.2008,  16:34 ) Принадлежность точки треугольнику ты можешь определить? Не знаю, сейчас подумаю... Добавлено через 47 секунд Цитата(Fortop @  18.5.2008,  16:34 ) Да, вот тебе статья навскидку http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B8%D0%BA%D0%B5  О! Там, похоже, что-то стоящее  . Посмотрю попозже, спасибо за хорошую ссылку  . Добавлено через 2 минуты и 43 секунды Кстати, с пересечением тоже дела не очень...  Пожалуйста, не бросайте на растерзание судьбы  беззащитную студентку  .

Автор: KasMP 18.5.2008, 16:55

Цитата(Wikipedia) Для проверки принадлежности точки треугольнику (а также выпуклому многоугольнику с любым числом вершин) можно применить и другой алгоритм. Заданная точка соединяется отрезками с вершинами треугольника. Если площадь исходного треугольника равна сумме площадей образовавшихся трёх треугольников, то считается, что точка принадлежит треугольнику. Гм, и неужели нельзя изобрести такой треугольник и такую непринадлежащую ему точку, что указанная сумма площадей будет равно площади треугольника? Имхо если постараться, то может получиться  ! (а с многоугольником точно должно получиться изобрести!)

Автор: Fortop 18.5.2008, 16:58

KasMP,  С пересечением тоже можно поискать ссылки  Не думая, алгоритмически я бы сделал так. Взял бы каждую сторону многоугольников и проверил бы на пересечение с каждой стороной другого. Если есть, то найти точки пересечения и определив направление обхода, бежал бы последовательно по узлам. Например. Если первое пересечение находится на стороне А1А2 и Б2Б3, а следующее А5А6 Б4Б5,то необходимо пробежаться по все фигуре от точки пересечения  А1А2-Б2Б3 через А2А3, А4А5 до точки пересечения А5А6-Б4Б5 и назад через Б3Б4 до точки пересечения  А1А2-Б2Б3. Хотя надо еще проверять выпуклость и впуклость. Плюс здесь же будет проверка вырожденого случая. Если один многоугольник целиком внутри другого. А вообще  пару запросов в Гугль, и думаю, там будут более оптимальные варианты, чем предложенный мной  Добавлено @ 17:00 Цитата(KasMP @  18.5.2008,  16:55 ) Гм, и неужели нельзя изобрести такой треугольник и такую непринадлежащую ему точку, что указанная сумма площадей будет равно площади треугольника? Имхо если постараться, то может получиться  ! (а с многоугольником точно должно получиться изобрести!) нет. Смотри, так как ты соединяешся с каждой вершиной. То площадь многоугольника ты захватишь в любом случае. Но если точка лежит вне, то ты захватишь еще и лишнего  Добавлено через 4 минуты и 4 секунды KasMP, если что-то не можешь понять - нарисуй на бумаге  Так бывает гораздо проще. А треугольник или многоугольник - разницы большой в этом случае нет.

Автор: KasMP 18.5.2008, 17:07

Цитата(Fortop @  18.5.2008,  16:58 ) А вообще smile пару запросов в Гугль, и думаю, там будут более оптимальные варианты, чем предложенный мной smile Да, но ведь нормальный программист должен хотя бы раз додуматься до всего этого сам. (или хотя бы поразмышлять на эту тему, чтобы понять все нюансы и всю красоту оптимального варианта, понять свои ошибки и сделать вывод на будущее) Цитата(Fortop @  18.5.2008,  16:58 ) нет. Смотри. так как ты соединяещся с каждой вершиной. То площадь многоугольника ты захватишь в любом случае. Но если точка лежит вне, то ты захватишь еще и лишнего smile  И действительно     . (я уже нарисовала   )

Автор: Fortop 18.5.2008, 23:33

Цитата(KasMP @  18.5.2008,  17:07 ) Да, но ведь нормальный программист должен хотя бы раз додуматься до всего этого сам. (или хотя бы поразмышлять на эту тему, чтобы понять все нюансы и всю красоту оптимального варианта, понять свои ошибки и сделать вывод на будущее) Это классно  Но кто из нас двоих собирается быть нормальным программистом?

Автор: KasMP 20.5.2008, 07:58

Я вчера наконец-то отошла от раздумий над алгоритмами и приступила к написанию программы. Решила создать модуль, в котором будут нужные ВА. В модуле были созданы типы для списка и некоторые переменные: Код type    TPointer=^TCoordinate;         TCoordinate=record             x, y: integer;             next: TPointer;             end; var    start, step, finish: TPointer;         num: integer; {число вершин многоугольника} После процедур считывания первой вершины и всех остальных идут периметр и площадь (это мне удалось достаточно быстро и легко). Прошу каких-нибудь рекомендаций, замечаний. Код function Perimeter (var start: TPointer; var num: integer): real;     var    i: integer;         tempSum: real;         tempStep, tempNext: TPointer;         tempX, tempY: integer;     begin     tempSum:=0; tempStep:=start; tempNext:=start^.next;     for i:=1 to num do         begin         tempX:=(tempStep^.x-tempNext^.x)*(tempStep^.x-tempNext^.x);         tempY:=(tempStep^.y-tempNext^.y)*(tempStep^.y-tempNext^.y);         tempSum:=tempSum+SQRT(tempX+tempY);         tempNext:=tempNext^.next; tempStep:=tempStep^.next;         end;     Perimeter:=tempSum;     end; Код function Square (var start: TPointer; var num: integer): real;     var    i: integer;         tempSum: real;         tempStep, tempNext: TPointer;         tempX, tempY: integer;     begin     tempSum:=0; tempStep:=start; tempNext:=start^.next;     for i:=1 to num do         begin         tempX:=tempNext^.x-tempStep^.x;         tempY:=tempNext^.y+tempStep^.y;         tempSum:=tempSum+tempX*tempY;         tempNext:=tempNext^.next; tempStep:=tempStep^.next;         end;     Square:=tempSum*0.5;     end; Дальше идет определение принадлежности точки многоугольнику: точка последовательно соединяется со всеми соседними вершинами, накапливается сумма площадей полученных треугольников (площадь каждого отдельного треугольника считается по формуле Герона); если накопленная сумма площадей равна площади многоугольника, то точка принадлежит многоугольнику (иначе не принадлежит, это понятно). Очевидно, что при подсчете площадей двух соседних треугольников длина одной и той же стороны будет нужна 2 раза. Это учтено: длина каждой стороны считается один раз, а в цикле просто переводятся указатели. Мне удалось найти у себя несколько ошибок: периметр вместо полупериметра, непереведенные на вершину вперед указатели и т.п.. Но функция по прежнему всегда выдает false. Код function PointInPolyhedron (var start: TPointer; var num: integer; var x, y: integer): boolean;     var    i: integer;         tempSum: real; {накопление суммы площадей треугольников}         tempStep, tempNext: TPointer;         difX, difY, difStepX, difStepY, difNextX, difNextY: integer;         len, lenStep, lenNext: real;         tempP: real; {полупериметр каждого получевшегося реугольника}     begin     {для разностей и длин::      Step - точка и текущая вершина;      Next - точка и следующая вершина;      [ничего] - текущая и следующая вершины}     tempSum:=0; tempP:=0; tempStep:=start; tempNext:=start^.next;     difStepX:=(x-tempStep^.x)*(x-tempStep^.x);     difStepY:=(y-tempStep^.y)*(y-tempStep^.y);     lenStep:=SQRT(difStepX+difStepY);     for i:=1 to num do         begin         {расстояние от текущей вершины до следующей}         difX:=(tempNext^.x-tempStep^.x)*(tempNext^.x-tempStep^.x);         difY:=(tempNext^.y-tempStep^.y)*(tempNext^.y-tempStep^.y);         len:=SQRT(difX+difY);         {расстояние от точки до следующей вершины}         difNextX:=(tempNext^.x-x)*(tempNext^.x-x);         difNextY:=(tempNext^.y-y)*(tempNext^.y-y);         lenNext:=SQRT(difNextX+difNextY);         {полупериметр}         tempP:=(len+lenStep+lenNext)*0.5;         tempSum:=tempSum+SQRT(tempP*(tempP-len)*(tempP-lenStep)*(tempP-lenNext));         {переносим длины текущей стороны          сдвигаем указатели на  одну вершину вперед}         lenStep:=lenNext; tempStep:=tempNext; tempNext:=tempNext^.next;         end;     {сумма площадей равно площади многоугольника?}     PointInPolyhedron:=(Square(start,num)=tempSum);     end; В упор не могу найти еще ошибки (помогите, пожалуйста). Ну и сама программа, в которой все это тестируется, выглядит так: Код uses Module; var    input: text;     i: integer;     x, y: integer; begin {создание списка из вершин­} assign(input, 'C:\in.txt'); reset(input); MReadFirst(input,num,start,step); for i:=1 to (num-1) do MRead(input,step); {закольцовывание списка} finish:=step; finish^.next:=start; writeln(Perimeter(start,num):2:2); writeln(Square(start,num):2:2); readln(x,y); writeln(PointInPolyhedron(start,num,x,y)); readln; end.

Автор: KasMP 20.5.2008, 14:58

Я вместо массива организовала динамический список  !

Автор: skyboy 20.5.2008, 16:43

я так понял, у тебя сравниваются площади "строго равно". все же у тебя дробный тип данных. воспользуйся сравнением "отлиается на некую погрешность". Цитата(KasMP @  20.5.2008,  06:58 )  Но функция по прежнему всегда выдает false. ну, так отладь функции в отдельности. корми тестовые данные, смотри дебаггером текущие значения переменных. сравнивай с ожидаемым. когда функции в отдельности будут отлажены и проверены по мере сил, приходи к тестированию программы в целом. а то даже с помощью целого форума искать ошибку в непростом коде - вещь небыстрая, малоинтересная и низкоинформативная

Автор: KasMP 20.5.2008, 19:19

skyboy,  ! (очень рада тебя видеть!!!) Цитата(skyboy @  20.5.2008,  16:43 ) я так понял, у тебя сравниваются площади "строго равно". все же у тебя дробный тип данных.    Цитата(skyboy @  20.5.2008,  16:43 ) воспользуйся сравнением "отлиается на некую погрешность"      Т.е., другими словами, взять модуль разности суммы площадей треугольников и площади многоугольника, а затем сравнить этот модуль с какой-то положительной величиной? Цитата(skyboy @  20.5.2008,  16:43 ) ну, так отладь функции в отдельности. корми тестовые данные, смотри дебаггером текущие значения переменных. сравнивай с ожидаемым. когда функции в отдельности будут отлажены и проверены по мере сил, приходи к тестированию программы в целом. Я так и делаю  . Видимо, сказывается недостаток опыта  .

Автор: Fortop 21.5.2008, 01:25

Цитата(KasMP @  20.5.2008,  19:19 ) Т.е., другими словами, взять модуль разности суммы площадей треугольников и площади многоугольника, а затем сравнить этот модуль с какой-то положительной величиной? Если в Delphi нет специальной функции, то алгоритм описан правильно  главное чтобы эта положительная величина была достаточно мала

Автор: KasMP 21.5.2008, 10:16

Цитата(Fortop @  21.5.2008,  01:25 ) главное чтобы эта положительная величина была достаточно мала Подумаем, сколько это должно быть... Только проблема в том, что функция проверки принадлежности точки многоугольнику выдает false даже тогда, когда результаты всех вычислений, всех извлечений корней целочисленны  . Буду дальше искать и сравнивать...

Автор: Fortop 21.5.2008, 22:33

KasMP,  А что тут искать? бери треугольник со сторонами 3, 4, 5 переведи на листике его в векторы и точку где-нибудь внутри. затем заданные значения просчитай своей функцией и выведи результат суммы площадей.

Автор: KasMP 21.5.2008, 22:40

О  ! Сегодня запустила тот же самый код на другом компе - функция работала идеально  . Сейчас запустила у себя - тоже идеально  . Как такое может быть    ? (может память надо чаще очищать    ?)

Автор: KasMP 22.5.2008, 09:02

Сделала все кроме пересечения двух многоугольников (вторым "многоугольником" может быть точка). Про пересечение буду читать вот http://www.inf.tsu.ru/library/Publications/2004/46.pdf. Сдавать в классе мы уж не успеваем, поэтому буду писать на e-mail. Я попробовала прокомментировать модуль и саму программу так, чтобы преподаватель понял, откуда что взялось. Не могли бы вы оценить то, насколько понятно получилось? Помогите, пожалуйста, своей оценкой. Я нисколько не хочу, чтобы преподаватель увяз в дебрях переменных, связей между ними и т.п.. Хочется, чтобы ему было не очень сложно и чтобы он не мучился слишком сильно... (видимо, придется посылать два варианта: с комментариями и без - уж слишком много их получилось)

Автор: THandle 22.5.2008, 09:20

KasMP, покажи что у тебя получилось, почитаю

Автор: KasMP 22.5.2008, 09:24

Сейчас  . Добавлено через 2 минуты и 44 секунды Эм... Если открыть *.pas в блокноте, выбрать шрифт "Terminal", скопировать и вставить сюда, то вместо кириллицы получается абракадабра. Если выбирать не "Terminal", то получается абракадабра и в блокноте, и здесь...  Добавлено через 3 минуты и 58 секунд Как перенести кириллицу из *.pas (т.е. из-под MSDOS) сюда (т.е. в Windows)?

Автор: THandle 22.5.2008, 09:39

KasMP, прикрепи сам файл

Автор: KasMP 22.5.2008, 09:46

Так не все будут качать... Кто-то по ссылке до статьи дойти не может, а тут тем более...

Автор: KasMP 22.5.2008, 09:47

Там 5 файлов: модуль с комментариями и без, программа с комментариями и без, формула для площади многоугольника. Добавлено через 7 минут и 44 секунды Я вспомнила, что забыла очистить память!!!!!! Добавлю потом... Считайте, что память очищена  . Добавлено через 10 минут и 54 секунды Да, кстати, вам потребуется файл входных данных. Можете взять этот: Цитата 4 -6 0 -6 2 -4 3 -4 -2 3 0 0 0 -3 -2 0 5 2 1 2 5 4 5 4 1 3 3 6 2 -3 5 -3 5 -4 7 -4 5 -5 3 -5

Автор: KasMP 22.5.2008, 10:03

Если кому-то интересно, то с этими входными данными Цитата 4 -6 0 -6 2 -4 3 -4 -2 3 0 0 0 -3 -2 0 5 2 1 2 5 4 5 4 1 3 3 6 2 -3 5 -3 5 -4 7 -4 5 -5 3 -5 получаются http://img221.imageshack.us/img221/7223/spa0155ne2.jpg многоугольники (~120Кб).

Автор: THandle 22.5.2008, 10:56

KasMP, ну в общем все чем мог помочь написал в ПМ, для форума это особой ценности не представляет

Автор: KasMP 22.5.2008, 11:16

Цитата(THandle @  22.5.2008,  10:56 ) KasMP, ну в общем все чем мог помочь написал в ПМ

Автор: KasMP 22.5.2008, 11:42

Так, пересечение  ... Цитата(Скворцов @  Обзор алгоритмов построения оверлеев многоугольников) Посидев над этой табличкой, я выбрала алгоритм О'Рурка для выпуклых многоугольников (а случай с многоугольником и точкой рассмотрю отдельно, на это много ума не надо...). Цитата(Скворцов @  Обзор алгоритмов построения оверлеев многоугольников) Честно говоря , я очень плохо представляю, как можно это реализовать ...

Автор: KasMP 23.5.2008, 18:09

Люди, ну помогите пожалуйста разобраться с алгоритмом О'Рурка! (моя тема чем-то хуже остальных?)

Автор: Fortop 23.5.2008, 20:15

KasMP, судя по всему он очень похож на то, что я тебе предлагал в самом начале. Перебирать все ребра и проверять пересекаются ли они между собой. или посмотри эту ссылку http://progs-maker.narod.ru/algor.html

Автор: volvo877 23.5.2008, 20:29

Цитата(KasMP @  23.5.2008,  18:09 ) ну помогите пожалуйста разобраться с алгоритмом О'Рурка! Наверное, лучше всего обратиться к первоисточнику - книге О'Рурка "Вычислительная геометрия на С". Вот тут лежат исходники из этой книги: http://maven.smith.edu/~orourke/books/ftp.html (тебе нужен Int Conv Poly)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)