# Optimize a search in 3D

I asked this first on stackoverflow and someone told me it was more appropriate to ask here, so I've copied it over:

I had some trouble trying to decide the best way to phrase this question so I apologize if it's a duplicate and I just missed it. I'm trying to optimize code meant to test if a collection of points are arranged in a rectangular prism. One of the only things I know going in is the first point and that object is aligned with the XYZ grid. IE a point must lay exactly +X or -X from the first point.

This is what I've come up with:

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
public class Program
{
public struct possition {
public float X,Y,Z;
public void assign(float a,float b, float c){
this.X = a;
this.Y = b;
this.Z = c;
}
public void assign(possition that){
this.X = that.X;
this.Y = that.Y;
this.Z = that.Z;
}
public possition (possition that){
this.X = that.X;
this.Y = that.Y;
this.Z = that.Z;
}
public possition (float a,float b, float c){
this.X = a;
this.Y = b;
this.Z = c;
}
public static bool operator ==(possition Pos1, possition Pos2){
if (Pos1.X == Pos2.X && Pos1.Y == Pos2.Y && Pos1.Z == Pos2.Z){
return true;
}
else {return false;}
}
public static bool operator !=(possition Pos1, possition Pos2){
if (Pos1.X != Pos2.X && Pos1.Y != Pos2.Y && Pos1.Z != Pos2.Z){
return true;
}
else {return false;}
}
}
public struct box {
public possition boundMin;
public possition boundMax;
public bool NotNull;

public box (possition Min, possition Max, bool NULL){
this.boundMin = Min;
this.boundMax = Max;
this.NotNull = NULL;
}
}
public static bool Occupied(possition checkPos){//this is function here entirelly for testing and demonstration Occupied is an outside function that is unimportant to the question
possition Fake1 = new possition(0.0f,0.0f,10.0f);
possition Fake2 = new possition(0.0f,10.0f,0.0f);
possition Fake3 = new possition(10.0f,0.0f,0.0f);
possition Fake4 = new possition(10.0f,0.0f,10.0f);
possition Fake5 = new possition(0.0f,10.0f,10.0f);
possition Fake6 = new possition(10.0f,10.0f,0.0f);
possition Fake7 = new possition(10.0f,10.0f,10.0f);

if (checkPos == Fake1 || checkPos == Fake2 || checkPos == Fake3 || checkPos == Fake4 || checkPos == Fake5 || checkPos == Fake6 || checkPos == Fake7) {
return true;
}
else {return false;}
}
public static box getBoundingBox(possition cornerOrigin){
cornerOrigin.assign(0.0f,0.0f,0.0f); //this won't always be set to the origin of the cordinate grid, but it's easier for this example to define it as a constant
possition scanTarget = new possition(cornerOrigin); //just a holder variable for working with the data in cornerOrigin.
possition xy = new possition();
possition yz = new possition();
possition xz = new possition();
possition xyz = new possition();

float y=0.0f,x=0.0f,z=0.0f, xMax, yMax, zMax, xMin, yMin, zMin;

//these along with the cornerOrigin define the four main corners
bool Success = false;
for (int I=0; I<=1; I++){
for (int J=1; J<=399; J++){
scanTarget.Y = J*(int)(Math.Pow(-1.0,I));//Changes the direction searched if I=0 then J>0, if I=1 then J<0
if (Occupied(scanTarget)){
Success = true;
y=scanTarget.Y;
break;
}
}
if(Success){break;}
}
scanTarget.assign(cornerOrigin);
if(Success){
Success = false;
for (int I=0; I<=1; I++){
for (int J=1; J<=399; J++){
scanTarget.X = J*(int)(Math.Pow(-1.0,I));
if (Occupied(scanTarget)){
Success = true;
x=scanTarget.X;
break;
}
}
if(Success){break;}
}
}
scanTarget.assign(cornerOrigin);
if(Success){
Success = false;
for (int I=0; I<=1; I++){
for (int J=1; J<=399; J++){
scanTarget.Z = J*(int)(Math.Pow(-1.0,I));
if (Occupied(scanTarget)){
Success = true;
z=scanTarget.Z;
break;
}
}
if(Success){break;}
}
}

//the following are/can be inffered based on where other corners are
xy.assign(x,y,cornerOrigin.Z);
yz.assign(cornerOrigin.X,y,z);
xz.assign(x,cornerOrigin.Y,z);
xyz.assign(x,y,z);

if (Success){//if any of the following are true then the object fails to be defined
if(!Occupied(xy)){Success = false;}
if(!Occupied(yz)){Success = false;}
if(!Occupied(xz)){Success = false;}
if(!Occupied(xyz)){Success = false;}
}

if (Success) {
xMax = (x>cornerOrigin.X) ? x : cornerOrigin.X;
xMin = (x<cornerOrigin.X) ? x : cornerOrigin.X;

yMax = (y>cornerOrigin.Y) ? y : cornerOrigin.Y;
yMin = (y<cornerOrigin.Y) ? y : cornerOrigin.Y;

zMax = (z>cornerOrigin.Z) ? z : cornerOrigin.Z;
zMin = (z<cornerOrigin.Z) ? z : cornerOrigin.Z;

return new box(new possition (xMin,yMin,zMin),new possition (xMax,yMax,zMax), true);
}
else {return new box(new possition (0,0,0),new possition (0,0,0), false);}
}

public static void Main(string[] args)
{
box Boxxy = new box();
Boxxy = getBoundingBox(new possition (0,0,0));
if (Boxxy.NotNull) {Console.WriteLine("Success");}
else {Console.WriteLine("Failure");}
}
}
}


Assume the function Occupied requires one operation. Does anyone know of a way I could optimize this further?

Edit: Someone had suggested I use an octree. I don't really know what that is and, after perusing wiki to find out what it is, I'm not sure how I would implement it or apply one to this problem.

Edit2: I rewrote the code with a skeleton implementation so it can be compiled, it's meant as a mod for the game space engineers. I had to write it in an online compiler so please excuse idiosyncrasy that emerge as a result. The portion of this code I'm really asking about is the 'getBoundingBox' function.

• Could you post the complete code? What is scanTarget or Occupied? How does this work? Why 399? What does this formula do float(J)*(pow(-1,I))? What is NULL? It looks like pseudocode. – t3chb0t Mar 1 '17 at 16:47
• This does not compile xy = {x,y,cornerOrigin.Z}; – t3chb0t Mar 1 '17 at 16:50
• This is missing parentheses if (!Occupied(xy){ Success = false; } and does not compile either. – t3chb0t Mar 1 '17 at 16:52
• You have 3 instances where Success == false is missing the ending semi-colon. – Rick Davin Mar 1 '17 at 17:05
• @t3chb0t I've edit the code to make it a bit clearer for you, and fixed the compilation errors you found, I had no access to a compiler when i wrote this and forgot NULL should be null in c#. 399 because that's the maximum distance the search should go to in any direction(400 units including the origin). – JOJO Mar 2 '17 at 19:17