System, method, and computer program product for a geometric search of a configurable product structure
View Patent ↗A method for searching a bill of materials (BOM) in a data processing system, a data processing system configured to perform a corresponding method, and a computer program product encoded with instructions for performing the method. The method includes retrieving BOM data in a data processing system, and forming a wavefront queue of a plurality of proto lines corresponding to the BOM data. The method also includes determining the cumulative geometric bounds of multiple ones of the plurality of proto lines and performing a geometric bounds test on the cumulative geometric bounds of multiple ones of the plurality of proto lines. The method also includes producing a BOM line to each proto line that passes the geometric bounds test, and adding the produced BOM lines to a candidate results list stored in the data processing system.
1. A method for searching a bill of materials (BOM) in a data processing system, comprising:
retrieving BOM data in a data processing system;
forming a wavefront queue of a plurality of proto lines corresponding to the BOM data by the data processing system;
determining the cumulative geometric bounds of multiple ones of the plurality of proto lines;
performing a geometric bounds test, by the data processing system, on the cumulative geometric bounds of multiple ones of the plurality of proto lines;
producing a BOM line by the data processing system corresponding to each proto line that passes the geometric bounds test; and
adding the produced BOM lines to a candidate results list stored in the data processing system.
2. The method of claim 1 , further comprising performing a geometric test on each BOM line in the candidate results list and storing the results in a confirmed BOM list.
3. The method of claim 1 , wherein the cumulative geometric bounds of multiple ones of the plurality of proto lines are determined by retrieving the cumulative geometric bounds from a spatial index.
4. The method of claim 1 , further comprising removing, from the wavefront queue, any proto line having a cumulative geometric bounds that fails the geometric bounds test.
5. The method of claim 1 , further comprising removing, from a BOM tree, a subtree corresponding to the removed proto line.
6. The method of claim 1 , wherein the BOM line is produced by applying a configuration rule to the corresponding proto line.
7. The method of claim 1 , further comprising adding, to the wavefront queue, a set of child proto lines corresponding to any proto line having a cumulative geometric bounds that passes the geometric bounds test.
8. A data processing system comprising a processor and accessible memory, the data processing system implementing a CAD system and configured to perform the steps of:
retrieving BOM data;
forming a wavefront queue of a plurality of proto lines corresponding to the BOM data;
determining the cumulative geometric bounds of multiple ones of the plurality of proto lines;
performing a geometric bounds test on the cumulative geometric bounds of multiple ones of the plurality of proto lines;
producing a BOM line corresponding to each proto line that passes the geometric bounds test; and
adding the produced BOM lines to a stored candidate results list.
9. The data processing system of claim 8 , the data processing system further configured to perform the step of performing a geometric test on each BOM line in the candidate results list and storing the results in a confirmed BOM list.
10. The data processing system of claim 8 , wherein the cumulative geometric bounds of multiple ones of the plurality of proto lines are determined by retrieving the cumulative geometric bounds from a spatial index.
11. The data processing system of claim 8 , the data processing system further configured to perform the step of removing, from the wavefront queue, any proto line having a cumulative geometric bounds that fails the geometric bounds test.
12. The data processing system of claim 8 , the data processing system further configured to perform the step of removing, from a BOM tree, a subtree corresponding to the removed proto line.
13. The data processing system of claim 8 , wherein the BOM line is produced by applying a configuration rule to the corresponding proto line.
14. The data processing system of claim 8 , the data processing system further configured to perform the step of adding, to the wavefront queue, a set of child proto lines corresponding to any proto line having a cumulative geometric bounds that passes the geometric bounds test.
15. A physical computer readable medium encoded with and comprising computer-executable instructions that, when executed, cause a data processing system to perform the steps of:
retrieving BOM data in a data processing system;
forming a wavefront queue of a plurality of proto lines corresponding to the BOM data by the data processing system;
determining the cumulative geometric bounds of multiple ones of the plurality of proto lines;
performing a geometric bounds test, by the data processing system, on the cumulative geometric bounds of multiple ones of the plurality of proto lines;
producing a BOM line by the data processing system corresponding to each proto line that passes the geometric bounds test; and
adding the produced BOM lines to a candidate results list stored in the data processing system.
16. The computer readable medium of claim 15 , further comprising computer-executable instructions that, when executed, cause a data processing system to perform the further step of performing a geometric test on each BOM line in the candidate results list and storing the results in a confirmed BOM list.
17. The computer readable medium of claim 15 , wherein the cumulative geometric bounds of multiple ones of the plurality of proto lines are determined by retrieving the cumulative geometric bounds from a spatial index.
18. The computer readable medium of claim 15 , further comprising computer-executable instructions that, when executed, cause a data processing system to perform the further step of removing, from the wavefront queue, any proto line having a cumulative geometric bounds that fails the geometric bounds test.
19. The computer readable medium of claim 15 , further comprising computer-executable instructions that, when executed, cause a data processing system to perform the further step of removing, from a BOM tree, a subtree corresponding to the removed proto line.
20. The computer readable medium of claim 15 , wherein the BOM line is produced by applying a configuration rule to the corresponding proto line.
21. The computer readable medium of claim 15 , further comprising computer-executable instructions that, when executed, cause a data processing system to perform the further step of adding, to the wavefront queue, a set of child proto lines corresponding to any proto line having a cumulative geometric bounds that passes the geometric bounds test.