Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Пересечение фигур [D7, XP]

Newss © (2008-07-31 23:08:00)
Здравствуйте!
Задача такая: у меня есть 2 n-угольника, расположенные один в другом (количество углов каждого не больше 8). Внутренний многоугольник можно двигать внутри внешнего, но так, чтобы он не выходил за границы внешнего многоугольника. Не подскажете, как мне организовать проверку, пересекает ли маленький многоугольник границы большого?
Спасибо.

oldman (2008-08-01 16:13:00) [1]
Задача не стоит выеденного яйца.

Строим для первой фигуры внутреннюю огибающую
Строим для второй фигуры внешнюю
Находим решения для системы двух уравнений

Dennis I. Komarov (2008-08-01 14:51:00) [2]
ЗЗЫ - точка пересечения не должна быть вершиной

han_malign (2008-08-01 13:46:00) [3]
Есть примитив - принадлежность точки многугольнику...
Получаем условие: (mi принадлежит M, i = 1..n) и (Mi не принадлежит m, i = 1..N)

В ТФКП можно найти более оптимальное решение - через круговые интегралы...

Нат (2008-08-01 13:21:00) [4]
Для определения вероятной "зоны контакта" можно использовать окружности одну, вписанную в большой м-к, другую, описанную вокруг малого.
Чем более кривые много уг-ки, тем больше погрешность.
Можно использовать секущую прямую для получения точек пересечения с границами обоих мн-в, анализировать расположение точек пересечения на секущей.
Положение секущей и направление ее перемещения - подбирать для оптимизации.
Частный случай - совпадение секущей с какой-либо гранью одного мн-ка.
Можно использовать секущую окружность, изменяя радиус.

Vlad Oshin (2008-08-01 13:17:00) [5]
CreatePolygonRgn
The CreatePolygonRgn function creates a polygonal region.

CombineRgn
- Return Values NULLREGION The region is empty.

KilkennyCat (2008-08-01 12:48:00) [6]

> Dennis I. Komarov © (01.08.08 12:30) [13]

да вроде бы, без разницы.

Dennis I. Komarov (2008-08-01 12:30:00) [7]
ЗЫ Если многоугольники выпуклые

Dennis I. Komarov (2008-08-01 12:29:00) [8]
пересечение двух различных граней одного многоугольника с гранями (гранью) другого при условии что многоугольники принадлежат одной плоскости даст: " пересекает ли маленький многоугольник границы большого.

Vlad Oshin (2008-08-01 09:58:00) [9]
регионы

KilkennyCat (2008-08-01 01:14:00) [10]

> KilkennyCat © (01.08.08 01:11) [9]

Не, тут не трансформация обекта нужна, а системы координат, чтобы внешний многоугольник нам стал казаться кругом.
жуть.

А в каком классе проходят пересечение векторов на плоскости?
спать пора.

KilkennyCat (2008-08-01 01:11:00) [11]
еще есть вариант. трансформируем внешний многоугольник до квадрата, или окружности. свойства трансформации, полученные при этом, применяем и к внутреннему многоугольнику. Не уверен, конечно, но вроде бы, система в целом останется неизменна. Проверить же выход за границы простого квадрата или круга - проще пареной репы.

KilkennyCat (2008-08-01 01:08:00) [12]
или просто проверить пересечение граней. каждую с каждой.

KilkennyCat (2008-08-01 01:07:00) [13]
Или закрасить один красным, а другой зеленым. наложить. проверить появление третьего цвета.

KilkennyCat (2008-08-01 01:05:00) [14]
Да даже если и вращать. Даже и если и впуклый. И даже если не знать математики, задачу решить несложно. Вот, например, неоптимальный, но очень простой метод: поскольку у нас пиксели все квадратные, то границу многоугольников легко описать матрицей. в первом многоугольнике это будут единички, во втором - двойки. Пустые места - нолики. проецируя одну матрицу на другую, легко определить появление тройки - суть пересечение.

Нат (2008-08-01 00:32:00) [15]
А вращать его можно?
Если вращать нельзя, то можно попробовать построить функцию ( вектора смещения центра одного многоуг-ка относительно другого ) = касание многоугольников.
Тогда останется только контролировать параметры вектора (направление и длина).
Можно поcтроить фазовую траекторию движения по границе.
Для аналитического решения надо найти аналитические уравнения, описывающие данные многоугольники
Для итеративного построения построить векторы из центра координат к вершинам обоих фигур. Далее последовательно сдвигать многоугольник вдоль каждого вектора до пересечения. Т.о. задачу можно попытаться свести к определению с какой стороны от границы (сторона одного мн-ка) находиться точка (вершина другого).
Дальше тонкости.

Интереснее, если меньший еще и вращается...

KilkennyCat (2008-08-01 00:20:00) [16]
заодно определиться с типом многоугольника, все углы выпуклые или есть впуклые?

Юрий Зотов (2008-08-01 00:06:00) [17]
> Newss (31.07.08 23:38) [2]

То нельзя, то можно... Вы уж определились бы...

Newss (2008-07-31 23:38:00) [18]
Нет, по условию его можно перемещать. Но можно ведь его передвинуть так, что он выйдет за границы большого. А мне это нежелательно.

Юрий Зотов (2008-07-31 23:24:00) [19]
Не пересекает по условию. Можно не проверять.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »