@Leotor

Всех приветствую. У меня возникла такая проблема, мне необходимо нарисованный полигон проверить на наличие пересечений с расставленными на поле другими объектами (прямоугольниками). Т.е. это выглядит примерно так, на PictureBox в разном порядке расположенны простейшие геометрически фигуры, которые имеют свои имена, далее поверх рисуются два Polygon-а, которые нужно проверить на пересечение и вывод потом в список какие оъекты были перекрыты, Polygon - ом. Немогу найти какое-нибудь более или менее достойное решение!
Подскажите пожалуйста, как можно это организовать или где можно по этому вопросу почитать.

0

@asd321

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

1

@Unril

Советую на эту тему прочитать тут: Пересечение: Два выпуклых многоугольника.
Если лень разбираться, то можно просто каждое ребро одного полигона проверять на пересечение со всеми ребрами другого полигона.

1

@Leotor

Это может и не плохой способ, но проблема в том что таких отрезков может быть милион, а то и больше не удобно! Может есть какой-нибудь способ сравнивать объекты целиком, ну или разбить их на более мелкие и сравнивать массивы объектов.

0

@asd321

более короткого способа нету, этот самый оптимальный, вы же не все проверяете отрезки а только до того момента пока одна из пар не персечеться, алгоримт для большого количества можно сократить методом "золотого сечения" не видел чтоб этот алгоритм применялся для подобных задач но в моей голове это выглядит так, берем делим полигон на 4 примерно равные части, составляющтие которых отрезки, если какой т оотрезок перескает отрезок другого многоугольника который тоже разделен на 4 отрезка то дальше мы вясняем какой именно подотрезок пересеккся с другим подотрезко, постепенно разбивая подотрезки на другие подотрезки допустим по 2, так как в итоге может оказаться чт оони не пересекаются, точно также при условии чт они один из первых четырех отрезко не пересекается с соотвествующими 4 отрезкаим другого много гульника- разбиваем многоугольник уже на 16 32 и тд отрезко дял фломрирвоания более четкой фигуры контура в конце соотвествующей искомой фигуре....... как то так по омему неплохо)

0

@Leotor

О спасибо, про выпуклые многоугольники, вроде то что надо, жаль что не для C#, но не беда!
Но если, кто-то еще, какие-нибудь способы подскажет буду благодарен!

0

@asd321

вообще для полигонов вси шарпе есть готовая функция наличия пересечения

1

@Leotor

asd321, Спасибо! Может эта функция даст мне больший результат и быстрей! Мне нужно толко два полигона проверить с десятком мелких полигонов на пересечение.

0

@Koran

Leotor, если ваш математический аппарат не хромает и полигон довольно хитрый, то на Хабре есть статья на эту тему

2

@Leotor

Спасибо, Koran. Я эту статью видел, неплохая статья немного мудрено. Там на одну точку проверка, а если точек будет тысячи, то тогда как? Вот пытаюсь найт способ проще и быстрей! Сравнение нескольких полигонов это самы, наверное, удобный способ, т.к. у меня несколько десятков маленьких полигонов и два основных.
P.S. Как реализую этот вопрос обязательно выложу код, а пока я еще в поиске лучшего варианта.

0

@atomohod

Добрый день!
Есть Теория R-функций. Мне кажеться это наиболее достойное решение. Суть его в том, что имея уравнения всех полигонов, или нужных вам, вы с помощью R-функции можете получить новую функцию, которая у вас будет описывать пересечение, объеденение или отрицание примитивов.

Вот пример:

1. У вас есть круг, уравнение которого в двумерном пространстве имеет вид: f1 = R*R-x*x-y*y >= 0
2. У вас есть плоскость, уравнение которой f2 = x >= 0

Вам нужно найти, пересечение (коньюнкцию).

Составляете такую формулу: f1&f2 = f1 + f2 - sqrt(f1*f1 + f2*f2)

В результате получаете: f3 = f1&f2 = R*R-x*x-y*y + x - sqrt((R*R-x*x-y*y)*(R*R-x*x-y*y) + x*x)

И теперь, если эта функция хотя бы в одной точке больше нуля, то фигуры накладываются.

Подробнее еще можно здесь.

	Комментарий модератора
	На форуме есть редактор формул.

1

@Unril

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

1