[hasherfrog]

Почему я упомянул про 1. Давным-давно (лет двенадцать назад) я решал такую задачу. Есть карта Москвы, улицы - полилинии, дома даны в виде полигонов (не путать с полилинией), у каждого свой Id, координаты в базе. Надо определить, куда попал пользователь мышой, выдать подпись "Улица/дом". Очевидно, что объектов очень много, поэтому было использована технология (громко сказан :]) нескольких "окон".

Ещё до вывода, до отрисовки, вообще "до", в самом формировании базы, все дома (точнее, прямоугольники, куда входили полигоны домов) отфильтровывались по оси Y. У каждого дома, дополнительно, в соответствии с его ID, хранился прямоугольник boundaries, ы который "вписывался дом". При выводе на экран бинарным деревом отфильтровывались Id тех ненужных домов, которые оказывались вне экранного окна по Y (min/max окна). Потом отфильтровывались (емнип, тупым перебором) по данным прямоугольников boundaries дома оставшиеся - теперь выкидывались те, кто оказался вне экрана по оси X. Из оставшихся формировался список Idэшек, который хранился до тех пор, пока пользователь не сменит масштабирование/не проскроллит экран. По этому списку дома отрисовывались, если надо было перерисовать экран.

Когда пользователь кликал мышой, координата пересчитывалась в реальные. Этот XY использовался для отфильтровки из "хранимого" Id-списка всех тех "близлежащих" домов, прямоугольные boundaries которых содержали в себе тыкнутую точку. Потом начиналось самое дурацкое - определение "попал-не-попал" для полигона и точки. Сейчас я (вот прямо сейчас :] ага. Нет уж, когда время будет и когда доки дпишу китайцам) ищу/пишу нормальный алгоритм того же самого, потому что старые (подсчёт и анализ количества точек пересечений всех сторон полигона с горизонтальной осью x=x_точки_тыка слева от y_точки_тыка) меня перестал устраивать. Правда, сегодняшняя задача у меня много проще, нет такого количества данных, примитивный coreldraw :]

Когда-то (это уже лет пять назад) я писал в AutoCAD, с использованием ихнего :] API, там было всё круто насчёт определения очки пересечения отрезков - это было вшито в библиотеки и работало как электровеник. Но во реализация и алгоритм их мне не известен, поэтому у меня свой :]

***

Что касается вопроса 2. Для линий всё немного проще. Вы (ну в смысле я) делаете небольшой виртуальный крестик из двух отрезков, превращая точку в плюсик. И у двух отрезков данного плюсика ищете точки пересечения с отрезками из заданной полилинии (с минимальной двухуровневой оптимизацией. основанной на тех же "окнах": окно всей полилинии vs boundaries крестика и окна отрезков крестика vs каждый отрезок полилинии при поиске точки тересечения). Если пересечение есть, считаете, что пользватель "попал". Можно брать не крестик, а квадратик (если мышиный курсор у Вас не квадратик, а стрелочка, лучше брать всё-таки "плюсик-крестик").

***


Вот по поводу именно GDI - я не знаю. У меня всегда расчёт шёл в double-числах, может, для integer'ов можно как-то всё ещё прооптимизировать...

бинарным деревом :D чё сказал?