Общая точка на двух картах.

и задачки для интервью.
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Общая точка на двух картах.

Post by Hoochin »

Еще одно геометерическое построение.

Есть 2-е карты одного и тогоже прямоугольника на местности исполненные в разных маштабах. Скажем, одна карта имеет маштаб 1:a, а вторая - 1:b.

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

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

P.S. если условие не ясно, могу перефразировать. Надо узнать только что не ясно.
User avatar
olg2002
Уже с Приветом
Posts: 990
Joined: 27 Mar 2002 10:01
Location: Palo Alto, CA

Post by olg2002 »

Ну, это просто (хотя формулировка задачи достаточно эффектная!).

Пусть ABCD - больший прямоугольник, и abcd - меньший. Найдем точки пересечения: K = ab x AB, L = bc x BC, M = cd x CD, N = da x DA. Искомая точка лежит на пересечении KM и LN. Если ab || AB, тогда искомая точка - aA x bB, она же aA x сС (если единственная), она же aA x dD.
User avatar
Etherlord
Уже с Приветом
Posts: 3260
Joined: 13 Dec 2005 07:20
Location: Lviv, UA->San Diego, CA

Re: Общая точка на двух картах.

Post by Etherlord »

Hoochin wrote:Спрашивается, как геометрически с помощью линейки и циркуля найти ту общую точку на картах, которая отображает одно и то же место на земле.

P.S. если условие не ясно, могу перефразировать. Надо узнать только что не ясно.


Военку напомнили. Экзамен по военной топографии. Только там еще в придачу эти точки в виде танчиков, БМП и БТРов надо было рисовать :х
Хорошо, что препод волшебными линзами взял, т.е. бутылками водки :mrgreen:
User avatar
Poryadok
Уже с Приветом
Posts: 1383
Joined: 17 Jan 2005 22:33
Location: Minsk, Belarus - Beaverton, OR

Post by Poryadok »

А я софт такой писал еще когда Союз не распался. Для линейного случая нужно было три точки привязки, для квадратичного - шесть (квадратичный был актуален в связи с тем что Земля как оказалось совсем не плоская и чем ближе к полюсам тем больше искажения, причем на разных картах они разные).
Отлипай давай от форума и марш работать!
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Post by Hoochin »

olg2002 wrote:Ну, это просто (хотя формулировка задачи достаточно эффектная!).



hmm, I have a different solution. Do you have a proof of yours?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Назовём один прямоугольник - ABCD, а другой - A'B'C'D'.
Найдём точку P - пересечение прямых AB и A'B'.
Построим две окружности, проходящие через точки PAA', и PBB'.
Пересечение этих окружностей и есть искомая точка.
User avatar
sergeman
Уже с Приветом
Posts: 661
Joined: 08 Apr 2001 09:01
Location: Москва -> New Jersey

Post by sergeman »

venco wrote:
Назовём один прямоугольник - ABCD, а другой - A'B'C'D'.
Найдём точку P - пересечение прямых AB и A'B'.
Построим две окружности, проходящие через точки PAA', и PBB'.
Пересечение этих окружностей и есть искомая точка.

Не понятно.
You do not have the required permissions to view the files attached to this post.
---------------------------
Too Old To Die Young©
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Post by Hoochin »

sergeman wrote:
venco wrote:
Назовём один прямоугольник - ABCD, а другой - A'B'C'D'.
Найдём точку P - пересечение прямых AB и A'B'.
Построим две окружности, проходящие через точки PAA', и PBB'.
Пересечение этих окружностей и есть искомая точка.

Не понятно.


Не точто совсем непонятно, а понятно что
абсолютно неправильно.
User avatar
rvd
Уже с Приветом
Posts: 1418
Joined: 04 Aug 2005 19:12

Re: Общая точка на двух картах.

Post by rvd »

Hoochin wrote:если условие не ясно, могу перефразировать. Надо узнать только что не ясно


1. пренебрегать сферичными искажениями карты?
2. учитывать вращение ?
Лучшее - враг хорошего!
User avatar
sergeman
Уже с Приветом
Posts: 661
Joined: 08 Apr 2001 09:01
Location: Москва -> New Jersey

Re: Общая точка на двух картах.

Post by sergeman »

rvd wrote:
Hoochin wrote:если условие не ясно, могу перефразировать. Надо узнать только что не ясно


1. пренебрегать сферичными искажениями карты?
2. учитывать вращение ?

Я так понимаю что, карта не обязательно географическая, а например игральная. Туз пик. Туз большои и туз маленький. Один кинули на другой произвильным образом. Ну или еше проще: два подобных прямоугольника.

To Hoochin: Я сдаюсь. Можно решение в приват.
---------------------------
Too Old To Die Young©
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Hoochin wrote:
sergeman wrote:Не понятно.

Не точто совсем непонятно, а понятно что
абсолютно неправильно.

Всё таки непонятно. :)
You do not have the required permissions to view the files attached to this post.
Last edited by venco on 15 Feb 2007 23:34, edited 1 time in total.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: Общая точка на двух картах.

Post by venco »

sergeman wrote:To Hoochin: Я сдаюсь. Можно решение в приват.

Уже два решения на этой странице есть: от olg2002 и от меня.
User avatar
rvd
Уже с Приветом
Posts: 1418
Joined: 04 Aug 2005 19:12

Post by rvd »

venco wrote:Всё таки непонятно. :)


а можно как-то их подвинуть, чтобы ассиметрично, а то не видно ничего?
кстати, как по трем точкам вы круг провели? или ета задача уже была? :-)

p.s. на 2-ой вопрос не надоотвечать - Euclid ето уже сделал :-)
Лучшее - враг хорошего!
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

rvd wrote:а можно как-то их подвинуть, чтобы ассиметрично, а то не видно ничего?

Подвинул чуток. А что не видно то?

кстати, как по трем точкам вы круг провели?

Это классика - пересечение двух срединных перпендикуляров.
User avatar
sergeman
Уже с Приветом
Posts: 661
Joined: 08 Apr 2001 09:01
Location: Москва -> New Jersey

Post by sergeman »

venco wrote:
Hoochin wrote:
sergeman wrote:Не понятно.

Не точто совсем непонятно, а понятно что
абсолютно неправильно.

Всё таки непонятно. :)

Теперь понятно. Красиво.
---------------------------
Too Old To Die Young©
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Post by Hoochin »

venco wrote:
Hoochin wrote:
sergeman wrote:Не понятно.

Не точто совсем непонятно, а понятно что
абсолютно неправильно.

Всё таки непонятно. :)


Да, я не правильно прочитал Ваше решение. Я подумал что P - центр окружности.

My bad!

Похоже на мое решение, окружности, правда, я строил по двум точкам и условии соблюдения отношения расстояний AB/A'B'.

Не уверен что ваше решение дает такой же исход, как и решение Olg...
Не знаю.

ABCD - larger than A'B'C'D'.
Мое решение. Построим окружности по точкам BB' и AA' так что бы все точки окружностеы, Xb и Xa соответстевнно, что бы они имели одинаковое отношение расстояний XbB / XbB' = AB/A'B' и соответстевенно XaA / XaA' = AB/A'B'.
Для етого надо отложить два отрезка от B по BB" (произвол.) один за другим с длиннами AB и A'B', т.е. BY и YZ (BY=AB, YZ=A'B') и наити точку T между B и B' на BB' так что BT/TB' = AB/A'B' , затем наити точку T' снаружы (не между) но на BB' . Центр проводимой окружности ровно посредине T и T'.
Аналогичные действия делаем с AA' получаем другую окружность со всеми точками удаленными от A и A' с пост. отножением (см. выше).

Если чего не так, простите, сложно описать.
2 других решения я не понял как работают... :appl:

Посмотрел на картинку - блеск! Похоже оба решения от Venco и Olg200Х очень похожи по сути.
User avatar
olg2002
Уже с Приветом
Posts: 990
Joined: 27 Mar 2002 10:01
Location: Palo Alto, CA

Post by olg2002 »

Hoochin wrote:hmm, I have a different solution. Do you have a proof of yours?


Отношение расстояний от любой точки на прямой KM до сторон AB и ab постоянно и равно отношению |AB|/|ab| (из соотношений подобия), следовательно искомая точка обязана лежать на этой прямой. Аналогичные рассуждения для прямой LN приводят к тому, что искомая точка лежит на пересечении LN и KM.
И все одной линейкой, что интересно.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

olg2002 wrote:И все одной линейкой, что интересно.

Мне ваше решение больше понравилось. :great:
Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Post by Deynekin »

Кстати, эта задача - пожалуй, самая идеальная иллюстрация "Принципа сжимающих отображений", все нехитрые условия налицо:

1. Метрическое пространство (карта) отображается строго само в себя (меньшая карта-образ целиком наложена на исходную карту-прообраз)

2. Отображенте сжимающее: расстояние ρ(a,b) между любыми двумя точками-образами a и b меньше расстояния между их прообразами A и B:
ρ(a,b) <= const*ρ(A,B), const<1 (!)

Отсюда получаем ещё одно решение, правда, не "циркульно-линейковое", но посредством итераций, которые в данном случае обязаны сойтись к искомой точке:

Фотографируем наши наложенные карты М0 и М1, сжимаем изображение и поворачиваем-накладываем его так, чтобу ужатая М0 точно легла на исходную М1, при этом ужатая М1 даст свою уменьшенное изображение М2. ...И т.д. - Процесс сойдётся как геометрическая прогрессия с коэффицииентом К, т.е. как K^n, где К - отношение размера меньшей карты к большей.
--------
PS Красивая задача, жаль, что я "пролетел", когда её поставили
User avatar
Hoochin
Уже с Приветом
Posts: 1031
Joined: 29 Nov 2006 22:09
Location: Si Valley

