?

Log in

No account? Create an account

Previous Entry | Next Entry

Слушайте, мои уважаемые френды, среди вас ведь куча умных людей. У многих неплохо с математикой, я думаю, а у кого-то  вполне себе и с программированием. Помогите решить задачку. Задачка совершенно реальная, в рамках моих должностных обязанностей. Более того, уже практически просроченная -- крайний срок сдачи -- утро пятницы. Не, код за меня писать не надо, код я сам напишу. помогите на уровне общего алгоритма действий. Чего-то залип я на ней -- не могу понять как сделать.

Задачка такая

Необходимо посчитать стоимость доставки из точки А в точку Б. Стоимость считается примитивно  -- есть "шахматка"  доставки из зоны в зону. Ну то есть доставка из зоны 1 в зону 1 стоит скажем 500 рублей, а из зоны 9 в зону 18  -- 7400 рублей. Цифры понятно условные. Задачка сводится к более простой -- определить зоны для каждой точки.

Зоны -- это просто Москва, расчерченная на равные прямоугольники 5*5 --итого 25 зон.  Для каждой точки есть ее географические координаты -- широта и долгота, кроме того, есть географические координаты МКАД(а) -- 108 точек, начало каждого километра. Как зная ТОЛЬКО это, найти по координатам зону?  Тем, что земля -- это не плоскость, а сфера,  при данных расстояниях можно пренебречь

По смыслу задачка ДОЛЖНА решаться, но вот как -- понять не могу, Помогите чем можете, сами мы не местные... Или как там еще в моей хипповской молодости -- "Мы приехали из маленького города Тарту. Мы отстали от поезда, все уехало, документы уехали, вещи уехали, деньги уехали, дайте 10 рублей на хлеб..."

Не, серьезно, если кто поможет -- пиво точно с меня. По желанию могу заменить на мороженное или тортик...
promo torin_kr декабрь 5, 2015 19:43 26
Buy for 200 tokens
Этот пост -- заказной. Меня его попросила написать одна моя хорошая знакомая, с которой мы знакомы такое количество лет. что аж страшно становится. Как говорит в таких случаях мой младший брат -- "Да ну нафиг. Столько и не живут". Живут... к сожалению. Ладно, это было лирическое…

Comments

( 44 comments — Leave a comment )
smenavech
Jan. 12th, 2016 02:48 pm (UTC)
простите, а зачем нужна кольцевая дорога ? Или точка в одной зоне вне кольцевой считается по другому тарифу, нежели точка б той же зоне внутри кольцевой ?

Edited at 2016-01-12 02:50 pm (UTC)
torin_kr
Jan. 12th, 2016 02:54 pm (UTC)
Кольцевая -- это просто границы Москвы... Зон ВНЕ кольцевой быть не может, все зоны ВНУТРИ кольцевой.

Ну то есть еще раз -- есть координаты границы некоего замкнутого контура. Есть точка ВНУТРИ контура. Надо, зная координаты точки, рассчитать в каком прямоугольнике внутри этого контура окажется точка, если прямоугольники расчерчены через равное расстояние, а крайние границы прямоугольников проходят через самые дальние точки контура. Так понятней?

