Как определить, пересекаются ли два выпуклых многоугольника?
Я лично предпочитаю использовать этот способ:
if(!strpos($v,'ttp:'))$v='http://'.$v;
или
if(strpos(' '.$v,'http'))
, чтобы избежать положения «0», а затем всегда делает его числом больше, чем 0 приветствия
6 ответов
Вы можете использовать этот алгоритм столкновения :
Чтобы определить, пересекаются ли два выпуклых многоугольника (касаясь друг друга), мы можем использовать теорему о разделяющей оси. По существу:
- Если два выпуклых многоугольника не пересекаются, существует линия, которая проходит между ними.
- Такая линия существует, только если одна из сторон одного из многоугольников образует такую линию.
Первое утверждение легко. Поскольку оба многоугольника являются выпуклыми, вы сможете нарисовать линию с одним многоугольником на одной стороне и другим многоугольником на другой стороне, если они не пересекаются. Второй немного менее интуитивно понятен. Посмотрите на рисунок 1. Если самые близкие стороны многоугольников не параллельны друг другу, точка, где они находятся ближе всего друг к другу, является точкой, где угол одного многоугольника становится ближе к стороне другого многоугольника. Эта сторона тогда сформирует разделяющую ось между многоугольниками. Если стороны параллельны, они обе являются разделительными осями.
Так как же это конкретно помогает нам решить, пересекаются ли многоугольники A и B? Ну, мы просто переходим каждую сторону каждого многоугольника и проверяем, образует ли он разделяющую ось. Для этого мы будем использовать некоторую базовую векторную математику, чтобы раздвинуть все точки обоих многоугольников на линию, которая перпендикулярна потенциальной разделительной линии (см. Рисунок 2). Теперь вся задача удобно одномерна. Мы можем определить область, в которой лежат точки для каждого многоугольника, и эта линия является разделительной осью, если эти области не перекрываются.
Если после проверки каждой линии из обоих многоугольников не было найдено разделительной оси, она была Доказано, что полигоны пересекаются, и с этим нужно что-то делать.
если многоугольники всегда выпуклые, сначала вычислите угол линии, проведенной от центра к центру многоугольников. затем вы можете исключить необходимость проверки краевых сегментов в половине многоугольника (ов) на 180 градусов от другого многоугольника (ов).
Чтобы устранить ребра, начните с многоугольника слева. возьмите отрезок линии от центра многоугольника, который перпендикулярен отрезку линии от предыдущей маркировки, и коснется обеих сторон многоугольника. Назовите этот отрезок линии p с вершинами p1 и p2. Тогда для всех вершин, если координата x меньше p1.x и p2.x, эта вершина может попасть в «безопасное ведро».
Если этого не произойдет, вы должны проверить, что он находится в «сейфе».
Your test cases should work, since you're checking the case where the polygons don't intersect at all (completely outside or completely inside), as well as where there is any form of partial intersection (edges intersect always if there is overlap).
For testing, I would just make sure to test every potential combination. The one missing above from what I see is a single edge shared, but one poly contained in the other. I would also add tests for some more complex poly shapes, from tri -> many sided, just as a precaution.
Also, if you had a U shaped poly that completely surrounded the poly, but didn't overlap, I believe your case would handle that, but I would add that as a check, as well.
Поскольку altCognito уже дал вам решение, я укажу только на отличную книгу по вычислительной геометрии , которая может вас заинтересовать.
Вот идея:
Найти центральную точку каждого многоугольника
Найти две точки каждого полигона, ближайшего к центральной точке другого. Они будут смежными точками в выпуклых многоугольниках. Они определяют ближайшее ребро каждого многоугольника, назовем точки {A, B} и {Y, Z}
. Находим пересечение прямых AB и YZ. Если отрезки отрезков пересекаются (пересечение на AB лежит между A и B), ваши полигоны пересекаются. Если AB и XY параллельны, игнорируйте это условие, следующий шаг поймает проблему в ловушку.
Есть еще один случай, который вам нужно проверить, это когда многоугольники пересекаются достаточно сильно, чтобы AB и XY полностью проходили друг за другом и на самом деле не пересекаются. Чтобы уловить этот случай, вычислите перпендикулярные расстояния AB и XY до центральных точек каждого полигона. Если любая из центральных точек находится ближе к отрезку линии противоположного многоугольника, полигон сильно перекрывается.