Detect concave using 4 points of a rectangle?

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

Papercut
71 ●3 ●6

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[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?

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

matt.hammer
336 ●1 ●5 ●13

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

Comments

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 ( 2015-09-18 03:59:36 -0600 )edit

add a comment

Detect concave using 4 points of a rectangle?

1 answer

Comments

Links

Question Tools

Stats

Related questions

Detect concave using 4 points of a rectangle? edit

1 answer

Comments

Links

Question Tools

Stats

Related questions

Detect concave using 4 points of a rectangle?