4

enter image description here

Above image contains 4 points which user can drag any were within the image frame,I want algorithm(logic) where a user draw rect is valid rect or NOT.Rect should be valid SHAPE(trapezoid triangle,quadrilateral).What can be best method to find that rect is valid shape or not.

Below shapes are not valid enter image description here

enter image description here

Mukesh
  • 3,680
  • 1
  • 15
  • 32
  • What is the intention? This seems like an XY-problem to me. You are asking a very odd and very specific thing. WHY is the user drawing a rect? Is it to crop the image by any chance? – Fogmeister May 21 '15 at 10:41
  • 1
    OK, but what is a valid shape? Why is one shape valid and another shape not valid? – Fogmeister May 21 '15 at 10:43
  • I think a different approach would be better here. Is a right angle triangle valid? Or a square rotated 45 degrees? Or how about a quadrilateral with a concave angle? You might be better providing predefined shapes that can be moved and scaled. Then the user can pick triangle or trapezoid etc... and move it to the desired location. – Fogmeister May 21 '15 at 10:50
  • i have edited please check – Mukesh May 21 '15 at 10:56
  • Exactly, there are infinitely many more invalid shapes than there are valid shapes if you allow the user to move the four points independently. I would still go back to providing preset shape that they can place over the image. – Fogmeister May 21 '15 at 11:11

1 Answers1

1

You want to check if your shape is a quadrilateral, in particular a convex quadrilateral (look for concave and convex polygons). For the two problems that you showed, you can used two tests:

  1. For the first case you just need to check that no interior angle between two sides is higher than 180 degrees, i.e., that your polygon is convex. To do this, check this question in SO.

  2. I am not sure that checking for "convexitivity" solves the second case. You should try. If it doesn't, you need to check that the sum of the four interiror angles is 360 degrees (this holds true for all quadrilaterals). To get the angle between two segments you can convert them to vectors and use the dot product. The angle at vertex 2 would be:

v_{12} = ( x2 - x1 , y2 - y1 ) --> Vector from point 1 to point 2

v_{23} = ( x3 - x2 , y3 - y2 ) --> Vector from point 2 to point 3

Now calculate the dot product

v_{12} . v_{23} = (x3 - x2)(x2 - x1) + (y3 - y2)(y2 - y1)

The cosinus of the angle between segments 12 and 23 is the dot product divided by the modulus of each vector.

Community
  • 1
  • 1
rpsml
  • 1,486
  • 14
  • 21
  • can u xplain in code.I know this logic?I am not able to map in code.I got the first case.But not the second. double angle_ab = atan2(p1.y - p2.y, p1.x - p2.x); double angle_cb = atan2(p3.y - p2.y, p3.x - p2.x); double angle_abc = angle_ab - angle_cb; I am using the above code to calculate angle between points – Mukesh May 21 '15 at 12:00
  • @muku I added some more info on the answer. – rpsml May 21 '15 at 19:20
  • u also need to calculate the cross product .@rpsmi – Mukesh May 22 '15 at 05:13