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.
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: 𝑋 ∼ 𝑌 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
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. 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. 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.
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 (𝑛, 𝑤, 𝑐𝑥).
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 admissibility. We consider a shorter sequence by removing these parts. There are two reduction rules: the
Let 𝜎 1 and 𝜎 2 be sequences of orientations and 𝑠 1 , 𝑠 2 , 𝑠 3 , 𝑠 4 ∈ {+, −}.
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. 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.
The rotation difference is preserved in the reduction.
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.
). An scurve is admissible if and only if its reduced form is admissible.
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 𝑝.
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.
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.
This research is supported by JSPS Kakenhi 24K15096.