JPH0525149B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a stroke intersection detection device used for detecting the intersection of two strokes in a kanji learning device or the like.

For example, one type of kanji learning device is one that uses a character input device such as a tablet to determine whether a character pattern written by a learner is correct or not, and provides advice to the learner.

In such a device, for example, the kanji ``power''
If you write ``katana'' in a way that is easy to mistake for ``katana'', you can judge whether it is good or bad based on the intersection of two strokes, for example, based on the ratio of the length of the part above and below the intersection of the second stroke. It will be done.

At this time, it is desired to provide a means that can accurately and quickly detect the intersection of strokes.

[Conventional technology]

FIG. 2 is a block diagram showing the configuration of a conventional example of a stroke intersection detection device, in which 1 inputs the coordinate values of each point extracted at a predetermined time interval from the strokes of a character pattern written by a character entry person. A tablet used as a coordinate input unit; 2 is a representative point extracting unit for extracting representative points from a sequence of points extracted by the tablet 1 according to a predetermined rule, for example, by extracting points at intervals of a plurality of points; 3 approximates the stroke represented by the coordinate values of a plurality of extraction points obtained by the tablet 1 by a polygonal line by sequentially connecting the representative points extracted by the representative point extracting section 2. , a storage unit that stores data for each line segment forming a polygonal line for each of the first stroke and second stroke that are the targets of intersection detection; A first calculation unit extracts line segments for the second stroke one by one and checks whether they intersect. This is a second calculation unit that retrieves the coordinate value from the storage unit 3 and calculates the coordinate value of the intersection of the first stroke and the second stroke, for example, as the average value of the coordinate values of the end points of each line segment.

[Problem that the invention seeks to solve]

In the stroke intersection detection device having the above configuration, for example, if the first stroke is approximated by a polygonal line by m line segments, and the second stroke is approximated by a polygonal line by n line segments, then (m×n ) It is necessary to determine the intersecting nature of a pair of line segments, and in order to increase the accuracy of detecting the intersection point, the numbers m and n must become large, resulting in a problem that it takes a long time to detect the intersection point.

[Means for solving problems]

The stroke intersection detection device according to the present invention includes a coordinate input section for inputting the coordinate values of each extraction point extracted from the stroke at a predetermined interval, and a representative point from among the extracted extraction points according to a predetermined rule. A representative point extraction unit to be extracted, and two sets parallel to the coordinate axis through both ends of each partial stroke obtained by dividing the stroke or a partial stroke obtained by dividing the stroke into two by the extraction point or representative point. a first determination unit that determines a range in which two strokes may intersect based on a rectangle formed by parallel lines; and the first determination unit determines that there is a possibility that two strokes may intersect with each other. and a second determination unit that determines whether or not there is a possibility that the two partial strokes intersect by a line segment connecting the end points of each of the two partial strokes. This allows for accurate and quick detection.

[Effect]

FIG. 1b is a diagram illustrating the operation of the present invention,
The first stroke PQ and the second stroke RS are divided into two partial strokes PM and MQ and RN and NS by representative points M and N located approximately in the middle, respectively, and the orthogonal coordinate axis passes through the end points of each partial stroke. parallel to 2
Create a rectangle bMaP, a rectangle dQcM, a rectangle ReNf, and a rectangle NgSh that are composed of a pair of parallel lines, and create 2 pairs of 2 rectangles, 4 pairs of rectangles, that is, rectangle bMaP and rectangle
ReNf, rectangle bMaP and rectangle NgSh, rectangle dQcM and rectangle ReNf, and rectangle dQcM and rectangle NgSh are checked to see if there is a common part. Narrow down to partial strokes PM and RN, and do the same below.
The partial strokes PM and RN are divided into two again by a representative point approximately in the middle of each, and the range of possibilities of intersection is further narrowed down.Each time the partial strokes PM and RN are divided into two, the presence or absence of a common part is checked for the four pairs of rectangles. Since the judgment is made, if the number of times of bisection is t times, if there is one intersection point, then
It is sufficient to perform the judgment 4t times.

In addition, after narrowing down the range that may intersect using the first determination section to the sub-characters sandwiched between adjacent representative points, use the first determination section again to perform the same process. Then, by narrowing down the search to partial characters sandwiched between adjacent extraction points, the accuracy of detecting intersection points is improved.

〔Example〕

The gist of the present invention will be specifically explained below with reference to an embodiment shown in FIG.

FIG. 1a is a block diagram showing the configuration of an embodiment of the present invention, and the same reference numerals as those in the conventional example in FIG. For each of the strokes and the second stroke, the coordinate values of the plurality of extraction points obtained by the tablet 1 and the address of the coordinate values for the representative point extracted by the representative point extraction section 2 (hereinafter referred to as , a representative point address).

6, as shown in FIG. 3' and memorize it, the representative point address m=1/2(p+q) of the representative point M approximately in the middle of the first stroke PQ, and the representative point address of the representative point N approximately in the middle of the second stroke RS. The address n=1/2(r+s) is retrieved from the first storage unit 3' to create four sets of partial stroke combinations described by the representative point addresses as shown in the figure. Among the combinations, four more sets of partial strokes are created in the same way from among the partial strokes selected by the first determination section 8 described later, and in the same manner, This is the first calculation unit that calculates partial strokes that may intersect.

Reference numeral 7 indicates a pair of partial strokes sandwiched between adjacent representative points, which are selected by the first calculation unit 6, the first determination unit 8, and the second determination unit 9, which will be described later. , instead of the representative point address in the first calculation unit 6, the coordinate values of the extraction points extracted by the tablet 1 are memorized, and in the same way as the procedure in the first calculation unit 6, the coordinate values of the extraction points at both ends are stored. Four sets of partial stroke combinations described by the coordinate values of the extraction points are created and stored, and from among these four sets of partial strokes selected by the first determination unit 8 described later, a similar to create 4 sets of partial stroke combinations,
Thereafter, in the same manner, the second calculation unit calculates partial strokes that are likely to be sandwiched between and intersect with adjacent extraction points.

8 passes through both ends of each partial stroke obtained by dividing the stroke or partial stroke into two using the extraction point extracted by the tablet 1 or the representative point extracted by the representative point extraction unit 2, and the A first determination unit (see FIG. 1b) that determines a range in which two strokes may intersect based on a rectangle formed by two sets of parallel lines parallel to the coordinate axes.

9 determines whether or not there is a possibility that a pair of partial strokes will intersect based on line segments connecting the respective end points of the pair of partial strokes determined by the first determination unit 8 to have a possibility of intersecting with each other. A second determination unit that makes a determination.

Further, 10 indicates a second calculation unit 7 and a first determination unit 8.
a storage unit 11 for storing the coordinates of the intersection of the pair of partial strokes finally obtained by the and second determination unit 9;
is the display section.

Once the coordinate values of the extraction point obtained by the tablet 1 and the representative point address for the representative point extracted by the representative point extracting section 2 are stored in the storage section 3', they are then stored in the following order. Find the intersection of two strokes.

The first calculation section 6 reads representative point addresses p and q at both ends of the first stroke PQ and representative point addresses r and s at both ends of the second stroke RS from the storage section 3'.

As explained with reference to FIG. 1c, the first calculation unit 6 has four
Create a combination of substrokes of a set and delete the original combination.

The first determining unit 8 determines, from among the four sets of partial strokes obtained by the first calculating unit 6, that there is no possibility of intersecting, as explained with reference to FIG. 1b. Delete the selected partial stroke combination.

The first calculation unit 6 creates four sets of partial stroke combinations from the remaining partial stroke combinations in the same manner as described above.

Similarly, the processes of and are repeated until a combination of partial strokes sandwiched between adjacent representative points is obtained.

In this way, when a combination of partial strokes sandwiched between adjacent representative points is obtained, the second determination unit 9 determines whether or not the line segments connecting both ends of each partial stroke intersect. , determine whether there is a possibility that two partial strokes will intersect.

Note that whether or not two line segments ab and cd intersect is determined by, for example, assuming that the coordinate vectors of the end points of each line segment are a, b, c and d, and s=det.(c-a;c- d) ÷det.(b-a;c-d) t=det.(b-a;c-a) ÷det.(b-a;c-d) When 0≦s, t≦1 The determination can be made based on whether or not the following conditions are satisfied.

The second calculation unit 7 calculates a pair of partial strokes that are sandwiched between adjacent representative points and determined by the second determination unit 9 to have a possibility of intersecting.
The coordinate values x and y and u and v at both ends of xy and uv are read from the storage unit 3'.

Hereinafter, the coordinate values of the extraction points extracted by the tablet 1 are used instead of the representative point addresses, and the second calculation unit 7 is used instead of the first calculation unit 6, and the The second calculating section 7, the first determining section 8, and the second determining section 9 find a pair of partial strokes that are sandwiched between the extraction points and that may intersect with each other.

Next, the coordinates of the intersection are determined by the storage unit 10 and displayed on the display unit 11.

〔Effect of the invention〕

As explained above, according to the present invention, the range in which two strokes may intersect can be narrowed down to half each, and the partial strokes sandwiched between adjacent representative points can be sandwiched, and then , the intersecting point is determined after sub-strokes sandwiched between adjacent extraction points are found, so that the detection speed and detection accuracy can be greatly improved compared to the conventional example.

[Brief explanation of the drawing]

Figure 1a is a block diagram of one embodiment of the present invention;
Figures b and c are diagrams explaining the functions of the same embodiment, and Figure 2 is a block diagram of the conventional example. In the figure, 1 is a tablet, 2 is a representative point extraction unit,
3' is a storage section, 8 is a first judgment section, and 9 is a second judgment section.

Claims (1)

[Claims] 1. A coordinate input section for inputting the coordinate values of each of the extraction points extracted at predetermined intervals from a stroke; a representative point extraction section for extracting a representative point from the extracted extraction points according to a predetermined rule; A rectangle formed by two sets of parallel lines parallel to the coordinate axis passing through both ends of each partial stroke obtained by dividing a stroke or a partial stroke obtained by dividing the stroke into two by the extraction point or representative point. a first determination unit that determines the range in which two strokes may intersect; and a first determination unit that determines the range in which two strokes may intersect; and A stroke intersection detection device comprising: a second determination unit that determines whether or not there is a possibility that two partial strokes intersect by a line segment connecting end points.