3
$\begingroup$

How to determine geometric properties of four distinct points in a plane (x1,y1), (x2,y2), (x3,y3), (x4,y4) represented in the 2-D Cartesian coordinate system, whether these four points are on

  • a line,
  • a circle,
  • a rectangle,
  • a triangle.

To check points are on a line, we can check if two lines forming are colliniar or not..

(y1 - y2) * (x1 - x3) -  (y1 - y3) * (x1 - x2) = 0
(y2 - y3) * (x2 - x4) -  (y2 - y4) * (x2 - x3) = 0

How about circle, rectangle and triangle?

$\endgroup$
3
$\begingroup$

Line

You already have a solution for that.

Circle

A circle is described by an equation like this:

$$ 0 = (x-c_x)^2 + (y-c_y)^2 - r = x^2 + y^2 + (-2c_x)x + (-2c_y)y + (c_x^2+c_y^2-r) $$

Multiplying that equation by a real factor and renaming the coefficients, you obtain an equation of the following form:

$$\alpha(x^2+y^2) + \beta x + \gamma y + \delta=0$$

Three points in the plane define a circle. They define the parameters $\alpha$ through $\delta$ up to a common scale factor. Adding a fourth point, you have two options: Either that point lies on the circle, then it fits the same 1d space of parameters. Or it does not lie on the same circle, then the only way to satisfy all four equations is by choosing all four parameters equal to zero.

So you can check cocircularity by evaluating the determinant of this system of equations:

$$\begin{vmatrix} x_1^2+y_1^2 & x_1 & y_1 & 1 \\ x_2^2+y_2^2 & x_2 & y_2 & 1 \\ x_3^2+y_3^2 & x_3 & y_3 & 1 \\ x_4^2+y_4^2 & x_4 & y_4 & 1 \end{vmatrix}=0$$

If you write this out, you get something pretty bulky:

\begin{align*} x_{2}^{2} x_{3} y_{1} - x_{2} x_{3}^{2} y_{1} - x_{2}^{2} x_{4} y_{1} + x_{3}^{2} x_{4} y_{1} + x_{2} x_{4}^{2} y_{1} - x_{3} x_{4}^{2} y_{1} - x_{1}^{2} x_{3} y_{2} + x_{1} x_{3}^{2} y_{2} \\{}+ x_{1}^{2} x_{4} y_{2} - x_{3}^{2} x_{4} y_{2} - x_{1} x_{4}^{2} y_{2} + x_{3} x_{4}^{2} y_{2} - x_{3} y_{1}^{2} y_{2} + x_{4} y_{1}^{2} y_{2} + x_{3} y_{1} y_{2}^{2} - x_{4} y_{1} y_{2}^{2} \\{}+ x_{1}^{2} x_{2} y_{3} - x_{1} x_{2}^{2} y_{3} - x_{1}^{2} x_{4} y_{3} + x_{2}^{2} x_{4} y_{3} + x_{1} x_{4}^{2} y_{3} - x_{2} x_{4}^{2} y_{3} + x_{2} y_{1}^{2} y_{3} - x_{4} y_{1}^{2} y_{3} \\{}- x_{1} y_{2}^{2} y_{3} + x_{4} y_{2}^{2} y_{3} - x_{2} y_{1} y_{3}^{2} + x_{4} y_{1} y_{3}^{2} + x_{1} y_{2} y_{3}^{2} - x_{4} y_{2} y_{3}^{2} - x_{1}^{2} x_{2} y_{4} + x_{1} x_{2}^{2} y_{4} \\{}+ x_{1}^{2} x_{3} y_{4} - x_{2}^{2} x_{3} y_{4} - x_{1} x_{3}^{2} y_{4} + x_{2} x_{3}^{2} y_{4} - x_{2} y_{1}^{2} y_{4} + x_{3} y_{1}^{2} y_{4} + x_{1} y_{2}^{2} y_{4} - x_{3} y_{2}^{2} y_{4} \\{}- x_{1} y_{3}^{2} y_{4} + x_{2} y_{3}^{2} y_{4} + x_{2} y_{1} y_{4}^{2} - x_{3} y_{1} y_{4}^{2} - x_{1} y_{2} y_{4}^{2} + x_{3} y_{2} y_{4}^{2} + x_{1} y_{3} y_{4}^{2} - x_{2} y_{3} y_{4}^{2} &=0 \end{align*}

Note that four points on a line will also satisfy this equation, and the solution will have $\alpha=0$. If you don't want to include this case, check for lines first.

Rectangle

Two vectors are orthogonal if their dot product is zero. Do this for three pairs of edge vectors and you have checked three corner angles. If they are all right angles, then so is the fourth and you have the corners of a rectangle.

For points on the edge of a rectangle: you will always find a rectangle which has the four points as elements of its edges as long as the points are in convex position. Start by connecting two points with a line, then extend that to the smallest bounding rectangle of the orientation indicated by that line. There are examples where the first choice of line would lead to one of the other points inside the resulting rectangle, but as far as my mental experiments go (although this is no proof), you can always find a different starting edge such that things work out.

Triangle

For four points to be the corners of a triangle, two of them have to be the same.

You will always find a triangle which has the four points on its edges as long as the points are in convex position. Simply take the convex hull, which is a quadrilateral in this case, and extend two of its edges to form a triangle.

$\endgroup$
  • $\begingroup$ Thank you very much :) the concept of triangle is not clear for me. How is it possible to find a triangle with all the four points on its edge? $\endgroup$ – Jasim Muhammed Dec 9 '13 at 7:57
  • $\begingroup$ @jasimmk: I have added details for these point-on-edge cases. $\endgroup$ – MvG Dec 9 '13 at 8:03
  • $\begingroup$ do you know the geometrical meaning of this 4x4 determinant if there is any (e.g. some area or length)? $\endgroup$ – Azat Ibrakov Sep 30 at 18:42
  • $\begingroup$ @Azat I know if no metric interpretation of that determinant. Note that if you scale all coordinates by a common factor, the determinant will scale by the fourth power of that factor. So at best you could expect it to be the square of some area. Except that the value of the determinant will be negative depending on how the points deviate from being cocircular. Square of an imaginary area? I doubt that makes a lot of sense. $\endgroup$ – MvG Oct 1 at 6:18
1
$\begingroup$

enter image description here

If AB.CD+BC.DA=AC.BD satisfies, four points makes Cyclic Quadrilateral and this prooves that they are on a circle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.