RfDL: Models for Capturing Directional and Topological
Characteristics of Path-Landmark Arrangements
Yohei Kurata and Hui Shi
SFB/TR 8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany{ykurata, shi}@informatik.uni-bremen.de

Abstract. This paper develops a series of projection-based spatial models,called RfDL (Region-in-the-frame-of-Directed-Line), which distinguishes thepatterns of spatial arrangements between a directed line (DLine) and a simple
region. RfDL considers eight types of intrinsic frames based on the combinationof left-right, front-side-back, and entry-interior-exit distinctions with respect tothe DLine, which naturally yield eight models with different levels ofgranularities. The use of intrinsic frames allows the RfDL models to capture thedirectional characteristics of DLine-region arrangements. In addition, we revealthat the finest RfDL model, called RfDL3-12, also captures their topologicalcharacteristics, especially when the region is convex. Thanks to thesecharacteristics, RfDL3-12 is highly useful for the qualitative characterization ofpath-landmark arrangements standing on a moving agent’s viewpoint.

1Introduction

When people describe the movement of an agent, they often use landmarks [1]. Thus,
spatial patterns of path-landmark arrangements are crucial for modeling humanconceptualization of movement. Even though landmarks may be modeled as points[2], the studies on human route instructions to mobile robots [3, 4] observe thesubjects’ use of expressions that presume landmarks’ spatial extent, such as “follow itaround” and “hit the end of …”. This finding motivated us to explore the models of
spatial arrangements between a directed line (DLine) and a simple region, whichcorrespond to path-landmark patterns, for future applications to dialogue-based manmachine interfaces that concern spatial tasks.
There are already some spatial models that support DLine-region arrangements.
For instance, Kurata and Egenhofer [5] developed a model of topological DLineregion relations. These topological relations highlight where the DLine starts, passes,and ends with respect to the region’s inside, outside, and border. Accordingly, therelations are useful for modeling some fundamental concepts of motions, such as “gointo” and “go across”. In this model, however, all movement patterns whose routedoes not intersect with the landmark are mapped to a single topological relation,
namely disjoint, whereas people can distinguish these patterns with such expressions
as “go toward …,” “pass by … on the left,” and “go until … comes to the left”. These
expressions usually highlight the landmark’s direction as seen from the path.

2

Yohei Kurata and Hui Shi

Therefore, a model of DLine-region arrangements, which features their directional
characteristics, will be also valuable for characterizing agents’ movement patterns, aswell as for capturing some human concepts of motions.
In this paper, we develop a series of spatial models, called RfDL (Region-in-theframe-of-Directed-Line), which distinguishes the patterns of DLine-region
arrangements. In order to capture the directional characteristics of DLine-region
arrangements, RfDL adopts a similar framework to Double Cross [6, 7]. In addition,
we reveal that the finest RfDL model, called RfDL3-12, also captures the topologicalcharacteristics of the DLine-region arrangements, even though the model stands on adirection-featured framework. As a result, spatial patterns distinguished by RfDL3-12
can be used for characterizing movement patterns based on both their directional andtopological characteristics. Such versatile models will fit nicely with real world
applications, where multiple aspects of the space are involved together [8].
The remainder of this paper is structured as follows: Section 2 develops RfDL
models. Section 3 assesses the topological information conveyed by the patterns ofRfDL3-12. Finally, Section 4 concludes with the discussion of future work.

2RfDL: Models of DLine-Region Arrangement Patterns

RfDL is a newly developed series of projection-based spatial models [9] thatdistinguish the patterns of spatial arrangements between a straight DLine and a simple
region embedded in a two-dimensional Euclidean space R2. The DLine is a simple
line with two ordered endpoints [10]. The simple line is a one-to-one mapping from[0, 1] to R2 [11]. A simple region is a bounded, regular closed set that ishomeomorphic to a closed neighborhood in R2 [11]. Following Orientation Calculi [2],we consider eight intrinsic frames of spatial reference [12], which partition the space
into fields on/around the DLine based on the combination of left-right, front-sideback, and entry-interior-exit distinctions (Fig 1a). These fields include zero- and onedimensional ones that fill the gap between two-dimensional fields. The pattern of aDLine-region arrangement is defined as the set of fields over which the regionextends. Naturally, the eight frames yield eight RfDL models with different levels ofgranularities. Each RfDL model is called RfDLm-n where m-n indicates the number ofthe fields on/around the DLine. For instance, RfDL3-12 adopts a ‡-shaped frame, which
defines three fields on the DLine—En (entry), I (interior), and Ex (exit)—and twelve
fields around it—LF (left front), SF (straight front), RF (right front), LB (left back),SB (straight back), RB (right back), LEn (left at entry), REn (right at entry), LI (left ofinterior), RI (right of interior), LEx (left at exit), and REx (right at exit) (Fig. 1b). The
patterns of DLine-region arrangements distinguished by RfDL3-12 (in short, RfDL3-12patterns) are represented visually by icons with 3×5 cells (Fig. 1c), whichgeometrically correspond to the 15 fields defined by the RfDL3-12’s frame. The marked
cells indicate the fields over which the region extends. Accordingly, RfDL3-12 patterns
are distinguished by the icons’ marking patterns.
RfDL3-12 is closely related to Double Cross [6, 7]. Double Cross distinguishes 15
patterns of ternary point arrangements [6], which are also viewed as 15 arrangement
patterns of a straight DLine and a point [7]. Both RfDL3-12 and Double Cross adopt theRfDL: Models for Capturing Directional and Topological Characteristicsof Path-Landmark Arrangements
312112212211211121221211211212

RfDL1-1

RfDL1-4

RfDL1-8010122

12001

RfDL3-1

RfDL3-4

RfDL1-12

12012
110212122121021120112

RfDL3-8(a)RfDL3-12

LF SF RFLEx Ex RExLIIRILEn En REn
LB SB RB(b)(c)

Fig. 1. (a) Eight frames of RfDL models (the numbers show the dimension of each field), (b)fifteen fields that RfDL3-12’s frame defines, and (c) iconic representation of an RfDL3-12 pattern.

same ‡-shaped frame that defines 15 fields. Accordingly, the RfDL3-12 pattern between
a DLine D and a region R is represented as the union of Double Cross patterns
between D and every point x in R. This does not mean, however, that the union ofarbitrary set of Double Cross patterns forms an RfDL3-12 pattern, because RfDL3-12patterns must satisfy the following two conditions:• the referent extends over at least one two-dimensional fields; and• the set of fields over which the referent extends must be connected, even if En and
Ex are removed from this set.
If the second rule is not satisfied, the referent has a spike or a disconnected interior as
long as the referent is a single connected set and, accordingly, the referent cannot be asimple region. Due to these two constraints, the number of RfDL3-12 patterns is limited
to 1772, instead of 215 = 32768.
In a similar way, we identified that RfDL1-1, RfDL1-4, RfDL1-8, RfDL1-12, RfDL3-1,RfDL3-4, and RfDL3-8 distinguish 2, 23, 142, 479, 8, 92, and 520 patterns of DLineregion arrangements, respectively. Providing such a series of models is useful toprevent the model’s overspecification. Suppose a robot that moves in a room avoiding
pieces of furniture. In this scenario, the robot’s path never overlaps with thelandmarks (furniture). This means that RfDL3-n is overspecific for the characterizationof this robot’s movement. The adoption of RfDL1-n instead of RfDL3-n drasticallyreduces the number of possible patterns and enables efficient computation processing.

3Topological Characteristics Captured by RfDL3-12

The patterns of RfDL3-n models describe whether each endpoint and interior of theDLine intersects with the region’s or not. This is a crucial topological property ofDLine-region arrangements. If a single model may capture both directional andtopological characteristics, we can avoid mixed use of two spatial models fordescribing the same spatial scene. This idea motivated us to assess the topologicalinformation that the patterns of each RfDL model conveys. Here we focus on the finest
model RfDL3-12 and consider the mapping from its 1772 patterns to 26 topological

4

Yohei Kurata and Hui Shi

DLine-region relation distinguished by the 9+-intersection [5]. In the 9+-intersection,
topological relations between a DLine D and a simple region R are distinguished by
the presence or absence of intersections between D’s four parts (interior D°, startpoint ∂sD, end point ∂eD, and exterior D–) and R’s three parts (interior R°, boundary∂R, and exterior R–). This information is represented by a bitmap-like icon (Figs. 2a),in which each marked block indicates the presence of the corresponding intersection.
Accordingly, topological DLine-region relations are distinguished by the icon’smarking patterns (Figs. 2a-e). These topological relations capture some fundamental
concepts of motions [5]. Therefore, the mapping from the 1772 RfDL3-12 patterns tothe 26 topological relations will be useful for making qualitative interpretation of themotion patterns represented by RfDL3-12 patterns.
D°R° ∂R R −∂sD∂e DD−(a) move within(b) go across(c) go on the edge of(d) go into(e) go out ofFig. 2. DLine-region configurations and their topological relations, together with thecorresponding concepts of motions [5].

The actual mapping from 1772 RfDL3-12 patterns to the 26 topological DLine-region
relations was derived computationally by a set of rules listed in Appendix. Among the1772 RfDL3-12 patterns, 1351 patterns (76.2%) are mapped to a single topologicalrelation, while the others are mapped to multiple relations (on average 1.49 relations
per RfDL3-12 pattern). For instance, an RfDL3-12 pattern
is mapped to a single
topological relation(Fig. 3a), while

is mapped to three topological relations(Figs. 3b-d). Such ambiguity occurs because if a certain part of the,, andDLine intersects with the region, RfDL3-12 patterns may not specify whether this partintersects with the region’s interior or boundary, while topological relations always do(Fig. 3b-c). Nevertheless, many RfDL3-12 patterns (76.2%) successfully capture thetopological characteristics of DLine-region arrangements without ambiguity.

(a)

(b)

(c)

(d)

Fig. 3. Four DLine-region configurations, together with two icons representing their RfDL3-12
pattern (left) and their topological relations (right).

We also analyzed the mapping under the assumption that the region is convex,
because many landmarks in indoor environments (e.g., tables, carpets, and closets) arerepresented by convex regions. Under this assumption, the following two rules areadded to the rules of mapping listed in Appendix:• if R extends over D’s LI and RI, D° intersects with R°; and• if R extends over D’s En and Ex, D° does not intersect with R–.

RfDL: Models for Capturing Directional and Topological Characteristicsof Path-Landmark Arrangements
5Meanwhile, the number of RfDL3-12 patterns decreases from 1772 to 638 under theassumption, due to the constraint that if R extends over two horizontally or vertically
remote fields, then R also extends over every field between them. Interestingly, at thistime every RfDL3-12 pattern is mapped successfully to a single topological relation.
This indicates that RfDL3-12 can be used as a versatile model for capturing both
directional and topological characteristics of path-landmark arrangements especiallywhen the landmarks are convex. Similarly, we identified that RfDL3-4 and RfDL3-8 also
captures the topological characteristics of DLine-region arrangements very well.

4Conclusions and Current Work

This paper developed RfDL models that distinguished the patterns of spatial
arrangements between a straight DLine and a simple region in R2. Making use of
intrinsic frames centered at the DLine, RfDL models captured the region’s direction as
seen from the DLine. In addition, we revealed that RfDL3-12 captured the topologicalcharacteristics of the arrangements considerably, especially when the region wasconvex. Such versatile models will be useful for the applications that involve both
directional and topological aspects of the space [8], such as the dialogue-based
interface of mobile robots [13]. We are now applying RfDL3-12 for the interpretation ofhuman route instructions, by associating typical concepts of motions seen in such
instructions with the patterns of path-landmark arrangements represented by RfDL3-12
patterns [14]. RfDL3-12 is highly useful for capturing such concepts as “go toward”,“pass … on the right”, “go into”, and “go across”, which concerns the direction or
spatial extent of the region-like landmark as seen from an agent moving on a path.
Acknowledgments
This work is supported by DFG (Deutsche Forschungsgemeinschaft) through theCollaborative Research Center SFB/TR 8 Spatial Cognition – Subproject I3-SharC.
References
1. Denis, M.: The Description of Routes: A Cognitive Approach to the Production of Spatial
Discourse. Current Psychology of Cognition 16, 409-458 (1997)
2. Krieg-Brückner, B., Shi, H.: Orientation Calculi and Route Graphs: Towards Semantic
Representations for Route Descriptions. In: Raubal, M. (ed.): GIScience 2006, LNCS, vol.
4197, pp. 234-250. Springer (2006)
3. Bugmann, G., Klein, E., Lauria, S., Kyriacou, T.: Corpus-Based Robotics: A RouteInstruction Example. In: 8th Conf. on Intelligent Autonomous Systems, pp. 96-103 (2004)
4. Shi, H., Tenbrink, T.: Telling Rolland Where to Go: HRI Dialogues on Route Navigation.
In: Workshop on Spatial Language and Dialogue (2005)
5. Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a
Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposium
on Behavioral Monitoring and Interpretation, pp. 62-76 (2007)

