Reasoning about the Embedded Shape of a Qualitatively Represented Curve⋆ Kazuko Takahashi1 1 Kwansei Gakuin University, 1 Gakuen Uegahara, Sanda, Japan Abstract 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. Keywords qualitative spatial reasoning, curved line, embedding on a plane 1. Introduction 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 [1, 2, 3]. The approach requires no big data and has less computational complexity, since it does not treat the numerical data. It also enables reasoning that suits human recognition. The focused aspects involve relative location, direction, size, distance of objects, the shapes of an object, and so on. Systems that combine more than one aspect are also proposed. Previously, we proposed a qualitative representation that describes the outline of a curve as a sequence of segments [4]. There, we defined the connection rule of curved primitive segments to obtain a smooth continuous curve. On the other hand, there are an infinite number of embeddings of the obtained curve on a two-dimensional plane, since precise information such as coordinates are missing. If an embedding forms a spiral, it is not realistic as a boundary of an object in nature. 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. SCSS 2024: 10th International Symposium on Symbolic Computation in Software Science, August 28–30, 2024, Tokyo, Japan ⋆ You can use this document as the template for preparing your publication. We recommend using the latest version of the ceurart style. * Corresponding author. $ ktaka@kwansei.ac.jp (K. Takahashi) € https://ist.ksc.kwansei.ac.jp/~ktaka/LABO/ (K. Takahashi)  0000-0002-5572-7747 (K. Takahashi) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 113 2. Fundamental Concepts Let CURVES be a set of directed curved segments with a unique direction and curvature on a two- dimensional 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: 𝑋 ∼ 𝑌 iff 𝑉 = 𝑉 ′ , 𝐻 = 𝐻 ′ 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) Figure 1: Connection of segments. 3. Embedding on a Two-Dimensional Plane 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. 114 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) Figure 2: Different embeddings of 𝑋 · 𝑌 . Figure 3: Open/closed embedding of 𝑋 · 𝑍 · 𝑌 . If there is an open embedding of an scurve, then the scurve is said to be admissible. The empty sequence 𝜖 is considered to be admissible. 4. Admissibility 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 𝑋 ∈ 𝒮, 𝑜𝑟𝑛(𝑋) = ′ + ′ iff 𝑋 = (𝑛, 𝑒, 𝑐𝑥), (𝑠, 𝑒, 𝑐𝑥), (𝑠, 𝑤, 𝑐𝑐) or (𝑛, 𝑤, 𝑐𝑐); 𝑜𝑟𝑛(𝑋) = ′ − ′ iff 𝑋 = (𝑠, 𝑤, 𝑐𝑥), (𝑠, 𝑒, 𝑐𝑐), (𝑛, 𝑒, 𝑐𝑐) or (𝑛, 𝑤, 𝑐𝑥). • For 𝑋1 , . . . , 𝑋𝑛 ∈ 𝒮, 𝑜𝑟𝑛(𝑋1 · . . . · 𝑋𝑛 ) = 𝑜𝑟𝑛(𝑋1 ) . . . 𝑜𝑟𝑛(𝑋𝑛 ). We define the function 𝑖𝑛𝑣 on the set {+, −} that assigns the opposite orientation: 𝑖𝑛𝑣(+) = − and 𝑖𝑛𝑣(−) = +. For an scurve 𝑝, the difference of the numbers of + and − that appear in 𝑜𝑟𝑛(𝑝) is said to be rotation difference of 𝑝. Some specific subsequences in the orientation of an scurve do not affect the judgment of its admis- sibility. We consider a shorter sequence by removing these parts. There are two reduction rules: the 115 (a) (b) Figure 4: Examples in which admissibility is not preserved. subsequence + − + (or − + −) is reduced to + (or −, resp.), and the subsequence + + −− (or − − ++) 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 𝜎1 𝑠1 𝑠2 𝑠3 𝜎2 is reduced to 𝜎1 𝑠1 𝜎2 . (r2) If 𝑠1 = 𝑠2 = 𝑖𝑛𝑣(𝑠3 ) = 𝑖𝑛𝑣(𝑠4 ) and ( 𝜎1 , 𝜎2 = 𝜖 or 𝜎1 , 𝜎2 ̸= 𝜖 ), then 𝜎1 𝑠1 𝑠2 𝑠3 𝑠4 𝜎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 difference preservation) The rotation difference 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. 116 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 difference. 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 [5, 6]. Due to the symmetry of the orientations + and −, and that of the order of the sequence, symmetric orientations need not be investigated. The introduction of the reduction significantly decreases the number of sequences to be checked, since the length is shortened and the reduced forms are restricted as is shown in Proposition 1. For example, we should examine four cases when 𝑛 is six, and only one case when it is eleven. And we conclude that for any scurve, its admissibility can be determined by the sequence of its orientation, and we have gotten the following theorem. Theorem 3. 𝑝 is admissible if and only if 𝑘 ≤ 3, where 𝑘 is the rotation difference of the orientation of 𝑝. 5. Related Works 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 [7, 8, 9]. Segments are usually equipped with information of its shape related to their subsequent segments. Additional information such as relative length and angle may be added to each segment [10, 11]. 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 [12, 13]. In OPRA, a primitive object is considered as a vector with its initial point and terminal point, which has a similar feature with our formalization. However, the primitive object in OPRA does not have a convexity as an attribute, which means that OPRA cannot be applied to the generation of a smooth curve by connecting objects. 6. Conclusion 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 difference 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. 117 References [1] A. Cohn, J. Renz, Qualitative spatial representation and reasoning, in: Handbook of Knowledge Representation, Elsevier, 2008. [2] J. Chen, A. Cohn, D. Liu, S. Wang, J. Ouyang, Q. Yu, A survey of qualitative spatial representations, The Knowledge Engineering Review 30 (2013) 106–136. [3] M. Sioutis, D. Wolter, Qualitative spatial and temporal reasoning: current status and future challenges, in: Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021, pp. 4594–4601. [4] Y. Taniuchi, K. Takahashi, Spatial representation and reasoning about fold strata: A qualitative approach, in: 15th International Conference, ICAART 2023, Revised Selected Papers, 2024, pp. 244–266. [5] K. Takahashi, Qualitative treatment of curves and judgment for their self-intersectionality (in japanese), in: IPSJ, SIG-PRO-149, 2024. [6] K. Takahashi, Qualitative formalization of a curve on a two-dimensional plane, in: The 16th International Conference on Spatial Information Theory (COSIT 2024), to appear. [7] M. Leyton, A process-grammar for shape, Artificial Intelligence 34 (1988) 213–247. [8] M. Tosue, K. Takahashi, Towards a qualitative reasoning on shape change and object division, in: 14th International Conference on Spatial Information Theory (COSIT 2019), 2019, pp. 7:1–7:15. [9] A. Galton, R. Meathrel, Qualitative outline theory, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (1999) 1061–1066. [10] L. M. Cabedo, L. G. Abril, F. V. Morente, Z. Falomir, A pragmatic qualitative approach for juxtaposing shapes, Journal of Universal Computer Science 16 (2010) 1410–1424. [11] Z. Falomir, A. Pich, V. Costa, Spatial reasoning about qualitative shape compositions, Annals of Mathematics and Artificial Intelligence 88 (2020) 589–621. [12] R. Moratz, Representing relative direction as a binary relation of oriented points, in: Proceedings of the 17th Eureopean Conference on Artificial Intelligence, ECAI’2006, 2004, pp. 407–411. [13] T. Mossakowski, R. Moratz, Qualitative reasoning about relative direction of oriented points, Artificial Intelligence 180-181 (2012) 34–45. Acknowledgments This research is supported by JSPS Kakenhi 24K15096. 118