StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGraph theory name/algorithm help required
text
Body
copied!<p>Apologies on the title, cant use 'Graph theory problem name'.</p> <p>I'm trying to process some data, where I need to extract information on structures contained within the data.</p> <ul> <li>Is a volume of space enclosed</li> <li>Volume of said enclosed space</li> </ul> <p><strong>Edit:</strong> The initial 'raw' data is in a series bytes, which I can access similar to a multidimensional array. </p> <pre><code>// X Y Z data(10, 10, 8); // 0 data(10, 10, 9); // 1 data(10, 10, 10); // 1 data(10, 10, 11); // 1 </code></pre> <p>Each neighbor in this data structure would be a possible edge-node pair, if there is a value greater than zero in the data at that position. So each element/node in the data structure could have six possible edges.</p> <p>Its trivial for me to transform this raw data into a graph like structure, since I know the starting position (seed). </p> <pre><code>node = dataToGraph(10,10,10); // seed position node->Edges[0]; // this would correspond to node represented by the value at 9,10,10 // returns null if the value is less than zero. i.e. no edge/node. </code></pre> <p>The data represents structures in 3D space, and each structure will have a specific seed(in dark grey below) of which the position is known. From this position I need to scan the data/structure to verify its a complete structure,i.e. no gaps, and if it is, compute its internal volume.</p> <p>While I'm sure I'd be able to kludge some sort of solution, its not going to be optimal, and there are millions of these structures to scan per data set.</p> <p>I'm guessing there is a standard graph theory solution I could use which would be better than anything I would hack out. Unfortunately I'm not too familiar with this sort of math, so I don't even know where to start looking.</p> <p>Below are three examples, of a 2D slice of the data which would be valid. The red line on #3 illustrates the pruned structure I'm interested in for that example.</p> <p>A valid structure always has the seed, the structure is fully closed. Invalid structures would be any structure which have a gap, anywhere in the complete 3D structure, or the seed had more than two neighbors/edges on the slice it exists on. i.e. it must not be blocked on the external or internal surface. </p> <p>The new picture of the cube below illustrates this to a degree. Assume it has a hollow interior. The red sphere is the seed, the blue line represents a single slice, #1 in the 2D example. Unfortunately, its never going to be a structure as regular as this, hence the need for the graph algorithms imo. </p> <p>I'd appreciate if someone could provide some pointers on where to start on this. I'm not expecting someone to feed me code, just to educate me ;)</p> <p><img src="https://i.stack.imgur.com/hvjsI.gif" alt="slice"> <img src="https://i.stack.imgur.com/GRara.jpg" alt="cube"></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload