Finding diagonals of convex quadrilateral How to find diagonals of any convex quadrilateral?
I have only Points which are corners P1(x1,y1), P2(x2,y2), P3(x3,y3), P4(x4,y4).
How can I distinguish diagonals from sides?
I couldn't find an answer anywhere on the web.
 A: For a well-known implementation in 2D of the general polygon orientation, see:
[2D Convex Hulls and Extreme Points]

CGAL provides implementations of several classical algorithms for computing the counterclockwise sequence of extreme points for a set of points in two dimensions (i.e., the counterclockwise sequence of points on the convex hull).

A tailored approach to the convex hull/cyclic orientation of a quadrilateral might be the following.

Pick an interior point $Q=(\overline{x},\overline{y})$ of the convex quadrilateral by averaging the four corner points $P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3),P_4=(x_4,y_4)$.  Sort the vectors from $Q$ to each $P_i$ by angle of elevation/depression.  The endpoints of diagonals will occupy alternating entries of this sorted list.

It is possible to avoid explicit use of trigonometry in this sorting by pigeonholing the vectors $P_i - Q$ into quadrants (based on signs of the coordinate components) and sorting within a quadrant based on "steepness" of the slopes of the vectors.
Another computational approach would be to solve the segment intersection problem for $\overline{P_1 P_2}$ and $\overline{P_3 P_4}$.  If they intersect (in a point belonging to both line segments), then these are the diagonals we seek.  If they don't intersect, then these are a pair of sides.  Unfortunately we may need to repeat the test (once) if the latter occurs, in order to determine which pairs of points form the diagonals.
A minimal amount of computation?
Given three points $A=(a_x,a_y),B=(b_x,b_y),C=(c_x,c_y)$, we can determine if the triangular loop $A\to B\to C\to A$ goes counterclockwise (or not) from the sign of the $3\times 3$ determinant:
$$ \left| \begin{array}{ccc}
 a_x & a_y & 1 \\
 b_x & b_y & 1 \\
 c_x & c_y & 1 \end{array} \right| = (b_x-a_x)(c_y-a_y)-(c_x-a_x)(b_y-a_y) $$
This determinant is positive if the loop goes counterclockwise, negative if it goes clockwise, and zero exactly when the three points are co-linear.
If $\overline{P_1P_2}$ is a diagonal, then the loops $P_1P_2P_3$ and $P_1P_2P_4$ will have opposite orientations, but if $\overline{P_1P_2}$ is a side, then they will have the same orientation.
Since $P_1P_2P_3$ gives the same orientation if we consider it as $P_2P_3P_1$, it suffices to check at most $3$ triangular loop orientations.  If loops $P_1P_2P_3$ and $P_1P_2P_4$ have the same orientation, we only need to check the orientation of $P_2P_3P_4$.  If it has opposite orientation to $P_1P_2P_3$, then $\overline{P_2P_3}$ is a diagonal; otherwise, if the orientation is again the same, then $\overline{P_2P_4}$ is a diagonal.
