Полигон. Максимальный поперечник.

ArcGIS 8.x,9.x,10.x (Arcview, ArcEditor, Arcinfo).
Ответить
Maka
Активный участник
Сообщения: 121
Зарегистрирован: 23 ноя 2005, 16:57
Репутация: 6
Откуда: Москва

Полигон. Максимальный поперечник.

Сообщение Maka » 24 фев 2009, 15:43

Здравствуйте!

необходимо найти максимальный поперечник для полигона

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

Проблема в громоздкости вычислений (полигонов около 19 000, а точек получается около 2 500 000).

Возможно кто-то делал что-то подобное.

Вот здесь обсуждается нахождение расстояния между точками
viewtopic.php?f=16&t=1349

только я не понимаю что такое БГД (база геоданных?) :oops:

Заранее спасибо Маша.

geologic
Гуру
Сообщения: 852
Зарегистрирован: 15 сен 2005, 13:19
Репутация: 6
Откуда: москва
Контактная информация:

Re: Полигон. Максимальный поперечник.

Сообщение geologic » 24 фев 2009, 16:20

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

Длину как максимальное удаление точек в облаках найти можно, несложно это реализовать даже средствами SQL - не в БГД, а в любой БД. Понятие "ширина" недостаточно формализовано, как вы увидите по ссылке - определения "максимальный поперечник" явно недостаточно.

Maka
Активный участник
Сообщения: 121
Зарегистрирован: 23 ноя 2005, 16:57
Репутация: 6
Откуда: Москва

Re: Полигон. Максимальный поперечник.

Сообщение Maka » 24 фев 2009, 16:52

Спасибо!
по ссылке все довольно сложно :)

моя задача проще. Мне нужна действительно максимальная длинна (максимальное рассотяние между двумя вертексами в полигоне). Ширина не интересует.
В SQL не сильна, решаю все в Excel.

А интересуют два момента:
1. насколько я поняла, прочитав, то что было в первой ссылке, там сразу в ArcGis получались расстояния. Это было бы хорошо, так как уменьшило бы вычисления в Excel.

2. Вероятно глупо вычислять для полигона расстояния между всеми точками. Так можно отбросить соседние точки. Может быть можно сократить количество точек, для которых надо вычислять расстояния?
Например, на ум приходят Хмах и Хmin , аналогично для У. Хотя например для элипса расположенного под углом к осям координат мы получим по этим расстояниям заниженные значения :(

Маша.

KolesovDmitry
Гуру
Сообщения: 810
Зарегистрирован: 22 авг 2007, 14:58
Репутация: 123
Откуда: Казань

Re: Полигон. Максимальный поперечник.

Сообщение KolesovDmitry » 24 фев 2009, 18:47

Maka писал(а): моя задача проще. Мне нужна действительно максимальная длинна (максимальное рассотяние между двумя вертексами в полигоне). Ширина не интересует.
Это задача - задача о поиске диаметра выпуклого множества. Прикрепляю несколько страниц из книги Препарата Ф., Шеймос М., "​Вычислительная геометрия", где описывается метод решения.
Вложения
vgeom.zip
Несколько страниц из "Вычислительной геометрии"
(392.55 КБ) 599 скачиваний

AndreyL
Завсегдатай
Сообщения: 483
Зарегистрирован: 17 авг 2006, 14:04
Репутация: 0
Откуда: Новосибирск

Re: Полигон. Максимальный поперечник.

Сообщение AndreyL » 24 фев 2009, 19:57

Не совсем понял, в чем проблема. Разбить полигоны на вертексы, рассчитать расстояния между всеми точками - это делается стандартными средствами АркГИС. Правда, получите огромную таблицу - ну и что? Можно, для пущей страсти, сначала вокруг каждого полигона сделать конвексный полигон - уберутся вертексы входящих углов. Теперь осталось сгруппировать расстояния по идентификатору полигона и выбрать максимальное значение - по-моему, тоже можно стандартными средствами АркГИС. И не нужен никакой Ексель, разве что запрос на таблицу сделать, так проще в Аксессе (в Екселе придется через Квери делать)
KolesovDmitry писал(а):Это задача - задача о поиске диаметра выпуклого множества. Прикрепляю несколько страниц из книги Препарата Ф., Шеймос М., "​Вычислительная геометрия", где описывается метод решения.
Алгоритм, кончено, хороший с точки зрения оптимальности количества операций, но, как я понимаю, о программировании тут и речи нет.

geologic
Гуру
Сообщения: 852
Зарегистрирован: 15 сен 2005, 13:19
Репутация: 6
Откуда: москва
Контактная информация:

Re: Полигон. Максимальный поперечник.

Сообщение geologic » 25 фев 2009, 11:16

Вертексы входящих убирать, наверное, ни к чему - на максимальный диаметр они не влияют ;)
По сути, это предварительное упрощение всех полигонов.

