# Detect concave using 4 points of a rectangle?

Hi,

I have 4 points of a rectangle, and I am trying to check if it has a concave in it.

CvPoint[] points = new CvPoint; points = new CvPoint(10,10); points = new CvPoint(10,20); points = new CvPoint(13,13); points = new CvPoint(20,10);

There are several ways I can think of but none of them is useful and smart in terms of speed and memory. Anyone knows the best way to check if it has a concave?

edit retag close merge delete

Sort by » oldest newest most voted

First, no rectangles are concave.

A quadrilateral is concave if and only if it has one interior angle over 180 degrees.

How smart and fast do you need?

Off the top of my head, you could find vectors for all 4 sides (not corners)* and take the outer product of each pair of adjacent sides (Outer Product is something like f([x1,y1],[x2,y2]) = x1y2+x2y1,* watch your order and direction, use the right hand rule). If the product is negative for one adjacent pair, that angle is over 180 degrees, you've got a concave quad. (if all the outer products are positive, the quad is convex) I just learned this technique myself a few days ago, so please Google for more detail first.

** subtract adjacent corners, in order CCW around the quad to get the side vectors

** I think this formula is actually the 3-D cross product in the plane z=0, by checking the sign you're seeing which direction the 3-D normal is pointing

more

there are two vector products, the one is the dot product, the other is the cross product. as you are talking about signed area values you probably think about the cross product. when inserting two 2D points into the 3D formula (the normals vector and direction is the measure for the area) then a formula like this is the result:

f([x1,y1],[x2,y2]) = x1 y2 - x2 y1

Official site

GitHub

Wiki

Documentation