This paper addresses the problem of embedding curves, represented qualitatively as sequences of primitive segments, onto a two-dimensional plane. These primitive segments are directed curved segments with intrinsic direction and convexity. We define a symbolic expression to each segment, and by connecting these segments, we can derive a symbolic expression that represents an abstract shape of a smooth continuous curve. There are an infinite number of embeddings of the derived curve on a two-dimensional plane, since precise information such as coordinates are missing. However, for some shape of curves, any embedding forms a spiral, which is undesirable when the curve represents the boundary of a natural object. We propose a method for judging whether it is possible to draw a curve not in a spiral form on a two-dimensional plane by checking the segment orientation.
Qualitative Spatial Reasoning (QSR) is a method that gives a symbolic expression to a spatial object or
the relationships between objects, focusing on a specific aspect of the spatial data, and that conducts
reasoning on this expression [
Previously, we proposed a qualitative representation that describes the outline of a curve as a sequence
of segments [
In this paper, we discuss whether there exists a way to embed a curve so that it does not form a spiral and show the judgment method by introducing the reduction rules on the sequence of orientations of a curve.
This paper is organized as follows. In Section 2, we describe fundamental concepts. In Section 3, we discuss the embedding of a curve in a qualitative representation on a two-dimensional plane. In Section 4, we propose the method of judging whether there exists an embedding that does not form a spiral. In Section 5, we compare our work with the related works. Finally, in Section 6, we show our concluding remarks.
Let CURVES be a set of directed curved segments with a unique direction and curvature on a twodimensional plane. For ∈ CURVES , we represent the qualitative shape of focusing on its intrinsic direction and convexity, ignoring the precise size and the exact curvature.
Let = {, }, ℎ = {, }, = {, } and = ∪ ℎ. The symbols , , and indicate the north, south, east and west directions, respectively, and and indicate convex and concave, respectively. The direction exactly in the middle between north and south (east and west) is regarded as either or ( or , resp.). Straight lines are not considered. For ∈ CURVES , = (, , ) is said to be the qualitative representation of where ∈ , ∈ ℎ and ∈ . , and show the vertical direction, horizontal direction and the convexity of . For , ∈ CURVES , let = (, , ) and = ( ′, ′, ′) be qualitative representations of and , respectively. We define the relation ∼ on CURVES as follows: ∼ if = ′, = ′ and = ′. Then ∼ is an equivalence relation on CURVES . As a result, CURVES is classified into eight equivalence classes which are jointly exhaustive and pairwise disjoint. We denote the set of these equivalence classes as , that is, = CURVES / ∼ . Then, ∈ CURVES is mapped to ∈ .
In this paper, a smooth continuous curve without a self-intersection is called an scurve. We connect multiple segments in to create an scurve.
For ∈ , its initial and terminal points are indicated by () and (), respectively. For , ∈ , if an scurve is obtained by considering that ( ) and () are identical, then and are said to be directly connectable, and the outcome of the connection is represented as · . For , ∈ , if = , then they are directly connectable and the result is regarded as a single segment without a cusp, since the precise curvatures of and are ignored. When and are directly connectable, and ̸= , the connection of and create inflection or extremum points via direct connections.
For 1, . . . , ∈ ( ≥ 2), if for each such that 1 ≤ ≤ − 1, and +1 are directly connectable, then we obtain an scurve by directly connecting and +1, and the outcome of the connections is represented as 1 · . . . · . As a result, scurve is a sequence of qualitative representations of curved segments.
For example, = (, , ) and = (, , ) are directly connectable (Figure 1(a)), and = (, , ) and = (, , ) are directly connectable (Figure 1(b)). On the other hand, = (, , ) and = (, , ) are not, since a cusp is created at their connection (Figure 1(c)); but if we insert = (, , ) between and , then we get an scurve · · (Figure 1(d)).
(a) (b) (c)
(d)
In the following, ‘embedding of ’ means an assignment of one ∈ CURVES to ∈ . It is defined as follows: 1. Let ∈ CURVES be a curved segment on a two-dimensional plane of which ∈ is its qualitative representation. (Note that there are infinite number of ’s.) Then is said to be an embedding of . () and () represent the locations of the initial point and the terminal point of on a two-dimensional plane, respectively. 2. Let 1 · . . . · be an scurve 1 · . . . · , and (1 ≤ ≤ ) be an embedding of . For all such that 1 ≤ ≤ − 1, if () and (+1) are located in the same position, then 1 · . . . · is said to be an embedding of an scurve 1 · . . . · .
For example, Figure 2 shows two kinds of embeddings of · where = (, , ) and = (, , ). The relative directions of the locations of ( ) regarding () are (, ) and (, ) in Figure 2(a) and Figure 2(b), respectively.
If an embedding of an scurve forms a spiral, it is not desirable, when an scurve corresponds to a boundary of an actual object. However, there exists an scurve which cannot be drawn in a non-spiral form, no matter how it is drawn. Here, we introduce a concept of an orientation of an scurve on a symbolic expression, and discuss the shape of its embedding by checking the orientation. We show how to determine whether there exists an embedding that does not form a spiral on a two-dimension plane, for a given scurve. For this purpose, we introduce a concept of open/closed embedding.
For , ∈ , let be an embedding of an scurve from to on a two-dimensional plane, where and be embeddings of and , respectively. And ′ be an infinite-length curve that is obtained by extending in both directions in a manner such that the curvature of at () and that of at ( ) are preserved. If ′ has a self-intersection point, then the embedding is said to be closed; otherwise, it is open. Figure 3 shows open (a) and closed (b) embeddings of an scurve · · where = (, , ), = (, , ) and = (, , ).
(a) (b) (a) (b)
4.1. Reduction For ∈ , its orientation is defined either as clockwise ( +) or anti-clockwise (− ). Moreover, the orientation of an scurve is defined as a sequence of orientations of the segments that configure it. • For ∈ , () = ′ + ′ if = (, , ), (, , ), (, , ) or (, , ); () = ′ − ′ if = (, , ), (, , ), (, , ) or (, , ). • For 1, . . . , ∈ ,
(1 · . . . · ) = (1) . . . ().
We define the function on the set {+, −} that assigns the opposite orientation: (+) = − and (− ) = +.
For an scurve , the diference of the numbers of + and − that appear in () is said to be rotation diference of .
Some specific subsequences in the orientation of an scurve do not afect the judgment of its admissibility. We consider a shorter sequence by removing these parts. There are two reduction rules: the subsequence + − + (or − + − ) is reduced to + (or − , resp.), and the subsequence + + − is reduced to the empty sequence . [Reduction rules]
Let 1 and 2 be sequences of orientations and 1, 2, 3, 4 ∈ {+, −} . (r1) If 1 = 3 = (2), then 1123 2 is reduced to 11 2. (or − − ++) (r2) If 1 = 2 = (3) = (4) and ( 1, 2 = or 1, 2 ̸= ), then 11234 2 is reduced to 1 2.
For a sequence of orientations , a sequence of orientations obtained by applying the reduction rules as far as possible is said to be a reduced form of .
Note that the condition on 1 and 2 in (r2) are necessary. It means that if only one of 1 and 2 is an empty sequence, then admissibility of is not always the same with that of ′. We show two examples that illustrate this situation.
1. Assume that = 1 · . . . · 9 where () = + + + + − − − + +. If we reduce the part − − ++ to obtain ′ = 1 · . . . · 5, then (′) = + + + + − . In this case, is admissible whereas ′ is not (Figure 4(a)). 2. Assume that = 1 · . . . · 7 where () = + + + + + − − . If we reduce the part + + − to obtain ′ = 1 · 2 · 3, then (′) = + + +. In this case, is not admissible whereas ′ is (Figure 4(b)).
For any sequence of orientations and any of its reduced form, the following properties hold, which are easily proved.
Proposition 1. 1. (termination)
The reduction procedure terminates. 2. (rotation diference preservation)
The rotation diference is preserved in the reduction. 3. (reduced form)
Let be either + or − . A reduced form is 1 2 3 where 2 is a nonempty sequence of , and 1 and 3 are the sequences of at most two ().
Generally, a reduced form of is not unique. For example, when = + + + − − + − , if we apply (r2) first, then we get the reduced form ; whereas if we apply (r1) first, then we get the reduced form +− . However, admissibility of these reduced forms are the same.
In addition to Proposition 1, reduction has a significant property of preserving admissibility. Theorem 2 (admissibility preservation). An scurve is admissible if and only if its reduced form is admissible. 4.2. Judgment of Admissibility For a given scurve , we determine its admissibility by checking its orientation.
Let = 1 · . . . · be a reduced form of a given scurve, and be its rotation diference.
Generally it is known that if the rotation angle of a curve is greater than or equal to 2 , then it forms a spiral and may have a self-intersection point on a two-dimensional plane. If ≥ 4, the rotation angle of an scurve is greater than or equal to 2 ; in this case, is not admissible. Therefore, it is enough to investigate the admissibility in the cases for ≤ 3.
When is more than eleven, ≥ 4 always holds, since there exist at most two segments at each end
of a sequence that have the opposite orientation to those in the center of the sequence. It follows that
any embedding of is closed, and thus is not admissible. When is less than twelve, we investigate
the admissibility of all possible orientations for scurves [
Theorem 3. is admissible if and only if ≤ 3, where is the rotation diference of the orientation of .
Embedding of curves and their intersection are frequently handled in geometry or graph theory. In geometry, shapes with strict curvatures are considered; and in graph theory, connectivity between nodes is the main target to be discussed and convexity of an edge is out of focus. The QSR approach taken in this paper treats these issues from yet another viewpoint; it is suitable for human’s recognition of abstract shapes and reasoning on an abstract level.
Although there have been lots of research on QSR, few of them focus on shapes, especially on curves.
Several systems in these works divide the boundary of an object into segments and represent its shape
by lining up the symbols corresponding to the segments [
Several QSR systems have been proposed which focus on relative directions. Moratz et al. proposed
OPRA that represents the relative direction of spatial entities as a ternary relation [
In this paper, we have discussed the treatment of curves in a symbolic expression, focusing on the admissibility of the curves. In conclusion, we have shown that the admissibility of a curve can be determined by its orientation sequence: if the rotation diference is less than or equal to three, the curve is admissible. We have introduced reduction rules that significantly decreases the number of sequences to be checked. This framework provides a novel approach for reasoning about the shapes of curves on a two-dimensional plane, ensuring that they do not form spirals.
It is to be considered to improve the reasoning system by relaxing the conditions on the application of the reduction rules. In addition, we are considering formalization of the obtained result as a QSR system, and also verification using proof assistant systems to certify the proofs.
This research is supported by JSPS Kakenhi 24K15096.