Post by Hoochin »

olg2002 wrote:
Hoochin wrote:hmm, I have a different solution. Do you have a proof of yours?


Отношение расстояний от любой точки на прямой KM до сторон AB и ab постоянно и равно отношению |AB|/|ab| (из соотношений подобия), следовательно искомая точка обязана лежать на этой прямой. Аналогичные рассуждения для прямой LN приводят к тому, что искомая точка лежит на пересечении LN и KM.
И все одной линейкой, что интересно.


Olg2002,

btw, Вы проверили работает ли ваше решение если карта перевернута на ca. 180 градусов, более 180 гр?
User avatar
Etherlord
Уже с Приветом
Posts: 3260
Joined: 13 Dec 2005 07:20
Location: Lviv, UA->San Diego, CA

Post by Etherlord »

А вот что делают в похожей ституации военные:
http://miltop.narod.ru/Snapshot/scheduled.htm
User avatar
olg2002
Уже с Приветом
Posts: 990
Joined: 27 Mar 2002 10:01
Location: Palo Alto, CA

Post by olg2002 »

Hoochin wrote:Olg2002,

btw, Вы проверили работает ли ваше решение если карта перевернута на ca. 180 градусов, более 180 гр?


Мое решение, похоже, будет работать, даже если карта действительно перевернута (зеркальное отображение), а не только повернута на угол более 180 градусов.
Я бы и не задумался, если бы Вы так не спросили.
Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Post by Deynekin »

Это ничего, если я "с некоторым опозданием" ещё одно решение добавлю? на днях само поутру приснилось.

Обозначения:
k - коэффициент сжатия (отношение масштабов карт), k < 1.
AB и ab - два однотипных отрезка большой и маленькой карт, соотв. (напр., "западные" стороны их рамок)
Т* - искомая точка.

Решение:
Вектор aT* для малой карты служит тем же, чем вектор AT* для большой, отсюда для их длин имеем: aT* = k * AT*. Более того, угол α между этими векторами задан - это угол поворота одной карты отн. другой.

Задача свелась к построению треугольника AaT* по заданной длине Aa, противолежащему углу α и заданному отношению k двух остальных сторон aT* и AT*.
Один треугольник, подобный искомому, в задаче уже имеется - это треугольник, построенный на векторах Aa и Bb. - Дальше просто.

Достоинства решения:
1. Решение логически-естественное, "straight forward"; оно не производит впечатление фокуса, который ещё нужно разгадывать.
2. Решение чисто линейное (пересечения окружностей, как у venco - это уже вторые степени в соотв. уравнениях, чего всегда, если возможно, хочется избежать).
3. Используется минимальное количество соотв. пар точек исходной и ужатой карт: понадобились всего две пары: (Aa) и (Bb)
User avatar
rvd
Уже с Приветом
Posts: 1418
Joined: 04 Aug 2005 19:12

Post by rvd »

Deynekin wrote:Это ничего, если я "с некоторым опозданием" ещё одно решение добавлю? на днях само поутру приснилось.

Обозначения:
k - коэффициент сжатия (отношение масштабов карт), k < 1.
AB и ab - два однотипных отрезка большой и маленькой карт, соотв. (напр., "западные" стороны их рамок)
Т* - искомая точка.

Решение:
Вектор aT* для малой карты служит тем же, чем вектор AT* для большой, отсюда для их длин имеем: aT* = k * AT*. Более того, угол α между этими векторами задан - это угол поворота одной карты отн. другой.

Задача свелась к построению треугольника AaT* по заданной длине Aa, противолежащему углу α и заданному отношению k двух остальных сторон aT* и AT*.
Один треугольник, подобный искомому, в задаче уже имеется - это треугольник, построенный на векторах Aa и Bb. - Дальше просто.

Достоинства решения:
1. Решение логически-естественное, "straight forward"; оно не производит впечатление фокуса, который ещё нужно разгадывать.
2. Решение чисто линейное (пересечения окружностей, как у venco - это уже вторые степени в соотв. уравнениях, чего всегда, если возможно, хочется избежать).
3. Используется минимальное количество соотв. пар точек исходной и ужатой карт: понадобились всего две пары: (Aa) и (Bb)

так все умеют, "ты нам мурку сыграй!" (c), с циркулем и линейкой :-)
Лучшее - враг хорошего!
Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Post by Deynekin »

rvd wrote:так все умеют, "ты нам мурку сыграй!" (c), с циркулем и линейкой :-)
Простите, rvd, я что-то не совсем понял: это "взаправдошное" возражение, или здесь всё-таки смайлик главнее?

На случай, если всё же "взаправдошное": в этом решении всё как раз классически выполнимо "циркулем и линейкой".

Но если хотите, вот Вам другая задачка-шуточка именно для "циркуля и линейки":

Для заданного отрезка и произвольно заданного числа k построить отрезок, длина которого в k раз больше. :roll:

Return to “Головоломки”