6

Yohei Kurata and Hui Shi

6. Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Frank, A.,
Campari, I., Formentini, U. (eds.): From Space to Territory: Theories and Method of SpatioTemporal Reasoning in Geographic Space, LNCS, vol. 639, pp. 162-178. Springer (1992)
7. Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning Using Orientation, Distance,and Path Knowledge. Applied Intelligence 6, 49-58 (1996)
8. Li, S.: Combining Topological and Directional Information: First Results. In: Lang, J., Lin,F., Wang, J. (eds.): KSEM 2006, LNAI, vol. 4092, pp. 252-264. Springer (2006)
9. Frank, A.: Qualitative Spatial Reasoning: Cardinal Directions as an Example. International
Journal of Geographical Information Science 10, 262-290 (1996)
10.Kurata, Y., Egenhofer, M.: The Head-Body-Tail Intersection for Spatial Relations between
Directed Line Segments. In: Raubal, M., Miller, H., Frank, A., Goodchild, M. (eds.):
GIScience 2006, LNCS, vol. 4197, pp. 269-286. Springer (2006)
11.Schneider, M., Behr, T.: Topological Relationships between Complex Spatial Objects. ACM
Transactions on Database Systems 31, 39-81 (2006)
12.Levinson, S.: Language and Space. Annual Review of Anthropology 25, 353-382 (1996)
13.Mandel, C., Frese, U., Röfer, T.: Robot Navigation Based on the Mapping of Coarse
Qualitative Route Descriptions to Route Graphs. In: IEEE/RSJ International Conference onIntelligent Robots and Systems, pp. 205-120 (2006)
14.Kurata, Y., Shi, H.: Modeling Ontological Concepts of Motions with Two Projection-BasedSpatial Models. To appear in: Gottfried, B. (ed.): 2nd International Symposium on
Behavioral Monitoring and Interpretation (2008)

Appendix: Rules for Mapping RfDL3-12 Patterns to Topological Relations
Let D° and ∂s/e D be the interior and start/end point of a DLine D, and R°, ∂R, and R–
be the interior, boundary, and exterior of a region R, respectively.
• ∂s/e D intersects with only one among R°, ∂R, or R–,• if R does not extend over D’s En/Ex, then ∂s/e D intersects with R–;• if R extends over D’s En/Ex and not all fields around it, then ∂s/e D intersects with∂R (Fig. 4a);
• if R extends over D’s En/Ex and all fields around it, then ∂s/e D intersects witheither R°or ∂R (Fig. 4b);
• if R does not extend over I, D° intersects with R– only; and• if R extends over D’s I, then D° intersects with R°, ∂R, or both, and possibly R– aswell, under the following restrictions:• if R does not extend over D’s En or/and Ex, then D° intersects with ∂R and R–(Fig. 4c);
• if R does not extend over D’s LI or RI, then D° does not intersect with R°;• if R extends over both D’s LI and RI, but not all the fields around En and thosearound Ex, then D° intersects with R° (compare Fig. 4d that satisfies thiscondition with Fig. 4e that does not); and• if D° intersects with both R° and R–, then D° also intersects with ∂R.

(a)

(b)

(c)

(d)

Fig. 4. Seven DLine-region configurations, together with their RfDL3-12 relations.

(e)