Optimal boolean set operation generation among...

Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C345S443000, C345S630000, C382S226000

Reexamination Certificate

active

07426455

ABSTRACT:
Performing Boolean operations among two regions; regions and results represented as vector tuples. Establish indexing cells about regions and classify by type of interaction between regions, e.g., (boundary, boundary). For each (boundary, boundary) cell, define pseudo-points at each boundary entrance/exit. Categorize each (boundary, boundary) cell on relationship of its pseudo-points. Identify starting points along boundaries based on: categorization, operation, and interior convention. Accumulate results cycling from a starting point, along region boundary. Upon encountering each intersection, proceed along the other region boundary. Upon encountering a cell edge, proceed along the cell edge in the direction consistent with the interior convention. Where a starting point or intersection between region boundaries remains untraversed, accumulate results in tracing a similar cycle along untraced boundaries. Discard duplicate/cell-edge only tuples. After traversing all starting points/intersections of boundaries, determine results for other cell types, and concatenate with those for (boundary, boundary) cells.

REFERENCES:
patent: 5014230 (1991-05-01), Sinha et al.
patent: 5321613 (1994-06-01), Porter et al.
patent: 5353395 (1994-10-01), Tokumasu et al.
patent: 5649084 (1997-07-01), Ernst
patent: 5724451 (1998-03-01), Shin et al.
patent: 5751286 (1998-05-01), Barber et al.
patent: 5818460 (1998-10-01), Covey et al.
patent: 5901245 (1999-05-01), Warnick et al.
patent: 5924053 (1999-07-01), Horowitz et al.
patent: 5963670 (1999-10-01), Lipson et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6292797 (2001-09-01), Tuzhilin et al.
patent: 6307555 (2001-10-01), Lee
patent: 6466696 (2002-10-01), Politis
B. Chazelle, D.P. Dobkin; “Intersection of Convex Objects in Two and Three Dimensions”, Journal of the ACM, vol. 34, No. 1, Jan. 1887, pp. 1-27.
You-Dong Liang, Brian A. Barsky, “Analysis and Algorithm for Polygon Clipping”, Communications of the ACM, vol. 26, No. 11, Nov. 1983, pp. 868-877.
Clodoveu A. Davis Jr., Alberto H. F. Laender, “Multiple Representations in GIS : Materialization Though Map Generation, Geometric, and Spatial Analysis Operations”, ACM GIS '99. pp. 60-65.
Toshiaki Satoh, “Boolean Operations on Set Using Surface Data”, 1991, ACM, pp. 119-127.
D. Ayala, P. Brunet, R. Juan, I. Navazo, “Object Representation by Means of Nonminimal Division Quadtree and Octree”, ACM Transactions on Graphics, vol. 4, No. 1, Jan. 1985, pp. 41-59.
Ingo Wegener, “The Size of Reduced OBDD's and Optimal Read-Once Branching Programs for Almost All Boolean Functions”, IEEE, vol. 43, No. 11, Nov. 1994, pp. 1262-1269.
Randal E. Bryant, “Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams”, Jul. 1992.
Randal C. Nelson, Hanan Samet, “A Consistent Hierarchical Representation for Vector Data”, ACM, vol. 20, No. 4, 1986.
Charles R. Dyer, Azriel Rosenfeld, and Hanan Samet,“Region Representation:Boundary Codes from Quadtrees”, Communications of the ACM, vol. 23, No. 3, Mar. 1980, pp. 171-179.□□.
Charles R. Dyer, Azriel Rosenfeld, and Hanan Samet,“Region Representation:Boundary Codes from Quadtrees”, Communications of the ACM, vol. 23, No. 3, Mar. 1980, pp. 171-179.□□.
Sabine Timf and Andrew U. Frank, “Using Hierarchical Spatial Data Structures for Hierarchical Spatial Reasoning”, 1997, Lecture Notes in Computer Science, pp. 69-83.□□.
James M. Sheng, Olivia R. Liu Sheng, “R-tree for Large Geographic Information Systems in a Multi-User Environment”, IEEE 1990.□□.
Hanan Samet, Robert E. Webber, “Storing a Collection of Polygons Using Quadtrees”, ACM Transactions on Graphics, vol. 4, No. 3, Jul. 19885, pp. 182-222.□□.
Richard T. Antony, “Principles of Data Fusion Automation”, 1995 Artech House, Inc.
Antony, Richard T., “Principles of Data Fusion Automation,” Artech House, Inc., Copyright 1995.
Antony, R. and Emmerman, P. J., “Spatial Reasoning and Knowledge Representation,” pp. 795-813, 1986.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Optimal boolean set operation generation among... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimal boolean set operation generation among..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal boolean set operation generation among... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3971405

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.