Найти, если 4 точки образуют четырехугольник - PullRequest
4 голосов
/ 01 марта 2012

Может кто-нибудь показать мне алгоритм, чтобы написать функцию, которая возвращает true, если 4 точки образуют четырехугольник, и false в противном случае? Очки не приходят ни с каким заказом.

Я попытался проверить все перестановки 4-х точек и посмотреть, есть ли 3 точки, образующие прямую линию. Если есть 3 точки, которые образуют прямую линию, то это не четырехугольник. Но потом я понимаю, что нет способа рассказать о заказе. А потом я боролся за несколько часов размышлений и поисков без результата: (

Я прочитал эти вопросы:

  1. найти, если 4 точки на плоскости образуют прямоугольник?
  2. Определение порядка расположения вершин для формирования четырехугольника

Но все равно не нашли решения. В случае 1 он не может обнаружить другой вид четырехугольника, а в 2 он предполагает, что точки уже являются четырехугольными. Есть ли другой способ узнать, составляют ли 4 точки четырехугольник?

Спасибо, раньше.

РЕДАКТИРОВАТЬ ДЛЯ УТОЧНЕНИЯ:

Я определяю четырехугольник как простой четырехугольник, в основном все фигуры, показанные на этом рисунке: Quadirateral

за исключением формы с "четырехугольным" и "сложным" заголовком.

Что касается проблем с подходом «проверка коллинеарных триплетов», я попытался проверить вертикальные, горизонтальные и диагональные линии примерно так:

def is_linear_line(pt1, pt2, pt3):
    return (pt1[x] == pt2[x] == pt3[x] ||
            pt1[y] == pt2[y] == pt3[y] ||
            slope(pt1, pt2) == slope(pt2, pt3))

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

Ответы [ 5 ]

1 голос
/ 15 марта 2013

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

Я сделал это в target-c https://github.com/hfossli/AGGeometryKit/

extern BOOL AGQuadIsConvex(AGQuad q)
{
    BOOL isConvex = AGLineIntersection(AGLineMake(q.bl, q.tr), AGLineMake(q.br, q.tl), NULL);
    return isConvex;
}

BOOL AGLineIntersection(AGLine l1, AGLine l2, AGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    AGPoint p = l1.start;
    AGPoint q = l2.start;
    AGPoint r = AGPointSubtract(l1.end, l1.start);
    AGPoint s = AGPointSubtract(l2.end, l2.start);

    double s_r_crossProduct = AGPointCrossProduct(r, s);
    double t = AGPointCrossProduct(AGPointSubtract(q, p), s) / s_r_crossProduct;
    double u = AGPointCrossProduct(AGPointSubtract(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = AGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            AGPoint i = AGPointAdd(p, AGPointMultiply(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}
1 голос
/ 01 марта 2012

Проверка на наличие коллинеарных триплетов (как и вы) исключит случаи, когда четыре точки образуют треугольники или прямые.

Чтобы исключить также сложный четырехугольник (с пересекающимися краями):

AЧетырехугольник, образованный точками A, B, C и D, является сложным, если пересечение AB и CD (если есть) лежит между точками A и B, и то же самое относится к BC и DA.

1 голос
/ 01 марта 2012

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

0 голосов
/ 01 марта 2012

Пусть A, B, C и D - четыре точки.Вы должны предположить, что ребрами являются AB, BC, CD и DA.Если вы не можете сделать это предположение, четыре точки всегда образуют четырехугольник.

if (A-B intersects C-D) return false
if (B-C intersects A-D) return false
return true
0 голосов
/ 01 марта 2012

У вас есть больше входов, чем 4 балла?потому что если 4 теста пройдут успешно, они всегда могут образовать 3 разных четырехугольника, иногда из разных семейств.Например, возьмите квадрат, добавьте 2 диагонали и уберите сторону.

Таким образом, имея только 4 точки в качестве входных данных, вы не сможете добиться большего успеха, чем уже делаете.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...