Найти точку соприкосновения двух выпуклых полигонов

PlutDem · 29.12.2014, 15:59

Здравствуйте, есть два выпуклых полигона, они касаются друг друга, но не пересекаются (точка одного лежит на стороне или отрезке другого) Можно ли вычислить точку их соприкосновения?

undefined · 29.12.2014, 19:32

есть миллион способов.
навскидку - считать площади треугольников, образованных вершинами одного полигона и 2-мя вершинами второго, для вершин, лежащих на стороне, эта площадь будет=0.

П.С. площадь через координаты считается через векторное произведение

PlutDem · 29.12.2014, 20:32

А нет ли более быстрого способа? Или хотя бы возможности исключить некоторые точки при просчете по вашему методу?

undefined · 29.12.2014, 20:48

боюсь,что, вершины полюбому надо все обходить.А почему такие требования к скорости? надо много полигонов проверять или у полигонов много вершин? Да и этот метод каких-то супер ресурсоемких операций не требует,несколько сложений и 2-3 умножения на каждый треугольник.Вообще о каких объемах вычислений идет речь?Какова размерность задачи ,так сказать? Насчет скорости - думаю сильно быстрее не получится