gres
not
lish
lent
s of
vise
oint
r to
>, OT
ntal
sing
rical
n of
uter
ition
e of
two
ong
an’s
mity
> the
have
on of
nder
ough
each
tion.
a of
the
sure.
deas,
nong
tural
song
ns of
other
ising
rgera
osed
stical
Luo
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
and Hancock (2002) have associated to this methodology a
Procrustean criterion for the solution of an alignment problem
between configurations with a different number of vertices.
Anyway, concerning the specific GIS and cartographic aspects,
and the CAD/CAM related ones, the reported references do not
provide a complete and satisfactory solution for the problem of
identification of the correspondence between two or more sets
of point coordinates. The above studies, in fact, have very
general purposes, and give a correspondence solution also in the
Case of very dissimilar configurations: consequently, these
methods are inadequate for the correspondence problem
solution.
2. THE PROPOSED METHOD
The described procedure makes it possible to automatically
recognise a given geometrical entity, represented by a finite
number of vertices, into a more complex configuration, that can
completely, or just partly, correspond with the entity taken into
account. In more detail, the method allows both to identify and
put in relation the single couples of homologous points of two
representations of the same entity, and to establish the
correspondence among points belonging to such entity and
those ones belonging to the geometric configuration enclosing it
entirely. For the two situations, the procedure just requires the
knowledge of the vertex coordinates of the geometrical entities
in the respective Cartesian reference systems. Therefore, the
procedure can operate without the need that the points be
acquired, or defined, according to a pre-fixed order, and also
without the knowledge of any structural or topological
information required to totally or partially characterise the
connections among the various vertices.
The procedure foresees two distinct operational sequences
according to the kind of the problem treated. In one case the
process carries out the recognition of the homologous points of
two correspondent representations of the same geometrical
entity, in a very simple and direct way, independently of the
assumed coordinate system and of the reciprocal scale factor. In
the second case the process solves the inclusion problem by
means of a more general methodology, capable to identify a
geometrical configuration completely contained within another
one, more complex and more extended, also in the case in
which the approximate knowledge of the mutual scale factor is
not available.
For both situations, the method is conceived on the use of
mainly algebraic and geometric rules, and on the use of basic
mathematical functions, chosen aiming to a fast and efficient
software implementation.
2.1 The comparison case
The comparison problem considers generic — point
configurations, describing in the various cases, geometrical
entities of the specific application fields (cartographic, CAD,
GIS and so on). The comparison problem rises when:
- the geometrical entities considered are both composed of n
points of known coordinates;
- the correspondence is bi-univocal: therefore each point of one
configuration finds a correspondent in the other, and vice versa.
These conditions are necessary and sufficient: for the
geometrical entities taken into account, further information is
not required, like for instance the value of the mutual scale
factor or the criterion by which the points are listed. For this
procedure, each entity is represented by a geometrical
configuration of points, without any information of structural or
topological kind; every configuration is uniquely described by
9°
its vertex coordinates in a proper and independent 2D or 3D
Cartesian reference system. If the geometrical configurations do
not have axes or planes of symmetry. for which not unique
solutions might happen, the procedure makes it possible to
specify the correspondences between homologous points, also
in the presence of errors in the coordinate values of the
considered vertices.
Before describing in detail every phase, it is necessary to
premise some definitions, useful in the following explanations.
Let us define “rigid link“ the segment joining two vertices (u,
v) arbitrarily chosen, of a same configuration C. If C is
characterised by 7 vertices, it follows that every vertex v
belonging to C has r-1 rigid links defined with respect to the
remaining vertices. Let us write as /;. the i rigid link referred to
the vertex v, and also the length of the same link.
Let us call "ordered set of rigid links* of the vertex v the
following set: I. = {/,., by. ... lay) with Z, € lj. jj, and with i
& m2.
Let u and v be two vertices belonging to a generic configuration
C of n points; let |, € I. be the respective ordered sets of the
rigid links. Furthermore, let us define "homologous rigid links
unconformity" of the vertices u and v the following value:
nl
A = II, ES [| = S zT |
i=]
with 7, € I, and 7, € I,
To each vertex v of a configuration C it can be associated a “ser
of asymmetry distances that assumes the following form:
D, ede sd
n-2) f
with d; — ae el els ini. n-,
2.1.1 The direct method: Once defined the necessary tools, let
us pass to the procedure description. The only available data for
solving the comparison problem are the vertex coordinates
characterising the geometrical configurations A and B, listed in
the respective and homonymous matrices.
An initial test tries to single out possible symmetrical axes. If
symmetrical configurations are present, the comparison problem
will be solved by the alternative general procedure, since there
exists the possibility of not univocal solutions.
The successive phase foresees the computation of the unknown
scale factor. The estimate of the scale factor s that joins B to A
is given by:
trace(A WA)
trace ( B'WB)
where W = Lj'ijj' is applied to centre the original point
coordinate values into their respective systems, j = [401
is the unit vector of dimension equal to the number of points
contained in A (or B), and I is the identity matrix.
The scale factor can be removed pre-multiplying the point
coordinates of the configuration B by the scalar s.
The next step is to look for a particular vertex in one of the two
configurations, for example in A. This is named “point of
maximal asymmetry", and identified with the symbol ;4. Since
the coordinate values are affected by errors, it is necessary to fix
a "significant" threshold (A); the value of A, computed
according to the length of the rigid links present in A, depends
on the fixed tolerance values, or on the entity of the errors
characterising the coordinates.
Now let v be any vertex of A. Let us call *index of significance
Of v" (1,,) the number of elements belonging to D, having a
men
aise
x
im
a
SR gE
