CODEWITHSUNDEEP
c++mathgeometrycomputational-geometryraylib
Steven31st
Steven31st

Reputation: 47

How to find if four lines make a quadrilateral, either convex or concave?

How can I detect if any given four lines make a quadrilateral, be convex or concave, and if they make more than one quadrilateral, in c++?

For example, with this: this is a geogebra screenshot, showing four intersecting lines, that hides at least two quadrilaterals

There is this one: highlighted with blue, the first quadrilateral, a concave one

And this one: also highlighted with blue, the second quadrilateral, a convex one

I have read this and this, but my main issue is with detecting concave quadrilaterals, especially if I don't know whether the lines even make a closed shape.

I also tried doing (my own code, along with some classmates) this, but it detects that there nearly always is a quad, even if there isn't any

Upvotes: 1

Views: 120

Answers (2)

chux
chux

Reputation: 154173

Given any 3 successive points form an angle [-180 ... 180]

It is sufficient to test for a sign change. (with some considerations for numerical co-linear sides).

// Concept code
bool is_concave(unsigned n, const point p[n]) {
  if (n <= 3) return true;
  double first_angle = angle(p[0], p[1], p[2]);  // [-180 ... 180]
  for (unsigned i=3; i<n; i++) {
    double next_angle = angle(p[i-2], p[i-1], p[i]);
    if (sign(first_angle) != sign(next_angle)) {
      return false;
    }
  }
  return true;
}

Upvotes: 0

Dillon Davis
Dillon Davis

Reputation: 7750

First, the existence of a concave quadrilateral implies the existence of a convex quadrilateral inscribed within it. Your example demonstrates this, and it holds in general for the case of 4 lines.

To test if a convex quadrilateral exists, check two conditions:

  • No three lines intersect at the same point
  • No two lines are parallel

You can check if three lines intersect at a single point by computing the point of intersection for all 6 pairs of two lines, and then plugging the x/y values of that intersection into the other two lines to see if the point is also on those lines. If this condition fails, then there does not exist a quadrilateral, convex nor concave.

If that condition holds, you can then check that no two lines are parallel. If this condition holds, then there exists a concave quadrilateral somewhere in your plane. If it doesn't hold, there still may be a quadrilateral, you'll just need to do a few more checks.

Firstly, if the two parallel lines are in fact the same line, then you effectively only have 3 distinct lines so there's no quadrilateral. Secondly, if three lines are parallel, you also have no quadrilateral. Finally, if the other two, non-parallel, lines intersect between the two parallel lines, there's also no quadrilateral. Otherwise, there is a convex quadrilateral. To test this, just again compute the point of intersection, and then check whether this point is on the same "side" of both lines.

Now, what about concave quadrilaterals? In the case with parallel lines, there will not be any concave quadrilaterals. Otherwise, I believe if there's a convex quadrilateral, there will also be a concave quadrilateral to accompany it, which will share an corner with the convex quadrilateral. There cannot be two concave quadrilaterals at once either.

All together, this lets you count the total number of quadrilaterals in your plane.

Upvotes: 3

Related Questions