Пересечение фигур

← →
Newss (2008-07-31 23:08) [0]

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

← →
Юрий Зотов © (2008-07-31 23:24) [1]

Не пересекает по условию. Можно не проверять.

← →
Newss (2008-07-31 23:38) [2]

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

← →
Юрий Зотов © (2008-08-01 00:06) [3]

> Newss (31.07.08 23:38) [2]

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

← →
KilkennyCat © (2008-08-01 00:20) [4]

заодно определиться с типом многоугольника, все углы выпуклые или есть впуклые?

← →
Нат (2008-08-01 00:32) [5]

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

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

← →
KilkennyCat © (2008-08-01 01:05) [6]

Да даже если и вращать. Даже и если и впуклый. И даже если не знать математики, задачу решить несложно. Вот, например, неоптимальный, но очень простой метод: поскольку у нас пиксели все квадратные, то границу многоугольников легко описать матрицей. в первом многоугольнике это будут единички, во втором - двойки. Пустые места - нолики. проецируя одну матрицу на другую, легко определить появление тройки - суть пересечение.

← →
KilkennyCat © (2008-08-01 01:07) [7]

Или закрасить один красным, а другой зеленым. наложить. проверить появление третьего цвета.

← →
KilkennyCat © (2008-08-01 01:08) [8]

или просто проверить пересечение граней. каждую с каждой.

← →
KilkennyCat © (2008-08-01 01:11) [9]

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

← →
KilkennyCat © (2008-08-01 01:14) [10]

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

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

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

← →
Vlad Oshin © (2008-08-01 09:58) [11]

регионы

← →
Dennis I. Komarov © (2008-08-01 12:29) [12]

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

← →
Dennis I. Komarov © (2008-08-01 12:30) [13]

ЗЫ Если многоугольники выпуклые

CreatePolygonRgn
The CreatePolygonRgn function creates a polygonal region.

CombineRgn
- Return Values NULLREGION The region is empty.

← →
Нат (2008-08-01 13:21) [16]

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

Есть примитив - принадлежность точки многугольнику...
Получаем условие: (mi принадлежит M, i = 1..n) и (Mi не принадлежит m, i = 1..N)

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

ЗЗЫ - точка пересечения не должна быть вершиной

Задача не стоит выеденного яйца.

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

Пересечение фигур Найти похожие ветки