1
$\begingroup$

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 .

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Andrei
    Commented Mar 4, 2021 at 16:22
  • $\begingroup$ yup i know so i want one set of solution which returns $z_1,z_2,z_3,z_4$ $\endgroup$
    – p_k
    Commented Mar 4, 2021 at 16:23
  • $\begingroup$ Are there any restrictions? Certainly if $z_1=z_2=z_3=z_4$, then it's minimal. $\endgroup$
    – ndhanson3
    Commented Mar 4, 2021 at 16:58
  • $\begingroup$ @ndhanson3 any other solution beside all z is equal $\endgroup$
    – p_k
    Commented Mar 4, 2021 at 17:03

1 Answer 1

1
$\begingroup$

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]]
Graphics3D[Polygon[quad]]

NOTE

To obtain the minimum area use instead

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

enter image description here

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]]))
$\endgroup$
18
  • $\begingroup$ can i get this script in python , because i know python i can relate it there $\endgroup$
    – p_k
    Commented Mar 4, 2021 at 18:03
  • 1
    $\begingroup$ I'm not very familiar with Python but I will try to arrange a Python version asap. $\endgroup$
    – Cesareo
    Commented Mar 4, 2021 at 18:06
  • $\begingroup$ sure that will be a great help $\endgroup$
    – p_k
    Commented Mar 4, 2021 at 18:07
  • $\begingroup$ which norm have you used Euclidean distance L2 Norm ?? $\endgroup$
    – p_k
    Commented Mar 4, 2021 at 18:15
  • $\begingroup$ Euclidean distance. $\endgroup$
    – Cesareo
    Commented Mar 4, 2021 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .