Optimize a search in 3D

Question

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.

• t3chb0t: 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: This does not compile xy = {x,y,cornerOrigin.Z};
• t3chb0t: This is missing parentheses if (!Occupied(xy){ Success = false; } and does not compile either.
• Rick Davin: You have 3 instances where Success == false is missing the ending semi-colon.
• JOJO: @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).

Answer 1

I would clean your code before trying to make any performance changes to the algorithm.

struct possition

You can find lots of articles and posts online that suggest to make structs immutable. This means we should remove method assign and make the properties readonly. Let's also rename this struct to Position while we're at it and make sure to use C# Conventions instead of those of Java.

public struct Position 
{
 public float X { get; }
 public float Y { get; }
 public float Z { get; }
 public Position (Position other) => this(other.X, other.Y, other.Z);
 public Position (float x, float y, float z) => (X, Y, Z) = (x, y, z);
}

The equality check could be simplified:

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;}
}

You don't need the explicit if (condition) true else false syntax.

public static bool operator == (Position source, Position target) 
 => source.X == target.X
 && source.Y == target.Y
 && source.Z == target.Z;

Bug: The inequality check is wrong. You should have used !cond1 || !cond2 || !cond3 instead of !cond1 && !cond2 && !cond3.

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;}
}

But even better is to negate the equality check.

public static bool operator != (Position source, Position target) => !(source == target);

struct box

I have no idea what NotNull means here. If you want the struct to be null-assignable, you should use a Nullable<box> instead. Also, this.NotNull = NULL; is a really unfortunate assignment. Why store the variable with its inverse meaning, it only adds confusion? Min and Max are common names for bounds, use them. Here's a refactored immutable struct.

public struct Box 
{
 public Position Min { get; }
 public Position Max { get; } 
 public Box (Position min, Position max) => (Min, Max) = (min, max);
}

public static box getBoundingBox

• You state the helper Occupied used by getBoundingBox is for testing purposes only. Then why does getBoundingBox call it?
• There is no clear specification what this method should do. Start by providing a clear spec.
• You don't need the #.f semantics for providing floats to your classes. cornerOrigin.assign(0.0f,0.0f,0.0f); can be written as cornerOrigin.assign(0, 0, 0);. - Since you no longer should assign, make a new instance instead var corner = new Position(0, 0, 0);. If you need to provided parameter to be able to store a different value, make it a by-ref parameter getBoundingBox(ref Position cornerOrigin).
• You have recurring blocks of code if(Success) Success = false;. Rather than resetting variables, you should split this algorithm up into more and smaller methods instead.

---

☛ Once you have cleaned your code up, perhaps you could ask a follow-up question with code that's much more comprehensible.