Edited at 2016-01-12 02:55 pm (UTC)
(no subject) - hryu - Jan. 12th, 2016 03:09 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 12th, 2016 04:29 pm (UTC) - Expand
(no subject) - smenavech - Jan. 12th, 2016 03:10 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 12th, 2016 04:28 pm (UTC) - Expand
(no subject) - smenavech - Jan. 12th, 2016 04:35 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 12th, 2016 04:39 pm (UTC) - Expand
(no subject) - smenavech - Jan. 12th, 2016 08:25 pm (UTC) - Expand
(no subject) - smenavech - Jan. 12th, 2016 08:50 pm (UTC) - Expand
cthsqdjkr
Jan. 12th, 2016 03:00 pm (UTC)
Я не понимаю, почему прямоугольники возникли? Логичнее концентрические окружности провести и назвать их зонами. А для этого достаточно знать расстояние между точками, которое вычисляется по координатам
torin_kr
Jan. 12th, 2016 04:31 pm (UTC)
Да хрен его знает почему. Но так ЕСТЬ. И ради моего удобства никто границы зон не поменяет...
hryu
Jan. 12th, 2016 03:01 pm (UTC)
Условия какие-то непонятные. При чем тут МКАД? Какие еще точки даны? Если прямоугольники равные, поверхность считается плоской, то все ж вроде бы очевидно, зоны будут одинаковой ширины-высоты, все сводится к банальному попаданию точки в прямоугольник. Или там что-то сложно с разбиением??
torin_kr
Jan. 12th, 2016 04:38 pm (UTC)
Прямоугольники НЕ ПАРАЛЛЕЛЬНЫ меридианам (ну или говоря чисто математически - не параллельны осям координат) -- это основная проблемка. Они параллельны... э-э-э как бы это сказать поточнее - БОЛЬШИМ ОСЯМ контура

Edited at 2016-01-12 04:41 pm (UTC)
(no subject) - hryu - Jan. 12th, 2016 06:43 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 12th, 2016 06:55 pm (UTC) - Expand
(no subject) - hryu - Jan. 12th, 2016 07:19 pm (UTC) - Expand
budidich
Jan. 12th, 2016 03:10 pm (UTC)
Ну можно так:
В таблице с координатами точек каждоый зоны хранить также информацию:
-Зона находится в пределах МКАД = (Да/Нет/Частично)
-Координаты пересечения входной линии МКАД и границы зоны; Координаты пересечения выходной линии МКАД. (КАК их получить - вопрос. Можно отдельной обработкой найти пересечения отрезков границ зон и отрезков МКАД и раскидать их в таблицу зон)

1 - Определить, в какой зоне находится точка. (через операции сравнения, больше-меньше)
2 - Определить, находится ли эта зона в пределах мкад (это свойство можно хранить вместе с координатами каждой зоны)
3 - В пределах одной зоны решить линейное уравнение, определить, точка под границей / над границей (граница вертикальна - частный случай). Определить, с какой стороны границы находится мкад (нужно подумать). = > Ответ.

P.S.
3.й пункт посложнее. Там не линейное уравнение. Нужно проверять находится ли точнка под ломаной / над ломаной, если излом находится в пределах клетки.

Edited at 2016-01-12 03:20 pm (UTC)
budidich
Jan. 12th, 2016 03:37 pm (UTC)
Это я подразумевал, что квадраты ровные. Т.е. отдельно есть координаты квадратов отдельно координаты границы.
(no subject) - torin_kr - Jan. 12th, 2016 04:36 pm (UTC) - Expand
budidich
Jan. 12th, 2016 03:26 pm (UTC)
Вариант 2:
Для каждой зоны расчитать координаты верхней ломаной и нижней ломаной.
Хранить в таблице вида
Зона1 - Верхняя граница - X1Y1-X2Y2
Зона1 - Верхняя граница - X2Y2-X3Y3
Зона1 - Верхняя граница - X3Y3-X4Y4
Зона1 - Нижная граница - X1Y1-X2Y2
Зона1 - Нижная граница - X2Y2-X3Y3
Зона1 - Нижная граница - X3Y3-X4Y4

Можно легко определить, что точка ниже верхней границы зоны, выше нижней.
ypary
Jan. 12th, 2016 03:49 pm (UTC)

День добрый. Случайно наткнулся на запись. Это по сути классическая задача определения принадлежности точки многоугольнику (на компьютерной графике такое читают). Вот пример алгоритмов для выпуклых и вогнутых многоугольников: www.gamedev.ru/code/forum/?id=43108

ypary
Jan. 12th, 2016 04:00 pm (UTC)

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

(no subject) - torin_kr - Jan. 12th, 2016 04:34 pm (UTC) - Expand
abienscumvento
Jan. 12th, 2016 05:50 pm (UTC)
Один раз завести большую плоскость для рисования. Нарисовать прямоугольники, вычислить координаты углов большого квадрата. Дальше вспомнить аналитическую геометрию и написать функцию для перевода нормальных географических координат в условные московские, такие, чтобы линии сетки были параллельны осям.
Все это можно сделать без рисунка, но с рисунком проще. Размер плоскости зависит от точности вычисления координат.

Edited at 2016-01-12 05:54 pm (UTC)
torin_kr
Jan. 12th, 2016 06:01 pm (UTC)
Скорее всего я именно так и сделаю. Но красиво конечно было бы решить чисто математическими методами, БЕЗ рисования. Но когда до дедлайна два дня тут уже не до красивости...
(no subject) - abienscumvento - Jan. 12th, 2016 06:20 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 12th, 2016 06:32 pm (UTC) - Expand
(no subject) - abienscumvento - Jan. 13th, 2016 07:08 am (UTC) - Expand
shardon74
Jan. 12th, 2016 07:18 pm (UTC)

Выбери ближайшую по иксу справа и слева и выбери ближайший по игроку справа и слева всего четыре точки Посчитай расстояние от них до искомой и выбери наименьшие

Alexander Sheptyakov
Jan. 13th, 2016 11:28 am (UTC)
Я бы решал через преобразование координат.

То есть провел бы новые оси Х и У параллельно сторонам прямоугольников, написал бы функцию перевода координат точки (для которой нужно определить нужный квадратик) из одной координаты в другую (https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%D0%B0) Получается, что задача сводится к точно такой же, но как будто бы стороны квадратов параллельны меридианам и широте. А это вроде как легко.

P.S. программировать не умею )
Александр Шептяков
Jan. 13th, 2016 11:28 am (UTC)
Я бы решал через преобразование координат.

То есть провел бы новые оси Х и У параллельно сторонам прямоугольников, написал бы функцию перевода координат точки (для которой нужно определить нужный квадратик) из одной координаты в другую (https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%D0%B0) Получается, что задача сводится к точно такой же, но как будто бы стороны квадратов параллельны меридианам и широте. А это вроде как легко.

P.S. программировать не умею )
Александр Шептяков
Jan. 13th, 2016 11:37 am (UTC)
А как определить находится ли точки внутри МКАДа - провести из точки лучи до каждой точки на МКАДе, и посчитать максимальный угол между получившимися лучами. Если точка будет за мкадом, то максимальный угол будет больше 180 градусов.
Правда это применимо только если МКАД и точки на нем расположены более-менее "кругло" без изгибов.
В местах изгиба МКАДа можно нарисовать отдельные квадраты и если точка попадает в такие области, уже решить задачу локильно на наких квадратах.
Способ конечно очень кривой, но я думаю, что запрограммировать его можно быстро)

Edited at 2016-01-13 11:49 am (UTC)
abienscumvento
Jan. 13th, 2016 11:56 am (UTC)
Максимальный угол будет меньше 180. Можно зафиксировать центр и считать максимум от него в обе стороны, а не попарно. В википедии МКАД вроде выпуклый многоугольник.
(no subject) - Александр Шептяков - Jan. 13th, 2016 01:17 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 13th, 2016 12:11 pm (UTC) - Expand
(no subject) - Александр Шептяков - Jan. 13th, 2016 01:19 pm (UTC) - Expand
(no subject) - abienscumvento - Jan. 13th, 2016 02:20 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 13th, 2016 05:52 pm (UTC) - Expand
(no subject) - abienscumvento - Jan. 14th, 2016 07:23 am (UTC) - Expand
(no subject) - torin_kr - Jan. 14th, 2016 09:48 am (UTC) - Expand
(no subject) - abienscumvento - Jan. 14th, 2016 05:24 pm (UTC) - Expand
(no subject) - torin_kr - Jan. 14th, 2016 05:27 pm (UTC) - Expand
(no subject) - abienscumvento - Jan. 15th, 2016 06:47 am (UTC) - Expand
( 44 comments — Leave a comment )