Прошу помочь вот в каком вопросе:
Все знают функции Винды для работы с так называемыми регионами!
Очень классная вещь, не правда ли!? Но вот КАК получить вершины региона из его HRGN ???
И возможно ли это??
Вот кстати и задачка в связи с этим:
Два треугольника на плоскости могут прекрываться любым из возжных способов!!!!
Задача -- независимо от способа перекрытия треугольников определять вершины области их прекрытия!!
Как вам???
Или хотя бы находить точку 100%-но принадлежащую этой области!!
Я ломаю голову уже почти месяц!!! Хотел с помощью регионов виндовозных решить — но видать забыл ....
Благодарен заранее.. HI-TECH
Вот вам задачка по геометрии... Решивший может считать себя Евклидом и Пифагором вместе взятыми!!!
Здравствуйте HI-TECH, Вы писали:
HT>Все знают функции Винды для работы с так называемыми регионами! HT>Очень классная вещь, не правда ли!? Но вот КАК получить вершины региона из его HRGN ??? HT>И возможно ли это??
Нет, невозможно. Внутреннее представление регионов не дает такой возможности.
HT>Вот кстати и задачка в связи с этим:
HT>Два треугольника на плоскости могут прекрываться любым из возжных способов!!!! HT>Задача -- независимо от способа перекрытия треугольников определять вершины области их прекрытия!!
Это только аналитически, регионы GDI тут не помогут. Решать аналитически — думать надо, так что тут помочь ничем не могу.
HT>Или хотя бы находить точку 100%-но принадлежащую этой области!!
А вот это можно сделать регионами. Берешь два региона, пересекаешь, а потом делаешь GetRegionData для пересечения. Выбираешь любую точку.
Здравствуйте HI-TECH, Вы писали:
HT>Я ломаю голову уже почти месяц!!! Хотел с помощью регионов виндовозных решить — но видать забыл что у Билли прадед — отец всех недоносков и недоделок этой цивилизации....
Родной, ну если уж ты кидаешься такими выражениями, то возьми учебник по аналитической геометрии, плюс, научись работать с целой арифметикой, и все, месяц можно было и не терять.
Здравствуйте Sashko, Вы писали:
S>Родной, ну если уж ты кидаешься такими выражениями, то возьми учебник по аналитической геометрии, плюс, научись работать с целой арифметикой, и все, месяц можно было и не терять. S>Евклид и Пифагор наверно в гробу перевернулись.
Здравствуйте Сашко!!!!
Свои выражения я могу легко доказать (как и ...на вскидку пара миллионов человек еще) на примере WinAPI!
Евклид тут уж точно совсем не причем!!! А вот пифагор, царство ему небесное, рад был бы да помочь мне не может! А жаль!
А задачку я решил, хотя не совсем ту что ставились в сабж, но цель достигнута!!
Для общего развития скажу -- аналитическая геометрия может все! То что она не может — может Дифференциальное исчисление!!
И если бы тактовая частота средне взвешенного пользовательского процессора составляла около 100 гигагерц — Я вообще бы не задавал таких вопросов!!!
А если поразмыслить решение сабж полезно было бы всем!
И что Вы уважаемые тут обсуждаете??? Это же элементарнее простого!!!
Я сам столкнулся с такой проблемой, когда писал движок для игры!!
Вот так выглядит примерный!!! алгоритм решения задачи (по заданной точке x,y установить принадлежность ее треугольнику, заданному вершинами в массиве T[]={x1,y1,x2,y2,x3,y3,...} )
Текст на С++:
-----------
int m; // это индекс в массиве T[], на тот случай если треугольников много :)
float ma=0.001; // микро-приращение дабы избежать неприятности вида <число>/0, выбирается произвольно
bool i1=i2=p1=p2=FALSE; // локальные переменные
int s1=s2=s3=s4=1;
if (T[m]-T[m+2]==0)
s1=sign (T[m+4]-T[m+2]);
if (T[m+4]-T[m+2]==0)
s2=sign (T[m]-T[m+2]);
if (T[m]-T[m+4]==0)
s3=sign (T[m+2]-T[m+4]);
if (T[m+2]-T[m+4]==0)
s4=sign (T[m]-T[m+4]);
if ((T[m]-T[m+2])*(T[m+4]-T[m+2])<0)
i1=TRUE;
if ((T[m]-T[m+4])*(T[m+2]-T[m+4])<0)
i2=TRUE;
if (i1)
{
if ((k1<k11&&k1<k12)||(k1>k11&&k1>k12))
p1=TRUE;
}
else
if ((k1<k11&&k1>k12)||(k1>k11&&k1<k12))
p1=TRUE;
if (i2)
{
if ((k2<k21&&k2<k22)||(k2>k21&&k2>k22))
p2=TRUE;
}
else
if ((k2<k21&&k2>k22)||(k2>k21&&k2<k22))
p2=TRUE;
if (p1&&p2) {...} — это условие того, что точка x,y действительно принадлежит треугольнику
----------
PS:Для установления принадлежности т. x,y двум и более треуг-ам проверить принадлежность для обеих отдельно и сделать соответствующий вывод: если оба принадлежат, то x,y соответственно принадлежит обеим :)
Тут все даже проще. Нам всего лишь надо найти вершины области пересечения.
Ищем все точки пересечения сторон треугольника. Если они есть, то искомые вершины — это они, плюс, возможно, некоторые из вершин самих треугольников. Вариантов немного, так что написать такую функцию сверхбольшого труда не должно составлять.
Здравствуйте Sergius, Вы писали:
S>Здравствуйте Andruha.
S>Тут все даже проще. Нам всего лишь надо найти вершины области пересечения. S>Ищем все точки пересечения сторон треугольника. Если они есть, то искомые вершины — это они, плюс, возможно, некоторые из вершин самих треугольников. Вариантов немного, так что написать такую функцию сверхбольшого труда не должно составлять.
Чисто в решении конкретной такой задачи проблемы естественно нет никакой!
Суть в том что нужен алгоритм работающий:
а) со всеми случаями перекрытия треугольников
б) работающий быстро!
Здравствуйте HI-TECH, Вы писали: HT>Суть в том что нужен алгоритм работающий: HT>а) со всеми случаями перекрытия треугольников HT>б) работающий быстро!
HT>Есть такие варианты??
Есть стандартный алгоритм для определения пересекаются ли два выпухлых полигона. Описан в книжках. На изобретение с "нуля" и программную демонстрацию уходит у среднего студента 1-2 недели. Ваш случай _намного_ проще: полигоны всего из трех вершин. Число типов пересечения — по пальцам пересчитать. Надо просто взять бумажку и порисовать маленько.
<Off>Заинтересовывать можно вопросами, у которых либо постановка интересная либо решение неочевидно либо еще что-то. У данной задачи решение достаточно простое.</Off>
Успехов!
К этому моменту у меня внутри 0.5, 0.7, 0.33 (с) НС
=cut= HT>Два треугольника на плоскости могут прекрываться любым из возжных способов!!!! HT>Задача -- независимо от способа перекрытия треугольников определять вершины области их прекрытия!! HT>Как вам???
Да так себе... Это задача по аналитической геометрии для первого курса матфака — не сложная, но ооооочень длинная, скучная и нудная. HT>Я ломаю голову уже почти месяц!!! Хотел с помощью регионов виндовозных решить — но видать забыл что у Билли прадед — отец всех недоносков и недоделок этой цивилизации.... HT>(простите мне это выражение)
Чё тут прощать-то? На правду только ландухи обижаются.
=cut=
Иными словами, тебе нужно определить к-ты точки пересечения двух прямых, содержащих стороны разных треугольников.
Итак, идея состоит в следующем:
1)взять учебник по аналитической геометрии и открыть главы "Прямая линия" и "Взаимное расположение точек и прямых";
2)в главе "Прямая линия" найти уравнение прямой, проходящей через две данняе не совпадающиеточки Р1(х1,у1) и Р2(х2,у2):
((у-у1)/(у2-у1))=((х-х1)/(х2-х1)), где х1,у1 и х2,у2 — координаты двух вершин треугольника.
Таким образом, для каждой стороны треугольников получится уравнение прямой вида:
у=kx+b (знакомо?);
3)из "Взаимного расположения точек и прямых" взять координаты точки (xo,yo) пересечения двух прямых
y=k1x+b1,
y=k2x+b2 , которые определяются из следующих уравнений: xo=(b1-b2)/(k2-k1), yo=(k2b1-k1b2)/(k2-k1).
Ну, вот тебе теория, применить которую на практике труда не должно составить. Для начала тебе нужно определить, пересекаются ли треугольники (это просто). NB!!!!! при определении точек пересечения нужно помнить, что ты находишь точки пересечения ПРЯМЫХ, а не отрезков, по этому, когда найдешь точку, обязательно нужно будет проверить принадлежит ли она обеим СТОРОНАМ стреугольника (это тоже просто).
Можно конечно еще поломать голову над методом для определения количества точек пересечения треугольников, но я бы просто двумя for'ами перебрал все возможные варианты пересечения сторон.
ЗЫ Ежели не понятно, мыль на
Здравствуйте Sashko, Вы писали: HT>>Я ломаю голову уже почти месяц!!! Хотел с помощью регионов виндовозных решить — но видать забыл что у Билли прадед — отец всех недоносков и недоделок этой цивилизации.... S>Родной, ну если уж ты кидаешься такими выражениями, то возьми учебник по аналитической геометрии, плюс, научись работать с целой арифметикой, и все, месяц можно было и не терять. S>Евклид и Пифагор наверно в гробу перевернулись.
Мне кажется не то чтобы повернулись, просто целый месяц вертелись там как пропеллеры
Господа, не хватит ли нам молоть воду в ступе? Ведь вопрос примитивный. Если нужна точка на 100% (термин то какой корректный и программистский, чай не метод Монте-Карло) приналдежащая обоим треугольникам, то возьми точку пересечения двух сторон разных треугольников. Вот и вся любовь.
Кендер
Re: Задачка по геометрии! Зубы поломаешь...
От:
Аноним
Дата:
26.10.02 10:46
Оценка:
Здравствуйте HI-TECH, Вы писали:
HT>Прошу помочь вот в каком вопросе: HT>Все знают функции Винды для работы с так называемыми регионами! HT>Очень классная вещь, не правда ли!? Но вот КАК получить вершины региона из его HRGN ???
это будет первым вопросом
HT>Два треугольника на плоскости могут прекрываться любым из возжных способов!!!! HT>Задача -- независимо от способа перекрытия треугольников определять вершины области их прекрытия!! HT>Как вам??? HT>Или хотя бы находить точку 100%-но принадлежащую этой области!!
а это следущими
Итак:
HRGN rgnRes, rgnTri1, rgnTri2;
// создаём треугольники rgnTr1 и rgnTri2 ( CreatePolygonRgn )int res = CombineRgn( rgnRes, rgnTri1, rgnTri2, RGN_AND );
if (res==ERROR) {
// ошибка
} else if (res==NULLREGION) {
// нет пересечения
} else {
// пересекаются
DWORD sz = GetRegionData( rgnRes, 0, 0 );
RGNDATA *buf = (RGNDATA*)new char[sz];
GetRegionData( rgnRes, sz, buf );
// buf->rdh.iType должен быть RDH_RECTANGLES
sz = buf->rdh.nCount; // кол-во RECTов
// итак, мы получили список RECTов, состовляющих область пересечения
// следовательно, любая точка RECTа принадлежит области пересечения ( КРОМЕ ПРАВОЙ И НИЖНЕЙ ГРАНИЦЫ!!! )for (RECT *p=(RECT*)buf->Buffer; sz>0; --sz, ++p) {
// пробегаем по всем RECTaм
// p->Left...
// ........................
}
delete[] (char*)buf;
}
а принадлежность точки региону можно узнать через PtInRegion ( если код уже есть, то зачем его писать? )
Здравствуйте, HI-TECH, Вы писали:
HT>здравствуйте!!
HT>Прошу помочь вот в каком вопросе: HT>Все знают функции Винды для работы с так называемыми регионами! HT>Очень классная вещь, не правда ли!? Но вот КАК получить вершины региона из его HRGN ??? HT>И возможно ли это??
HT>Вот кстати и задачка в связи с этим:
HT>Два треугольника на плоскости могут прекрываться любым из возжных способов!!!! HT>Задача -- независимо от способа перекрытия треугольников определять вершины области их прекрытия!! HT>Как вам??? HT>Или хотя бы находить точку 100%-но принадлежащую этой области!!
HT>Я ломаю голову уже почти месяц!!! Хотел с помощью регионов виндовозных решить — но видать забыл ....
HT>Благодарен заранее.. HI-TECH
HT>Вот вам задачка по геометрии... Решивший может считать себя Евклидом и Пифагором вместе взятыми!!!
Может, я не понял идеи, но, если надо найти точку внутри региона, то вроде как есть такая функция — ptInRegion, которая возвращает true, если точка принадлежит региону... Работает для любых сложных регионов. Сам проверял. А насчет вершин — есть ф-я GetRegionData, которая возвращает внутреннее представление региона. Посмотри, может, поможет.
А насчет вершин такая ситуация — у тебя есть шесть линий (стороны прямоугольника). Каждая линия задается уравнением прямой, проходящей через две точки. Уравнение можно найти в любом справочнике по аналитической геометрии (хотя бы в Выгодском). По уравнению двух прямых можно найти точку их пересечения, просто решив систему их этих двух уравнений (решается матричным способом. способ можно найти в интернете, а общая картина такова: уравнение1 : ax+by=c
уравнение 2: dx+ey=f. A — матрица коэффицентов (a,b,d,e) X — вектор переменных (x,y) B — вектор свободных коэффициентов (c,f). Систему из двух вышеприведенных уравнений можно записать, как AX=B, следовательно, решение системы X (т.е. значения x и y) находится как X=A^-1B (а в минус первой на б) A^-1 — это обратная матрица к A. Поскольку матрица A 2x2, то для A^-1 можно вообще сразу записать формулу (тоже можно найти в инете — но на самом деле это At/det(A), где At — транспонированная A, det(A) — определитель A = a*e-b*d). Если det(A)=0, то прямые либо параллельны, либо совпадают. Если det(A) не 0 — находятся (x,y) точки пересечения. Найдя таким образом точки пересечения каждой с каждой прямой, ты найдешь вершины полученной фигуры.
