Ask Your Question

Detect concave using 4 points of a rectangle?

asked 2013-04-22 16:08:17 -0600

Papercut gravatar image


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

CvPoint[] points = new CvPoint[4]; points[0] = new CvPoint(10,10); points[1] = new CvPoint(10,20); points[2] = new CvPoint(13,13); points[3] = 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 flag offensive close merge delete

1 answer

Sort by ┬╗ oldest newest most voted

answered 2013-04-22 19:42:03 -0600

matt.hammer gravatar image

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

edit flag offensive delete link 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

please watch the _minus_ sign!

alexs gravatar imagealexs ( 2015-09-18 03:59:36 -0600 )edit

Question Tools


Asked: 2013-04-22 16:08:17 -0600

Seen: 1,776 times

Last updated: Apr 22 '13