Graphic display area classification

• US 4,368,463 A
• Filed: 03/19/1980
• Issued: 01/11/1983
• Est. Priority Date: 03/21/1979
• Status: Expired due to Term

• Current Assignee: Sigman Electronic Systems Limited, University of Surrey
• Original Assignee: Sigma Electronics Incorporated, University of Surrey
• Inventors: Quilliam, John E. H.
• Primary Examiner(s): Waring, Alvin H.
• Application Number:
  US06/131,676
• Time in Patent Office: 1,028 Days
• Field of Search: 340/700, 340/732, 340/744, 340/756, 340/720
• US Class Current: 345/440
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

A method and apparatus are provided for classifying areas on a raster-type display unit. The problem is to identify areas defined by a closed boundary--e.g. for filling in such areas. Boundary data are entered into a first "polygon" store which has a plurality of memory locations each corresponding to a respective dot position of the display field, and at least one seed point is identified. Each dot position is then examined to see whether there exists a connected path, not including a boundary position, from it to a seed point, and if there is, this fact is recorded. The criterion for deciding whether or not a path is connected depends on the definition of what constitutes a closed boundary.

Claims

1. A raster-scan display apparatus comprising:

first store means having a plurality of memory locations for storing data representing respective dot positions of a display field;

means operable to store in said store data representing boundary dot positions;

second store means having a plurality of memory locations for storing data representing respective dot positions of the display field;

means operable to define one or more notional dot positions in or adjacent the field as representing a seed point or points; and

classifying means arranged in operation, for each dot position of the display field, to determine whether there exists, from that dot position to the or a seed point, a connected path of dot positions which does not include a dot position which is indicated by the corresponding location in said first store means as being a boundary dot position and, if such a path exists, to set the corresponding location in the second store means.

2. An apparatus according to claim 1 in which the means for defining the seed point(s) comprises means operable to set one or more locations in said second store means.

3. An apparatus according to claim 1 in which the means for defining the seed point(s) comprises means operable to supply a signal indicating that all points adjacent the edge of the field are to be taken to be connected to a seed point.

4. An apparatus according to claim 1, 2 or 3 in which the classifying means is arranged to carry out a scan of the field in which, for each dot position of the field the corresponding location in the second store means is set only if the position in question (a) is not a boundary point and (b) is adjacent to, and connected to a seed point or to another point in respect of which the corresponding location in the second store means has been set, and to carry out further such scans until a scan has taken place in which no locations have been set in the second store.

5. An apparatus according to claim 4 in which any eight-connected boundary is defined as closed, and a path is defined as connected only if four-connected, and the classifying means is arranged to carry out each scan in two parts wherein, in each part of the scan, the positions of the field are scanned in turn in a raster-like manner and the corresponding location in the second store is set only if condition (b) is satisfied in respect of those seed or other points which, in the relevant scan directions, precede the point in question, the classifying means including means for reversing the sense of scan in both directions during the second part of the scan.

6. An apparatus according to claim 5 in which the means for defining the seed point(s) comprises means operable to set one or more locations in said second store means and the classifying means comprises addressing means including address counters and arranged in operation during each part of the scan, to read out sequentially in a raster-like manner, data in respect of each dot position, said data comprising:

(a) boundary data consisting of the contents of the corresponding location in the first store means

(b) fill data consisting of the contents of the corresponding location in the second store means

(c) previous line fill data consisting of the contents of the location in the second store corresponding to the corresponding dot position of the previous line (if any) of the current part of the scan

(d) previous dot fill data consisting of the contents of the location in the second store means corresponding to the previous dot position (if any) of the current scan line

in which the means for defining the seed points comprises means operable to set one of more locations in said second store means, in which the classifying means further comprises logic means responsive to said data to write into the location in the second store means corresponding to the current dot position data representing the set state only if (a) the boundary data indicates the absence of a boundary point and (b) any one of the fill data, previous line fill data (if any) and previous dot fill data (if any) indicates the set state, and in which the classifying means further comprises bistable means the state of which is changed at the conclusion of each part of the scan and which controls the count direction of the address counters.

7. An apparatus according to claim 6 in which the means for defining the seed point(s) comprises means operable to supply a signal indicating that all points adjacent the edge of the field are to be taken to be connected to a seed point and the classifying means comprises addressing means including address counters and arranged in operation during each part of the scan, to read out sequentially in a raster-like manner, data in respect of each dot position, said data comprising:

(a) boundary data consisting of the contents of the corresponding location in the first store means

(b) fill data consisting of the contents of the corresponding location in the second store means

(c) previous line fill data consisting of the contents of the location in the second store corresponding to the corresponding dot position of the previous line (if any) of the current part of the scan

(d) previous dot fill data consisting of the contents of the location in the second store means corresponding to the previous dot position (if any) of the current scan line,

in which the means for defining the seed points is arranged in operation to supply a seed signal whenever the current dot position is (in the current scan direction) the first dot position of the current line of the scan or on the first line of the field, in which the classifying means further comprises logic means responsive to said data to write into the location in the second store means corresponding to the current dot position data representing the set state only if (a) the boundary data indicates the absence of a boundary point and (b) either (i) any one of the fill data, previous line fill data (if any) and previous dot fill data (if any) indicates the set state or (ii) said seed signal is present, and in which the classifying means further comprises bistable means the state of which is changed at the conclusion of each part of the scan and which controls the count direction of the address counters.

8. An apparatus according to claim 6 in which the second store means comprises a store, single-bit locations locations of which correspond to respective dot positions of the field, which is byte-organised, first and second shift registers for parallel to bit-serial conversion of said fill data and previous line fill data respectively, and a third shift register for bit-serial to parallel conversion of the output data, in which the shift direction of the shift registers is controlled by said bistable means, and in which the logic means is connected to receive said previous dot fill data directly from said third register without passing via said store.

14. An apparatus according to claim 7 in which the second store means comprises a store, single-bit locations locations of which correspond to respective dot positions of the field, which is byte-organised, first and second shift registers for parallel to bit-serial conversion of said fill data and previous line fill data respectively, and a third shift register for bit-serial to parallel conversion of the output data, in which the shift direction of the shift registers is controlled by said bistable means, and in which the logic means is connected to receive said previous dot fill data directly from said third register without passing via said store.

9. A method for classifying areas defined by a boundary in a display field of a raster-type display, comprising defining a boundary by means of a plurality of boundary dot positions;

identifying at least one seed point;

determining, for each dot position of the display field whether there exists, from that position to the or a said seed point, a connected path of dot positions not including a boundary dot position, and if such a path exists recording the position of the dot.

10. A method according to claim 9 including identifying at least one seed point within the display field.

11. A method according to claim 9 in which a continuous boundary of seed points is assumed to exist externally of, and adjacent to, the edges of the display field.

12. A method according to claim 9, 10 or 11 in which said determination comprises carrying out a scan of the field in which each dot position of the field is recorded as being linked by a connected path to a seed point only if the position in question (a) is not a boundary point and (b) is adjacent to, and connected to a seed point or to another point in respect of which such a path has already been recorded as existing, and carrying out further such scans until a scan has taken place in which no further paths have been recorded.

13. A method according to claim 12 in which any eight-connected boundary is defined as closed, and a path is defined as connected only if four-connected, and each scan is carried out in two parts wherein, in each part of the scan, the positions of the field are scanned in turn in a raster-like manner and each dot position is recorded as being so linked only if condition (b) is satisfied in respect of those seed or other points which, in the relevant scan directions, precede the point in question, the sense of the scan in both directions being reversed during the second part of the scan.