over the region
R
can be reduced to a curve integral over the
boundary
B
of
R
in the following manner:
∂
∂
−
∂
∂
=
+
∫∫
∫
Q
x
P
y
x y P x Q y
b
d d
d d
R
(30)
For polygons, i.e., closed sequences of
K
straight line seg-
ments
s
k
,
k
= 1, …,
K
, the parametrization of the segment
s
k
(
t
) is:
x
(
t
) =
t
x
k
+ (1 –
t
)
x
k
–1
t
∈
[0,1]
(31)
with the vertices
x
k
and
x
k
–1
of the
k
th
segment
s
k
(edge). The
indices
k
are taken cyclically. Thus,
P x Q y
P x Q y
b
k
k
K
d d
d d
+ =
+
∫
∫∑
=
1
S
(32)
holds for Equation 30.
For the computation of the integral of the function
F
(
x,y
) =
x
m
y
n
over
R
, the function
F
(
x,y
) has to be decomposed
into
∂
Q
/
∂
x
and
∂
P
/
∂
y
according to Equation 30 which cannot
be done uniquely. Table 1 summarizes convenient decomposi-
tions for the required moments, i.e., the area, the centroid co-
ordinates, and the centralized second moments of the region
R
(Steger, 1996b). A decomposition for arbitrary moments can
be found in Steger (1996a).
Integration and using the decompositions listed in Table
1 yields the following formulas. For details please refer to
Steger (1996b). The polygon’s area is:
A
A
A
x y x y
k
k
K
k
k k
k k
=
=
−
=
+
+
∑
1
1
1
2
with
(33)
taking index addition modulo
K
into account. The coordi-
nates of the centroid are:
x
A
A x x
k k k
k
K
0
1
1
1
3
=
+
+
=
∑
(
)
(34)
y
A
A y y
k k k
k
K
0
1
1
1
3
=
+
+
=
∑
(
)
(35)
and the second (non-central) moments read:
γ
xx
k k k k
k
k
K
A
A x x x x
=
+
+
(
)
+
+
=
∑
1
6
2
1
1
2
1
(36)
γ
yy
k k k k
k
k
K
A
A y y y y
=
+
+
(
)
+
+
=
∑
1
6
2
1
1
2
1
(37)
γ
xy
k k k
k k
k k
k k
k
K
A
A x y
x y x y x y
=
+
+
+
(
)
+
+ +
+
=
∑
1
12
2
2
1
1 1
1
1
(38)
The 2×2 matrix
G
= (
γ
..
) of second moments is used below
to compute a polygon’s orientation in 2D which will then be
transformed into 3D space.
Approach
Based on the above concepts, we describe our approach in de-
tail. After the computation of uncertain planes based on given
3D polygons, we explain the subsequent geometric reasoning
consisting of hypothesis generation, statistical testing, and
adjustment.
Uncertainty of Planes
First of all, we determine the plane defined by the
K
vertices
{
X
1
,
X
2
, …,
X
K
} of the planar polygon embedded in 3D. The
plane’s normal vector
A
h
is (Mäntylä, 1988, p. 218)
A
X X
h
k k
k
K
S
=
+
=
∑
( )
1
1
(39)
here in compact vector representation with
X
k
= [
X
k
,
Y
k
,
Z
k
]
and index addition modulo
K
. For boundary representations
defining vertex points by the intersection of three or more
planes, three noncollinear vertices are sufficient, i.e.,
A
h
=
S
(
X
3
–
X
1
)(
X
2
–
X
1
)
(40)
to determine the normal.
For the point
–
defined by the mean coordinates
X
–
of the
vertices
1
, the incidence
–
∈
A
holds. Expressed in homogeneous
coordinates, this reads
X
–
A
= 0 with the 3D point
X
= [
X, Y, Z,
1]
= [
U, V, W, T
]
. Thus the plane’s Euclidean part of reads:
A
h
0
= −
X A
(41)
To determine the moments of the polygon, we rotate the
vertices into a plane
A
″
with
Z
=const for all points, i.e.,
A
″
= [0, 0, 1, –
Z
]
. This can be achieved for instance by means
of the smallest rotation (Förstner and Wrobel, 2016, p. 340)
Q I
= −
+ +
+
+
≠ −
3
1
2
(
)(
)
a b a b
a b
ba
a b
,
(42)
from vector
a
= [0,0,1]
to vector
b
=
N
for the application
at hand. For horizontal planes
N
= [0,0,–1]
holds, and we
use
Q
= Diag([1, –1, –1]) as rotation matrix. The transformed
coplanar points are:
X
″
k
=
Q
X
k
with
Z
″
k
=
Z
(43)
for all transformed points.
The plane
A
″
constitutes a 2D coordinate system and the
polygon’s vertices have coordinates (
X
″
k
,
Y
″
k
). We assume the
polygons to be possibly multiply-connected, i.e., they could
enclose holes. Therefore, we have to distinguish between exte-
rior and potential interior boundaries, often denoted as rings.
With
R
rings representing a polygon, the polygon’s area is:
A
A
r
r
R
=
=
∑
1
(44)
with the signed areas
A
r
according to Equation 33 for each
ring. The centroid coordinates of the polygon, being the nor-
malized first moment, are:
1. This is not to be confused with the centroid
0
of the polygon’s area.
Table 1. Decompositions for the computations of moments
following Steger (1996b).
P
(
x,y
)
Q
(
x,y
)
∂
P
/
∂
y
∂
Q
/
∂
x
area
A
–
y
/2
x
/2
–1/2
1/2
centroid
coord.
x
0
–
xy
0
–
x
0
y
0
0
xy
0
y
second
moments
γ
xx
–
x
2
y
0
–
x
2
0
γ
yy
0
xy
2
0
y
2
γ
xy
–
xy
/4
x
2
y
/4 –
xy
/2
xy
/2
396
June 2018
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
