Дано: даны несколько многоугольников даны координаты всех вершин нескольких многоугольников возможны ещё и круги Определить: столкновения многоугольников(или кругов или многоугольников и кругов) (варианты:нет,2 стороны,2 вершины,сторона и вершина,внутренняя(тело внутри тела)) Никак алгоритм вычисления не могу придумать. Желательно на более понятном языке программирования(C++,Basic), что-бы легко было уловить смысл.
Чистейшей воды планиметрия. Прежде всего нужно максимально кокретизировать задачу. Вот навскидку мне такой вопрос непонятен. Пусть имеются 2 многоугольника. Координаты вершин одного: (2;2),(2;13),(7;2),(7,13) Координаты вершин другого (5;4),(5;12),(8;8),(13;12),(13;4) Ответ будет имеется столковение многоугольников. Количество столкновений 2. Тип столкновения N1 тело внутри тела. Тип столкновения N2 тело внутри тела или имеется столковение многоугольников. Типы столкновений: тело внутри тела. Правильны оба ответа. Но какой нужен, автор?
amvoz У каждого многоугольника свои стороны не сталкиваются. ((2;2),(2;13),(7;2),(7,13)—не верно: вот так—(2;2),(7;2),(7,13),(2;13)) Дано: Координаты вершин одного: (2;2),(7;2),(7,13),(2;13) Координаты вершин другого: (5;4),(5;12),(8;9),(13;12),(13;4) Ответ: Вершины не сталкиваются Стороны сталкиваются: сторона 2 прямоугольника (5;4),(5;12) внутри многоугольника (2;2),(7;2),(7,13),(2;13) сторона 2 прямоугольника (13;4),(5;4) сталкивается со стороной 1 прямоугольника (7;2),(7,13) в точке (7,4) сторона 2 прямоугольника (5;12),(8;9) сталкивается со стороной 1 прямоугольника (7;2),(7,13) в точке (7,10) И ещё хотелось-бы узнать более быстрый способ узнавания о столкновении квадратов,прямоугольников,треугольников... (учитывая что эти фугуры будут построееню не ровно по осям x и y, а могут быть повёрнуты) (x,y,width,height,angle)
Далее: условия задачи даны для многоуголоьников определённых как: 1) многоугольник- фигура, стостоящая из n количества точек, соединённых между собой в последовательности называния точек 2) многоугольник, фигура, стостоящая из n количества точек, соединённых между собой в последовательности называния точек. Никакие 2 точки не совпадают друг с другом. Ну и так далее. В общем, надо дать чёткое определение многоугольника для решаемой задачи. Поверь, иначе не решишь. Я попроще писал программу- определить взаиморасположение 2-отрезков. Все взаиморасположения. Пересекаются, не пересекаются, совпадают и так далее. Пока чётко не определил, для чего я решаю задачу (какие фигуры являются отрезками для даной задачи), путался долго. А у тебя задача много труднее.
есть такая теорема о о разделяющих осях (ТРО): если мы можем найти такую ось, проекции на которую двух выпуклых фигур не накладываются, значит эти фигуры не пересекаются... посмотри вот здесь, тут вроде понятно описано: http://noregret.org/tutor/n/collision/#2
Пробежался глазами. Я бы так делал: отвечал на вопрос: пересекаются ли какие-нибудь любые 2 стороны многоуольников (какая-нибудь стороона многоугольника N1 и какая-нибудь сторона многоугольника N2 ). Если пересекаются, значит, есть пересечение многоугольников. Нет- нет.
ну понимаешь, очень часто гораздо проще и эффективнее найти решение в "дарах математики", чем самому изобретать велосипед... там всетки гораздо более "общие" алгоритмы, а в своем "велосипеде" можно какую-нить мелочь не учесть и мучаться с ней потом долго... к тому же, со сторонами многоугольника возится на мой взгляд сложнее, чем с проекциями на оси, не говоря уже о том, что если сторона фигуры не прямая линия, а какой-то отрезок окружности, или того хуже?
посмотри в статье, там вроде понятно все описано... если фигуры простые (всмысле точки соединены прямыми линиями, н-угольники имеется ввиду), то можно посмотреть пересечения проекций на оси координат, если у двух сторон (одной стороны первой и одной стороны второй фигуры) имеются пересечения проекций на обеих осях, то они сталкиваются... мне кажется, это способ самым простым способом вычисления... может есть проще и лучше, но я его не знаю... когда фигура не простая (между двумя точками не прямая линия), то там надо добавлять ещё оси в пространстве и смотреть пересечение проекций на них тоже... кстати первая часть действительно только для "выпуклых" фигур... то есть если многоугольник "вогнутый" то тож надо дополнительные оси и проэкции считать... ваще сложная тема канеш...
Zhelezka А проверить, попадает ли каждая вершина многоугольника внутрь другого многоугольника? (проверить для обоих?, хз). Может быть на этой основе что-нибудь соорудить?
