# Optimization : Solve $4$ unknowns using $4$ equations

Suppose we have 4 points say A($$x_1,y_1,z_1$$), B($$x_2,y_2,z_2$$),C($$x_3,y_3,z_3$$), D($$x_4,y_4,z_4$$). Where $$x_1,x_2,x_3,x_4,y_1,y_2,y_3,y_4$$ are known points and rest $$z_1,z_2,z_3,z_4$$ are unknown points .
$$4$$ points will make a rectangle we want to find the corresponding Z - Coordinate using optimization .

We can make 4 equations as

1. $$AD^2 = AB^2$$
$$(z_4- z_1)^2 - (z_3 - z_2)^2 = (x_3 - x_2)^2 + (y_3 - y_2)^2 - (x_4 - x_1)^2 - (y_4 - y_1)^2$$

2. $$AB^2 = CD^2$$
$$(z_2- z_1)^2 - (z_3 - z_4)^2 = (x_3 - x_4)^2 + (y_3 - y_4)^2 - (x_2 - x_1)^2 - (y_2 - y_1)^2$$

3. (AB perpendicular to AD) $$(z_2- z_1) (z_4 - z_1) = -[(x_2 - x_1)(x_4 - x_1) + (y_2 - y_1)(y_4 - y_1)]$$

4. (BC perpendicular to CD) $$(z_2- z_3) (z_4 - z_3) = -[(x_2 - x_3)(x_4 - x_3) + (y_2 - y_3)(y_4 - y_3)]$$

Objective equation can be to minimize the area of rectangle i.e. $$Minimize (AB.AD)$$ $$i.e (Length* breadth)$$

How to solve this optimization so that we can we find other $$4$$ z-coordinate (i.e. $$z_1, z_2, z_3, z_4$$) corresponding to other 4 point .

• You can't. There is no unique solution. Suppose you find one. Notice what happens if you change all $z$ coordinates by the same amount $z_0$. Commented Mar 4, 2021 at 16:22
• yup i know so i want one set of solution which returns $z_1,z_2,z_3,z_4$
– p_k
Commented Mar 4, 2021 at 16:23
• Are there any restrictions? Certainly if $z_1=z_2=z_3=z_4$, then it's minimal. Commented Mar 4, 2021 at 16:58
• @ndhanson3 any other solution beside all z is equal
– p_k
Commented Mar 4, 2021 at 17:03

Given four points $$p_1,p_2,p_3,p_4$$ if they pertain to a rectangle then they are contained into the same plane $$\pi$$. Also the coordinates $$x,y$$ in each point, represent the $$XY$$ plane projection which should be a parallelogram. Assuming this projection is not a line (degenerate case) from this projection we can select a sequence to form a rectangle. From here we assume that the sequence $$p_1\to p_2\to p_3\to p_4\to p_1$$ gives us a rectangle. Curiously, only three of $$z_1,z_2,z_3,z_4$$ are independent so we assume $$z_4 = z_1+z_3-2z_2$$. If the objective is to determine the minimum perimeter rectangle then the optimization problem

$$\min_{z_i}|p_1-p_2|+|p_2-p_3|+|p_3-p_4|+|p_4-p_1| \ \ \ \text{s. t.} \ \ \cases{(p_1-p_2)\cdot(p_2-p_3)=0\\ (p_2-p_3)\cdot(p_4-p_3)=0\\ (p_4-p_3)\cdot(p_4-p_1)=0 }$$

comes with the solution.

Follows a MATHEMATICA script to accomplish with the calculations

p1 = {0, 0, z1};
p2 = {1, 2, z2};
p3 = {5, 3, z3};
p4 = {4, 1, z1+z3-2z2};
obj = Norm[p2 - p1] + Norm[p3 - p2] + Norm[p4 - p3] + Norm[p1 - p4]
sol = NMinimize[{obj, (p1 - p2).(p2 - p3) == 0, (p2 - p3).(p4 - p3) == 0, (p3 - p4).(p4 - p1) == 0}, {z1, z2, z3}]
quad = {p1, p2, p3, p4} /. sol[[2]]


NOTE

To obtain the minimum area use instead

obj = Norm[p2 - p1] Norm[p3 - p2]


In python a possible solution script could be

import numpy as np
import math
from scipy.optimize import minimize

x0 = [-1,1,-3]

def dif(x,y):
z = np.subtract(x,y)
return z

def obj(z):
p1 = [0,0,z[0]]
p2 = [1,2,z[1]]
p3 = [5,3,z[2]]
obj = math.sqrt(np.dot(dif(p1,p2),dif(p1,p2)))*math.sqrt(np.dot(dif(p2,p3), dif(p2,p3)))
return obj

def restr1(z):
p1 = [0,0,z[0]]
p2 = [1,2,z[1]]
p3 = [5,3,z[2]]
return np.dot(dif(p1,p2), dif(p2,p3))

def restr2(z):
p2 = [1,2,z[1]]
p3 = [5,3,z[2]]
p4 = [4,1,z[0]+z[2]-2*z[1]]
return np.dot(dif(p2,p3),dif(p4,p3))

def restr3(z):
p1 = [0,0,z[0]]
p3 = [5,3,z[2]]
p4 = [4,1,z[0]+z[2]-2*z[1]]
return  np.dot(dif(p4,p3), dif(p4,p1))

cons = ({'type': 'eq', 'fun': restr1},
{'type': 'eq', 'fun': restr2},
{'type': 'eq', 'fun': restr3})

res = minimize(obj,x0,constraints=cons)
print (res.fun)
print(res.x)

# Those prints show the residual form zero, to each
# restriction

print(restr1(list(res.x)))
print(restr2(list(res.x)))
print(restr3(list(res.x)))

def plane(p):
p1 = [0,0,res.x[0]]
p2 = [1,2,res.x[1]]
p3 = [5,3,res.x[2]]
n = list(np.cross(dif(p2,p1),dif(p3,p2)))
residue = np.dot(n,dif(p,p1))
return residue

# The following prints show the residual from zero
# at each vertex regarding the plane containing the rectangle

print(plane([0,0,res.x[0]]))
print(plane([1,2,res.x[1]]))
print(plane([5,3,res.x[2]]))
print(plane([4,1,res.x[0]+res.x[2]-2*res.x[1]]))

• can i get this script in python , because i know python i can relate it there
– p_k
Commented Mar 4, 2021 at 18:03
• I'm not very familiar with Python but I will try to arrange a Python version asap. Commented Mar 4, 2021 at 18:06
• sure that will be a great help
– p_k
Commented Mar 4, 2021 at 18:07
• which norm have you used Euclidean distance L2 Norm ??
– p_k
Commented Mar 4, 2021 at 18:15
• Euclidean distance. Commented Mar 4, 2021 at 18:17