Как реализовать проверку четырехугольника на вырожденность в Java?

Question

[Biaci_Anj]

Есть Point, каждый point имеет x и y. Первая мысль - проверить, лежат ли точки на одной прямой, но возникают сложности, не совсем понимаю, как это сделать.

public Quadrilateral(Point a, Point b, Point c, Point d) {
// Надо проверить на вырожденность 
}

Вот метод для поиска пресечений отрезков.

private Point intersectPoint(Point start1, Point end1, Point start2, Point end2) {
        double x1 = start1.getX();
        double y1 = start1.getY();
        double x2 = end1.getX();
        double y2 = end1.getY();

        double x3 = start2.getX();
        double y3 = start2.getY();
        double x4 = end2.getX();
        double y4 = end2.getY();

        double t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
        double u = ((x1 - x3) * (y1 - y2) - (y1 - y3) * (x1 - x2)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
        double x = x1 + t * (x2 - x1);
        double y = y1 + t * (y2 - y1);
        if (0.0 <= t && t <= 1.0 && 0.0 <= u && u <= 1.0) {
            return new Point(x, y);
        }
        return null;

    }

Буду рад помощи

Answer 1

[Алексей Черемисин]

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

Arraylist points = new Arraylist();
points.add(p1);
..
points.add(p2);

Iterator<String> iter = points.iterator();
while(iter.hasNext()){
 Point p = iter.next());
 iter.remove();
 if(points.contains(p)) return true; // здесь определяем, что точка равна еще какой-то точке.
}

Answer 2

[Сергей Водаков]

Чтобы определить, лежат ли четыре точки на одной прямой, нужно проверить, совпадают ли прямые, проведенные через каждую пару точек. Подробности по ссылке:
mathprofi.ru/zadachi_s_pryamoi_na_ploskosti.html

Answer 3

[Руслан .]

Четырехугольник вырожденный, если его площадь равна нулю.
Для четырехугольника это будет выполняться если все вершины лежат на одной прямой.

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

Например так:
vAB.x=b.X-a.X
vAB.y=b.Y-a.Y

vAC.x=c.X-a.X
vAC.y=c.Y-a.Y

vAD.x=d.X-a.X
vAD.y=d.Y-a.Y

Теперь находим скалярное произведение векторов vAB*vAС и vAB*vAD, если оба равны единице, то четырехугольник вырожденный.

Найти скалярное произведение от координат векторов можно так:
s(v1, v2) = (v1.x*v2.x+v1.y*v2.y)/(sqrt(v1.x*v1.x+v1.y*v1.y)*sqrt(v2.x*v2.x+v2.y*v2.y))

Либо второй вариант, можно пойти от уравнения прямой:
(b.x-a.x)/(b.y-a.y)=(c.x-a.x)/(c.y-a.y)=(d.x-a.x)/(d.y-a.y)=t
и тут, чтобы уйти от деления можно так переписать уравнение:
(b.x-a.x)*(c.y-a.y) =(c.x-a.x)*(b.y-a.y)
(b.x-a.x)*(d.y-a.y) =(d.x-a.x)*(b.y-a.y)
Если оба равенства выполняются, то четырехугольник вырожденный