Maka
Активный участник
Сообщения: 121
Зарегистрирован: 23 ноя 2005, 16:57
Репутация: 6
Откуда: Москва

Re: Полигон. Максимальный поперечник.

Сообщение Maka » 25 фев 2009, 11:42

KolesovDmitry спасибо посмотрю
AndreyL писал(а):Не совсем понял, в чем проблема. Разбить полигоны на вертексы, рассчитать расстояния между всеми точками - это делается стандартными средствами АркГИС.
Разбить полигон на вертексы - действительно без проблем.
А вот расчитать расстояния между всеми точками одного полигона (полигонов много) средствами АркГис - пока проблема. Можете расписать по подробнее как?

Маша.

AndreyL
Завсегдатай
Сообщения: 483
Зарегистрирован: 17 авг 2006, 14:04
Репутация: 0
Откуда: Новосибирск

Re: Полигон. Максимальный поперечник.

Сообщение AndreyL » 25 фев 2009, 17:40

geologic писал(а):Вертексы входящих убирать, наверное, ни к чему - на максимальный диаметр они не влияют ;)
По сути, это предварительное упрощение всех полигонов.


Полностью с Вами согласен, просто автор боится, что вертексов получается 2 500 000, значит результирующая таблица расстояний будет 6 250 000 000 000 записей. Вот и предложил для начала полигоны упростить. Мне то бы без разницы - не на счетах считать. На самом деле эффект сомнительный, а вот пара лишних действий может замедлить процесс значительно сильнее, чем перебор всех точек. Но это от конкретного случая зависит.
Maka писал(а):А вот расчитать расстояния между всеми точками одного полигона (полигонов много) средствами АркГис - пока проблема.
Я опять ничего не понимаю. Почему нужно считать расстояния между точками только одного полигона, тем более, что полигонов много? Вам нужна длина конкретного одного полигона? Или всех (т.е. каждого) полигонов слоя? И то, и другое не проблема, просто чуть по разному решаются. Поставьте задачу четче - чего имеете на входе, чего хотелось бы на выходе

Maka
Активный участник
Сообщения: 121
Зарегистрирован: 23 ноя 2005, 16:57
Репутация: 6
Откуда: Москва

Re: Полигон. Максимальный поперечник.

Сообщение Maka » 25 фев 2009, 18:15

AndreyL писал(а): просто автор боится, что вертексов получается 2 500 000, значит результирующая таблица расстояний будет 6 250 000 000 000 записей.
Да
AndreyL писал(а):Поставьте задачу четче - чего имеете на входе, чего хотелось бы на выходе
Стараюсь :oops:
Есть 19000 полигонов. Для каждого нужно вычислисть длину.
Маша.

AndreyL
Завсегдатай
Сообщения: 483
Зарегистрирован: 17 авг 2006, 14:04
Репутация: 0
Откуда: Новосибирск

Re: Полигон. Максимальный поперечник.

Сообщение AndreyL » 25 фев 2009, 19:20

Так, если Вы не в дружбе с базами данных, то можно все не выходя из АркГИС. Разбить полигоны на вертексы понятно Data Management Tools - Features - Feature Vertices To Points. В результирующем слое точек будет поле ORIG_FID - это идентификатор полигона. Получить расстояния от каждой точки до каждой Analysis Tools - Proximity - Point Distance. На входе два точечных слоя, в качестве входящего и ближайшего назначаем один и тот же слой вертексов. В (ОГРОМНОЙ) результирующей таблице два поля INPUT_FID и NEAR_FID, но это уже идентификаторы точек из таблицы вертексов. Вот теперь самое интересное - объединить таблицу с другой таблицей дважды нельзя - в АркГИС реляционная теория урезана до неузнаваемости (практически до бесплодия). Тогда создаем копию слоя вертексов, и объединяем (Join) таблицу расстояний с таблицей вертексов по полю INPUT_FID, а копию вертексов по полю NEAR_FID. В определяющем запросе (Definition Query) таблицы расстояний пишем, что ORIG_FID таблицы вертексов равен ORIG_FID ее копии. В результате у нас есть только расстояния внутри полигонов. Отсталость открыть таблицу расстояний (там теперь много новых полей появилось), выделить столбец ORIG_FID, кликнуть на нем правой мышой и выбрать Summarize, после чего сказать, что на выходе нас интересует только максимум по полю DISTANCE. Ну а далее объединяем суммарную таблицу с исходным слоем полигонов.

Если же не хочется сохранять таблицу огромного размера, то можно в Аксессе (или в любой СУБД), но с реляционными базами придется подружиться. Записываем в таблицу слоя вертексов координаты Data Management Tools - Features - Add XY Coordinates. Кидаем на эту таблицу два одинаковых запроса, для простоты Vert1 и Vert2 (чтобы не запутаться, хотя можно и без них). А далее вот такой запрос:

Код: Выделить всё

SELECT Vert1.ORIG_FID, Max(([Vert1]![POINT_X]-[Vert2]![POINT_X])^2+([Vert1]![POINT_Y]-[Vert2]![POINT_Y])^2) AS Dist
FROM Vert1 INNER JOIN Vert2 ON Vert1.ORIG_FID = Vert2.ORIG_FID
GROUP BY Vert1.ORIG_FID;
т.е. объединяем Vert1 и Vert2 по полю ORIG_FID, по нему же делаем группировку, считаем квадрат расстояния между точками и берем максимальный. Никаких промежуточных таблиц при этом не сохраняется.

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

Можно конечно и ручками каждый из 19000 полигонов, тогда проще. Делаете слой вертексов только одного полигона, считаете расстояния и берете максимальное. Но это вопрос, чего сложнее - загрузить машину огромной таблицей, прочитать книжку по СУРБД или 19000 раз нажать одну и ту же последовательность клавиш.

Maka
Активный участник
Сообщения: 121
Зарегистрирован: 23 ноя 2005, 16:57
Репутация: 6
Откуда: Москва

Re: Полигон. Максимальный поперечник.

Сообщение Maka » 26 фев 2009, 13:58

Спасибо!
Боюсь расчеты на АркГИС мой компьютер не потянет :(

буду пробовать в Аксесс. Немного с ним знакома (на уровне построить запрос с помощью конструктора)
Маша.

geologic
Гуру
Сообщения: 852
Зарегистрирован: 15 сен 2005, 13:19
Репутация: 6
Откуда: москва
Контактная информация:

Re: Полигон. Максимальный поперечник.

Сообщение geologic » 26 фев 2009, 16:14

Спасибо, AndreyL, почитал с удовольствием. Действительно, многие пространственные задачи на удивление ловко решаются средствами СУБД. В связи с этим СУБД ГИСовцам, разумеется, обязательно нужно осваивать и максимально привлекать к решению, а не наоборот ;)

Однако в предудущей теме на эту тему приводились ссылки на какие-то скрипты... Я поленился пробовать, они что, никак не помогают?

AndreyL
Завсегдатай
Сообщения: 483
Зарегистрирован: 17 авг 2006, 14:04
Репутация: 0
Откуда: Новосибирск

Re: Полигон. Максимальный поперечник.

Сообщение AndreyL » 26 фев 2009, 17:08

geologic писал(а):Действительно, многие пространственные задачи на удивление ловко решаются средствами СУБД. В связи с этим СУБД ГИСовцам, разумеется, обязательно нужно осваивать и максимально привлекать к решению, а не наоборот ;)
На самом деле это форменное издевательство над машиной. Ведь если таблица расстояний от каждой точки до каждой не сохраняется в явном виде на диске, это еще не значит, что она не создается, просто она существует в виртуальном виде, в виде запроса. По честному эту задачу нужно решать через скрипт, вообще без сохранения вертексов полигонов и без создания таблицы расстояний. И вычислений значительно меньше (т.е. время на решение задачи), и памяти столько не надо.

geologic писал(а):Однако в предудущей теме на эту тему приводились ссылки на какие-то скрипты... Я поленился пробовать, они что, никак не помогают?
не совсем понял, о какой теме со ссылками на скрипты идет речь? Если о нашем обсуждении ширины, то там задача неоднозначная и решение находилось оптимизацией некоторой функции, определяющей понятие "ширина". Оптимизация была численная, значит уже скрипт. А тут задача вполне однозначная.

AndreyL
Завсегдатай
Сообщения: 483
Зарегистрирован: 17 авг 2006, 14:04
Репутация: 0
Откуда: Новосибирск

Re: Полигон. Максимальный поперечник.

Сообщение AndreyL » 26 фев 2009, 17:19

geologic писал(а):Действительно, многие пространственные задачи на удивление ловко решаются средствами СУБД. В связи с этим СУБД ГИСовцам, разумеется, обязательно нужно осваивать и максимально привлекать к решению, а не наоборот ;)
Да, кстати, на Вашем же сайте очень неплохая подборка ссылок по РБД
http://www.geofaq.ru/pbylevels.php?level=0&cat=rdb

geologic
Гуру
Сообщения: 852
Зарегистрирован: 15 сен 2005, 13:19
Репутация: 6
Откуда: москва
Контактная информация:

Re: Полигон. Максимальный поперечник.

Сообщение geologic » 26 фев 2009, 17:54

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

К Маше это не относится, похоже ;)

Ответить

Вернуться в «ArcGIS»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя