Method of and apparatus for obtaining image data used for filling inner or outer region of graphic figure

• US 5,065,344 A
• Filed: 09/26/1988
• Issued: 11/12/1991
• Est. Priority Date: 09/25/1987
• Status: Expired due to Fees

• Current Assignee: SCREEN Holdings Co., Ltd.
• Original Assignee: SCREEN Holdings Co., Ltd.
• Inventors: Kishimoto, Katsumi, Shimazu, Shigeaki
• Primary Examiner(s): Herndon, Heather R.
• Application Number:
  US07/249,641
• Time in Patent Office: 1,142 Days
• Field of Search: 364/518, 364/521, 364/522, 340/721, 340/723, 340/744, 340/745, 340/747, 382/44-48
• US Class Current: 345/626
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

Segment data expressing segments which form the contour of a graphic figure are provided. Connection mode data expressing the connection modes between the segments are generated. The loops included in the graphic figure are detected on the basis of the segment data and the connection mode data. Even if the segments imperfectly define the contour, the loops can be detected through the step of correcting the segment data and the connection mode data.

Claims

1. A method of processing data for use in filling a region which is inside or outside of a graphic figure, said method comprising:

(a) preparing segment data representative of segments which form a contour of a graphic figure on an image plane, said segments defining connection modes therebetween;

(b) using said segment data to generate connection mode data representative of said connection modes;

(c) using said connection mode data to select a first one of said segments, said first segment having a floating terminal point;

(d) subsequent to said step (c), correcting said segment data and said connection mode data so that said first segment does not have a floating terminal point;

(e) subsequent to said step (d), using said connection mode data to detect a loop formed by said segments and to obtain loop data representative of said loop; and

(f) subsequent to said step (e), using said loop data and said segment data to obtain data for use in filling a region which is inside or outside of said loop;

wherein each one of said connection modes is classified as either a perfect connection mode or an imperfect connection mode, said perfect connection mode being defined as a mode in which a terminal point of a segment coincides with a terminal point of another segment, said imperfect connection mode being defined as a mode other than said perfect connection mode; and

wherein said step (c) includes using said connection mode data to detect a segment which is connected to another segment in an imperfect connection mode.

2. The method of claim 1, wherein said step (b) includes the steps of:

(b-1) generating data for a plurality of rectangles on said image plane, said rectangles surrounding said segments;

(b-2) selecting interrelated rectangles from among said plurality of rectangles, said interrelated rectangles surrounding a plurality of said segments, said interrelated rectangles overlapping each other on said image plane; and

(b-3) determining the respective connection modes between said segments surrounded by said interrelated rectangles.

3. The method of claim 2, wherein said step (b-2) includes the steps of:

(b-2-1) dividing said image plane repeatedly to obtain a tree of divisional areas, each one of said divisional areas being related to another of asid divisional areas according to a predetermined sequence of division;

(b-2-2) comparing each of said plurality of rectangles with said divisional areas to determine respective minimum divisional areas which include said rectangles; and

(b-2-3) identifying respective minimum divisional areas which are related according to said sequence.

4. The method of claim 2, wherein said interrelated rectangles surround said segments with a predetermined margin.

5. The method of claim 2, further comprising the step of delivering said data for use in filling said region to an iamge recorder to fill said region along scanning lines;

each of said rectangles having two pairs of opposite sides, one of said pairs being parallel to said scanning lines.

6. The method of claim 1 further comprising the step of storing said connection mode data in a memory as a data base.

7. The method of claim 1, wherein:

said step (e) includes the steps of;

(e-1) detecting a fundamental loop in which segments are serially connected only in a fundamental connection mode, said fundamental connection mode being defined as a mode wherien a terminal point of one segment coincides with a terminal point of another segment; and

(e-2) detecting a bridging loop formed by a segment bidging between detected loops; and

said loop data is representative of said fundamental loops and said bridging loop.

8. The method of claim 7, wherein:

said step (e) further includes the steps of;

(e-3) generating a connection point sequence table, said connection point sequence table representing a sequence of connection points of a first loop, said connection points being points at which said first loop is connected to segments other than segments forming said first loop; and

said step (e-2) includes the steps of;

(e-2-1) tracing a chain of segments from said first loop to a second loop;

(e-2-2) subsequent to said step (e-2-1), selecting a second connection point from said connection point sequence table, said second connection point following a connection point at which said tracing reaches said second loop; and

(e-2-3) tracing a chain of segments from said second connection point.

9. The method of claim 1, wherein:

said segments are vectors, each of said vectors being defined by a start point and an end point, said segment data including coordinates of said start points and said end points;

a plurality of loops are detected during said step (e), said loops including clockwise loops and counterclockwise loops determined with respect to the direction of said vectors; and

said step (f) includes the steps of;

(f-1) determining a mutual inclusion relationship between said plurality of loops; and

(f-2) changing the start point and end point of each vector so that a clockwise loop adn an anticlockwise loop occur alternately within said mutual inclusion relationship, provided that an outermost loop has a loop direction determined according to a plan for filling a graphic figure.

10. The method of claim 1, wherein said segment data is adapted for use in a cutting machine.

11. A data processor for converting segment data representative of segments which form a contour of a graphic figure into image data for filling a region which is inside or outside of said graphic figure, said data processor comprising:

(a) connection mode data generating means for generating connection mode data representative of connection modes between segments which form a contour of a graphic figure, each one of said connection modes being classified as either a perfect connection mode or an imperfect connection mode, said perfect connection mode being defined as a mode in which a terminal point of a segment coincides with a terminal point of another segment, said imperfect connection mode being defined as a mode other than said perfect connection mode, said segments being represented by segment data;

(b) a memory for storing said connection mode data as a data base;

(c) correction means for (1) using said connection mode data to detect a segment which is connected to another segment in an imperfect connection mode and (2) correcting said segment data and said connection mode data to create corrected data representative of a state wherein a terminal point of each of said segments coincides with a terminal point of another of said segments;

(d) a loop detecting means for detecting a loop formed by said segments with reference to said corrected data to obtain loop data representative of said loop; and

(e) image data generating means for generating image data for filling a region which is inside or outside of said loop, said image data generating means being responsive to said loop data and said segment data.

12. The data processor of claim 11, wherein said connection mode data generating means includes:

(a-1) positional relationship determining means for determining a positional relationship between a terminal point of a segment and a terminal point of another segment; and

(a-2) means for generating said connection mode data according to said positional relationship.

13. The data processor of claim 12, wherein said connection mode data generating means further includes:

(a-3) means for generating data for a plurality of rectangles surrounding said segments in an image plane;

(a-4) means for selecting interrelated rectangles from among said plurality of rectangles, said interrelated rectangles overlapping each other on said image plane; and

(a-5) means for delivering a portion of said segment data corresponding to segments surrounded by said interrelated rectangles to said positional relationship determining means.

14. The data processor of claim 11, wherein said loop detecting means includes:

(d-1) means for tracing a chain of segments which are serially connected only in a fundamental connection mode to detect a fundamental loop, said fundamental connection mode being defined as a mode wherein a terminal point of a segment coincides with a terminal point of anotehr segment, said fundamental loop being defined as a loop in whcih segments are serially connected only in said fundamental connection mode;

(d-2) means for tracing a chain of segments to detect a bridging loop; and

(d-3) means for generating said loop data with respect to both sid fundamental loops and said bridging loop.

15. A method of sorting segments defined with respect to an image plane into segment groups to detect a loop formed by said segments in each of said segment groups, said method comprising:

(a) receiving segment data representative of segments defined with respect to an image plane;

(b) generating data for rectangles which surround said segments in said image plane;

(c) determining areas in which said rectangles are located on said image plane;

(d) sorting said rectangles into rectangle groups so that all of said rectangles which belong to one of said areas are identified as a rectangle group; and

(e) sorting said segments into segment groups, each one of said segment groups including segments corresponding to rectangles of a rectangle group.

16. The method of claim 15, wherein said rectangles define predetermined margins around said segments.

17. The method of claim 15, wherein:

said step (c) includes the steps of;

(c-1) repeatedly dividing said image plane to obtain a tree of divisional areas in which each of said divisional areas is related according to a predetermined sequence of division; and

(c-2) comparing each of said rectangles with said divisional areas to determine minimum divisional areas which include said rectangles; and

said step (d) includes sorting said rectangles according to said minimum divisional areas.