|
Действия ...
|
10.06.2011, 17:15
|
|||
|---|---|---|---|
|
|||
По заданной точке найти полигон |
|||
|
|
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
09.06.2011, 20:43
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Подскажите, пожалуйста, алгоритм нахождения полигона которому принадлежит заданная точка. Суть такова: Есть полигоны(выпуклые и не выпуклые без самопересечений) Нужно определить вхождение точки в полигон. Пробовал перебирать все полигоны проверяя на вхождение точки(методом луча, подсчёт углов, триангуляция) предварительно выбрав полигоны которые могут попасть под условия отбора(т.е. плюс минус X Y), но быстродействие никакое. Может кто то сталкивался с данной задачей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 11:06
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
timtim, Цифры, статистика, подробности? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 15:55
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Бенедикт, Таблица ~3 млн строк(id,lat, lon), от 8 секунд, экспериментирую пока. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 15:59
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
полигоны имеют от 400 до 23000 точек ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 16:37
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
timtim, О как. Т. е. единицы тысяч полигонов. Могут пересекаться? Ортодромия в данной проекции (ребро многоугольника) и на данных растояниях, надеюсь, считается отрезком прямой? Сколько можно отдать памяти (оперативки и дисковой) под постороение вспомогательных индексов? Сколько сейчас в процентном соотношении занимает поиск многоугольников-кандидатов к процедуре определения попадания точки внутрь многоугольника? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 16:52
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Бенедикт, Могут иметь общие точки. Пока на плоскости считаю. Хочется вообще отказаться от таблицы(в бинарном виде как то хочу всё это описать, пока объёмы большие получаются). Поиск многоугольников-кандидатов, при использовании таблицы на сервере сейчас самая не трудозатратная операция. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:15
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Точки-то понятно как заданы... А сами полигоны каким методом задаются? И кстати, сколько примерно "кандидатов" в среднем набирается каждый раз? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:22
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
AndreTM, Полигоны задаются точками которые описывают полигон по часовой стрелке(первая точка <> последней). В среднем 2-3 кандидата отбираются. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:25
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
timtim, если поиск кандидатов - "дешёвая" задача, и многоугольники могут иметь общие точки (а то и рёбра?), то надо упрощать сами многоугольники, превращая их в набор выпуклых многугольников, а в пределе - треугольников. Но это стОит памяти. Насчёт желания - поимайте сначала одного зайца. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:28
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Бенедикт, Да, треугольники самое оптимальное, но память! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:29
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
timtim, ну а в абсолютном времени, если есть самый большой по количеству вершин многоугольник, сколько работает процедура определения попадания точки? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:39
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Бенедикт, Пока неприемлемо вообще по времени. Смысл примерно в следующем (в идеале), переместил курсор и получил номер страны, федерального округа, района, улуса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:45
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
а ты через API делаешь свои регионы? можно было бы тогда PtInRegion заюзать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:48
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
тут выкладывал, тебе надо насоздавать свои регионы в коде при открытии формы, потом только поиск по массиву созданных регионов. Помогите пож ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:48
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Konst_One, Пробовал - при большом количестве точек неприемлемо. Хотя пробовал так «на посмотреть» надо ещё разок попробовать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:50
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
timtim, понятно, что неприемлемо, не понятно, почему. Тот же метод трассировки луча линеен по количеству рёбер. Даже при 23000 он должен отрабатывать менее чем за секунду, IMHO. На каком этапе задержка? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 17:51
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
тоже самое можно и полиполигонам делать, API посмотри соответствующее. когда-то делал графическую рисовалку , где линии со стрелками тягал , как раз рисовал через APIполигоны и искал их по координатам мыши, работало очень шустро ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 18:12
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
Я возьму тайм-аут, что бы не пудрить Вам мозг. У меня смешалось всё(в коде, голове). Надо всё переосмыслить и опробовать ещё раз. Спасибо за ответы! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2011, 18:36
|
|||
|---|---|---|---|
По заданной точке найти полигон |
|||
|
#18+
А вот эту тему смотрел? http://forum.ixbt.com/topic.cgi?id=26:37687:16#16 http://forum.ixbt.com/topic.cgi?id=26:37687:16#25 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=60&tablet=1&tid=2158633]: |
0ms |
get settings: |
10ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
47ms |
get topic data: |
15ms |
get forum data: |
3ms |
get page messages: |
60ms |
get tp. blocked users: |
2ms |
| others: | 358ms |
| total: | 518ms |
| 0 / 0 |
