Method and apparatus for schematic routing
First Claim
1. A method for generating a graphical connector to form a connection between a first location on a first vertex object and a second location on one of the first vertex object or a second vertex object, the vertex objects being displayed on a monitor controlled by a computer, the computer including a memory storing an object records database and a software application mapping the monitor onto an array of cells, each cell corresponding to a predetermined number of pixels, the method including the steps of:
- (1) generating a first proposed connector having a first length and corresponding to the first position on the monitor, the first proposed connector extending from the first location to the second location;
(2) for each cell corresponding to the first position, determining whether that cell is a collision cell corresponding to a position of a colliding object stored in the database, and if so, assigning a value to a collision count, the value depending upon the total number of cells that are collision cells;
(3) if the collision count for the first position is zero, then storing the first proposed connector as the best connector and proceeding to step 9;
(4) generating an new proposed connector corresponding to a new position on the monitor and extending from the first location to the second location;
(5) for each cell corresponding to the new position, determining whether that cell is a collision cell corresponding to a position of an object stored in the database, and if so, assigning a value to a new collision count, the value depending upon the total number of cells that are collision cells;
(6) if the new collision count for the new position is zero, then storing the new proposed connector as the best connector and proceeding to step 9;
(7) if the new collision count for the new position is nonzero, maintaining a best collision count record of the proposed position having the lowest collision count of all proposed positions generated so far and storing the corresponding connector with the lowest collision count as the best connector, and returning to step 4;
(8) repeating steps 4 through 7 until at least one predetermined break criterion is met, and then proceeding to step 9; and
(9) storing the cells of the best connector in said memory.
3 Assignments
0 Petitions
Accused Products
Abstract
An apparatus and method for generating connected graphs for display on a computer monitor. A data structure and virtual map are defined which provide a linked list of objects appearing at any location in the connected graph, the virtual map being larger than the dimensions of the display monitor if the connected graph demands larger dimensions. Commands carried out with respect to any object on the monitor are correlated with the cell maps in the virtual map, which point to the linked lists of objects, the lists in turn pointing to objects stored in an object records database. This provides rapid access to all objects at any given location on the display or in the connected graph. When a user gives a command to create a connection between two objects in the graph, the method generates the shortest connection possible, in terms of both pixel length and arc length for arc-connections, balanced against a minimization of collisions by the connection with existing objects, including other connections. The method is described in connection with the generation of graphical models of finite state machines (FSMs), but is suitable for use in any system where it is desirable to rapidly produce connected graphs and to maintain a minimum, user-definable level of clarity and legibility of the graph.
-
Citations
17 Claims
-
1. A method for generating a graphical connector to form a connection between a first location on a first vertex object and a second location on one of the first vertex object or a second vertex object, the vertex objects being displayed on a monitor controlled by a computer, the computer including a memory storing an object records database and a software application mapping the monitor onto an array of cells, each cell corresponding to a predetermined number of pixels, the method including the steps of:
-
(1) generating a first proposed connector having a first length and corresponding to the first position on the monitor, the first proposed connector extending from the first location to the second location; (2) for each cell corresponding to the first position, determining whether that cell is a collision cell corresponding to a position of a colliding object stored in the database, and if so, assigning a value to a collision count, the value depending upon the total number of cells that are collision cells; (3) if the collision count for the first position is zero, then storing the first proposed connector as the best connector and proceeding to step 9; (4) generating an new proposed connector corresponding to a new position on the monitor and extending from the first location to the second location; (5) for each cell corresponding to the new position, determining whether that cell is a collision cell corresponding to a position of an object stored in the database, and if so, assigning a value to a new collision count, the value depending upon the total number of cells that are collision cells; (6) if the new collision count for the new position is zero, then storing the new proposed connector as the best connector and proceeding to step 9; (7) if the new collision count for the new position is nonzero, maintaining a best collision count record of the proposed position having the lowest collision count of all proposed positions generated so far and storing the corresponding connector with the lowest collision count as the best connector, and returning to step 4; (8) repeating steps 4 through 7 until at least one predetermined break criterion is met, and then proceeding to step 9; and (9) storing the cells of the best connector in said memory. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
Specification