# Point Ordering with  Natural Distance Based on Brownian Motion

Authors: Philsu Kim; Hyoungseok Kim
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

We consider a curve reconstruction problem from unorganized point clouds
with noise. In general, the result of curve reconstruction depends on how to select and
order the representative points to resemble the shape of the clouds. We exploit a natural
distance based on a property of one-dimensional Brownian motion to order sample points,
which simultaneously reflect smoothness and nearness of points, so that our algorithm is
able to reconstruct not only simple curves but also nonsimple curves. Numerous examples
show that this algorithm is effective. The natural distance proposed in this paper is able
to play an important role in a variety of fields of measuring the distance of points with
considering direction.


---

## Body

## 1. Introduction

In many engineering fields such as the reverse engineering of geometric models and image processing of medical images, great attention has been shown to the problems of reconstructing a shape from sample points. The curve reconstruction problem we want to discuss in this article plays an especially important role in shape reconstruction problems (see, e.g., [1–4] and references therein) and has also been instrumental in the recent realizations of many algorithms.Curve reconstruction problems can be regarded as the problem of fitting a curve or a familyℱ of curves to an irregularly spaced set 𝒫 of unorganized data points. Most existing techniques for solving the problem can be divided into two categories depending on whether the sample points of 𝒫 are distributed exactly on the family ℱ of curves without noise or are distributed around ℱ with some noise (possibly a point cloud around ℱ). The techniques in the first category can also be classified depending on situations where the curves are either closed or open, either smooth or nonsmooth, and the sample points are distributed either uniformly or non-uniformly and so on. In any case, the techniques in the first category are well developed by many researchers (e.g., see [5–10] and the references therein) and most of these techniques give mathematical guarantees. There are a few algorithms working for uniformly sampled curves such as alpha shape [9], r-regular shape [6], and EMST [11]. There are other algorithms that work for nonuniformly sampled curves such as Crust [5], Nearest Neighbor [8], Conservative Crust [12], Traveling Salesman Path [13], and Gathan [14, 15]. The algorithms provide a sampling condition with respect to geometric properties, which may result in a sample set not natural to human vision.Recently, there are two algorithms which use two important properties of human vision: proximity and smoothness [16, 17]. Although the sample points are non-uniformly distributed, they can well reconstruct open simple and nonsmooth curves because they use several local features such as the mean of the distances and the mean of the angles of already-obtained edges. The creative vision function of VICUR [16] is a mathematical representation with experimental foundation. They considered only proximity and smoothness of the sample points on the Delaunay triangulation. That is, the candidates for the next point are limited to only points adjacent to the last point although the other points may produce smoother reconstructions. Thus, this is not able to reconstruct nonsimple curves and solve the curve reconstruction problem with noise.Even though the second category, handling data points with noise, is closer to practical situations, relatively little research has been carried out on the second category (e.g., see [10, 18–20] and the references therein). Fang and Gossard [10] used a method based on spring energy minimization to approximate an unorganized point set with a curve, which requires a good initial guess to find the solution. Taubin and Ronfard [20] reconstructed a planar curve from unorganized points using an implicit simplicial curve, which is defined by a planar triangular mesh and the values at the vertices of the mesh. Lee [19] proposed an algorithm based on a modified least-squares method and Euclidean minimum spanning tree. This method is not appropriate for curves with self-intersections. Most curve reconstruction algorithms mentioned above are based on the Euclidean distance to compute the proximity and the adjacency without consideration for smoothness, so they do not solve nonsimple curve reconstruction.Assume that the set𝒫 of data points we want to handle fits into the second category. More precisely, let 𝒫={qk=(xk,yk)∈ℝ2:k=1,2,…,n}. As indicated by Dedieu and Favardin in [7], one of the main steps for solving the curve reconstruction problem is to give an order on a subset of 𝒫 to fit a curve interpolating the points in the subset. If we denote the ordered points as p1,p2,p3, and so on, and we assume that p1,…,pi are already ordered, then the central problem is to find a way of reasonably selecting a next successive point pi+1 from a subset 𝒞i⊂𝒫∖{p1,…,pi}, where we assume that the known facts are only the coordinates of points. For the case of the set 𝒫 in the first category, it is sufficient to estimate the angle between the lines for three consequence points, or estimate the Euclidean distance between nested points [7]. However, a separate usage of these two factors (angle and Euclidean distance) is not sufficient in the presence of noise.What we try to do in this paper is to expound a new persuasive measure (called anatural distance) giving a smoothness and closeness between points, and applicable to order the points in the second category by combining naturally two facts: angle and Euclidean distance. The natural distance to pick up the next consecutive point pi+1 from 𝒞i is defined by(1.1)fi(q)=ti(q)+Ksi(q)ti(q),q∈𝒞i,
where (1.2)ti(q)=|piq⃗|cosθ,si(q)=|piq⃗|sinθ,θ=θ(q)=cos-1(pi-1pi⃗·piq⃗|pi-1pi⃗||piq⃗|).
Hereafter, we call ti(q) a time distance, si(q)/ti(q) a standardized probability distance, and K a subjective weight. By taking into account simple properties of Brownian motion, we will interpret a naturalness about the distance fi(q) ordering the points in a subset of 𝒫. In particular, we will show that, the time distance ti(q) is a diffusing time measuring the closeness between points, while the standardized probabilistic distance si(q)/ti(q) is a function of measuring the smoothness between points. Finally, we will show that, under an appropriate lower bound of the subjective weight K, the natural distance fi(q) provides a plausible answer in ordering the points of 𝒫. Also we will provide remarkable results through several figures of numerical experiments.


## 2. Natural Distance

In this section, we will discuss a naturalness for the distancefi(q) defined in (1.1). In order to do this, we must first define a naturalness for a measure between points applicable to order the points. For chosen consecutive points pi-1 and pi which are already ordered, let 𝒞i be a subset of 𝒫 such that for any q∈𝒞i the angle between pi-1pi⃗ and piq⃗ is acute. If a measure μ prefers to pick up the next point pi+1∈𝒞i satisfying the following conditions, then we say that the measure has a naturalness and call it a natural distance. (C.1)
Suppose thatpi and q1,q2,…,qm∈𝒞i are on the same straight line. Then the measure prefers the closest one to the previous point pi among qj, j=1,2,…,m.(C.2)
Suppose thatq1,q2,…,qm∈𝒞i are on the same circle with center pi and the angle between pi-1pi⃗ and piqk⃗, 1≤k≤m, is the smallest angle among those between pi-1pi⃗ and piqj⃗ for all j=1,2,…,m,. Then the measure prefers qk among qj, j=1,…,m as the next point of pi.Two conditions (C.1) and (C.2) are similar to the first and second criterions of [7], respectively. To show a naturalness of fi(q), we will use a simple property of one-dimensional Brownian motion introduced in the following subsection.An easier way to understand Brownian motion is to think of it as a continuous version of the random walk process. As documented in an enormous amount of literature on stochastic processes such as [21, 22], Brownian motion has several properties which explain the irregular motion observed in nature; for example, in two-dimensional space the motion of pollen grains suspended in liquid which does not flow. Among those, we use only the following property throughout this paper. (P.B)
For given timeT, B(T,·) starting at 0 is a random variable normally distributed with mean 0 and variance T, where B(T,·),T≥0 is the Brownian motion process.Roughly speaking, (P.B) means that the set of original points on the real line at time0, which move randomly, becomes the set which is normally distributed with mean 0 and variance T after T time.


### 2.1. A Motivation of the Distancefi(q)

Before proving the naturalness forfi(q), we first explain a motivation of the derivation of fi(q). To do this, we begin with the following interpretation for the set 𝒞i. For two ordered points pi-1 and pi, (i≥2), which were previously chosen, let R(pi-1,pi) be the ray with initial point pi and directional vector pi-1pi⃗ and let L(q,pi-1,pi) be the perpendicular line to R(pi-1,pi) passing through the point q∈𝒞i+1 satisfying (C.1). Also define the signed angle θ  (-π/2<θ<π/2) between pi-1pi⃗ and piq⃗ by (2.1)cosθ=〈pi-1pi⃗,piq⃗〉|pi-1pi⃗||piq⃗|,
where the sign of θ is positive if q is located on the left-hand side of R(pi-1,pi) and is negative on the right-hand side. Here, 〈·,·〉 denotes the inner product in R2. Define two functions ti:𝒞i+1→R+ and si:𝒞i+1→R by (2.2)ti(q)=|piq⃗|cosθ,si(q)=|piq⃗|sinθ.The functionti(q) is the Euclidean distance between pi and the intersection of R(pi-1,pi) and L(q,pi-1,pi), and the function |si(q)| is the Euclidean distance between q and the intersection of R(pi-1,pi) and L(q,pi-1,pi). Then we can consider the pair (ti(q),si(q)) as the new coordinates representation of q (see Figure 1).Figure 1
New coordinates for a scattered pointq with θ>0 when i=2.With the property (P.B) of Brownian motion, we further think of theti-axis as the time axis with the original point pi, and si-axis as the axis representing the value of Brownian motion. Therefore, if ti(q)=t>0, si(q) is considered as a sample point of the random variable which has the normal distribution with mean 0 and variance t as shown in Figure 2, then we consider the point q as one of the normally distributed points after t time, which is randomly diffused from original point.Figure 2
The distribution of Brownian motion after timet=t2(q).With this setting, we want to find a functionF providing the distances between pi and candidate points of pi+1, which prefer to choose a point q∈𝒞i+1 satisfying the conditions (C.1) and (C.2) where F has the minimum value. Then what is suitable for variables of F? We suggest two factors as variables of F.We adopt the functionti, called ithtime distance, as its first variable. The condition (C.1) in the previous section requires that F should be strictly increasing for ti. This implies that we prefer to choose the point taking the smaller diffusion time to pi+1.Similarly thinking, one may take the function|si| as the second variable of F. As shown in Figure 3, the probability density p satisfies that, for arbitrary ϵ>0 and two points q,q'∈𝒞i+1 such that ti(q)=ti(q')=t and |si(q)|>|si(q')|, (2.3)∫N(si(q),ϵ)p(t,0,s)ds<∫N(si(q'),ϵ)p(t,0,s)ds.Figure 3
The probabilities of theϵ-neighborhoods of two points q,q' for i=2.However, the functionsi is not enough as the second variable of F because it is not independent of the first variable ti. Assume that q,q'∈𝒞i+1 are the points having different reaching times, that is, ti(q)≠ti(q'). Since si(q)(si(q')) is interpreted as a sample point of the random variable with a normal distribution with variance ti(q)(ti(q'),resp.), we cannot compare the probability in the same way as above. For this reason, it is necessary to standardize random variables with normal distributions with the variance ti to be the standardized random variable with normal distribution with the same mean and the variance 1. So we adopt the function |si|/ti as the second variable of F. We call this function ithstandardized probability distance. Easily speaking, if we ignore the effect of the ith time distance, we think that the original point pi is more naturally attainable to q' than q whenever |si(q′)|/ti(q′)>|si(q)|/ti(q) (see Figure 4). The condition (C.2) in the previous section requires that F should be strictly increasing for this second variable, though this is not a sufficient condition for (C.2).Figure 4
Standardizations ofsi(q) and si(q') when i=2.Consequently, our problem is rewritten as the following, ifF is assumed to be C1.Chooseq∈𝒞i+1 satisfying the conditions (C.1) and (C.2) where the suitable (still undetermined) C1-function
(2.4)F(ti(q),|si(q)|ti(q))
has the minimum value. Here the function F(x,y):R+×R+∪{0}→R+ strictly increases for both variables, that is, Fx>0 and Fy>0.There are plenty of such increasing functionF with two variables. Among all, the simplest one will be the linear function of the form (2.5)F(x,y)=x+Ky,
for a positive constant K. This is mostly caused by the convenience of calculation, but the function has several good features as the solution for the point ordering problem. The reader can check these, exploring some examples in the next section.In this spirit, we define theithnatural distancefi  (i≥2) by, for q∈𝒞i+1 and a positive constant K,(2.6)fi(q)=ti(q)+K|si(q)|ti(q).
We call K the subjective weight, since it represents how much weight is given to the second factor.


### 2.2. Naturalness offi(q)

To prove the naturalness offi(q), we need to make some technical assumptions. Choosing points on the same level curve is problematic, where the points have the same natural distance from pi. If points lie on the same level curve with a different Euclidean distance from pi, we choose the closest point from pi to the Euclidean distance. Also, if two points lie on the same level curve with the same Euclidean distance from pi, we choose the point lying on the right-hand side of the direction pi-1pi⃗.Theith natural distance fi has the following properties, which can be easily checked.(P.1)
Ifq1 lies in the interior of the level curveti+K(|si|/ti)=fi(q), then fi(q)>fi(q1),(P.2)
Iffi(q)<ti(q2), then fi(q)<fi(q2),(P.3)
If23fi(q)3/2/9K<|si(q3)|, then fi(q)<fi(q3),(P.4)
Ifq4 lies on the level curve ti+K(|si|/ti)=fi(q), then fi(q)=fi(q4).Some of these can be used to simplify numerical algorithms ordering the points. Hereq,qj∈𝒞i+1 for j=1,2,3,4 (see Figure 5). (P.1) implies that the level curves do not intersect each other in (ti,si)-plane, so the natural distance fi(q) satisfies (C.1). (P.3) is derived by the fact that the maximum value of the level curve ti+K(|si|/ti)=fi(q) is 23fi(q)3/2/9K. In the following theorem, we will show that the natural distance fi(q) locally satisfies (C.2).Figure 5
The level curve passing through a pointq for i=2.Theorem 2.1.
Assume that(2.7)K>(2783+483)1/4r0
for some fixed positive r0. Then the natural distance fi(q) satisfies the condition (C.2).Proof.
To show (C.2), it is enough to show that, for any fixedc>0 and 0<r<r0, the system of equations
(2.8)x2+y2=r2,x+Kyx=c
has at most one root in the first quadrant x>0,  y>0.
The second equation of (2.8) gives the equation y2=x(x2-2cx+c2)/K2. Hence from the first equation of (2.8), we have
(2.9)g(x)=K2r2,whereg(x)=x(x2+(K2-2c)x+c2).
Thus, it suffices to prove that two curves y=g(x) and y=K2r2 meet at most one point in the first quadrant x>0,y>0. Note that, if the cubic function g(x) has three zeros, all of them must be less than zero because x2+(K2-2c)x+c2=(x-c)2+K2x>0, and hence g(x)>0 provided x>0. In this case, the intersection of two curves y=g(x) and y=K2r2 on the first quadrant x>0,y>0 is at most one.
First, assume thatg(x)=0 has only one zero at x=0. If the quadratic equation g'(x)=0 does not have solution or has negative solutions, then g(x) is a strictly increasing function for x>0, and hence the system has at most one root. Therefore the only case that has to be considered is the case
(2.10)K2<(2-3)c,orequivalentlyc>(2+3)K2.
Note that, in this case, the quadratic equation g'(x)=0 has two distinct positive solutions
(2.11)x1=2c-K2-X3,x2=2c-K2+X3,
where X=c2-4cK2+K4, and the minimal extreme value of g(x) is obtained at x2. Using the relation g'(x2)=0, we can derive
(2.12)g(x2)=-29x2(K4-4cK2+c2)-19c2(K2-2c)=-29x2X2-19c2(K2-2c)=127(-2X3+2c3+K2(15c2-12K2c+2K4)).
From (2.10) it can be easily verified that X has the maximum value c. So g(x2) is bounded such as
(2.13)g(x2)≥K227(15c2-12K2c+2K4)≥83+48327K6.
The last inequality is derived from c>(2+3)K2. Hence if the inequality
(2.14)r2K2≤83+48327K6,orequivalentlyK>(2783+483)1/4r,
holds, then the proof is complete.From Theorem2.1, we know that points lying on the same level curve with the same Euclidean distance to the points should be located symmetrically with respect to the ti-axis. Thus if there exist such points, then there are only two in N(pi,r0).Now, we need to make a practical remark concerned with Theorem2.1. As seen in its proof, the lower bound for K is not obtained optimally, so we conjecture that this bound can be smaller in most cases. For practical usage of our method, we think that it is not inevitably necessary to give a consideration for the bound, since the purpose of our point ordering is to construct (or reconstruct) meaningful shapes (or the original shape) after connecting all ordered points. For this reason, in the following experiments, we are not concerned with the lower bound for K on using the natural point ordering method.Before closing this section, we remark on the effect of the subjective weightsK on the point orderings. It is obvious that, if K is very big, the ith natural distance fi is more sensitive to magnitudes of the changes of the ith standardized probability distance |si|/ti than those of the ith time distance ti. This fact can be checked in Figure 6, which presents the level curves of (2.6) for several values of the subjective weight K. As K increases, the width between the line si=0 and level curve becomes narrower.Figure 6
Level curves for various subjective weightsK.


## 2.1. A Motivation of the Distancefi(q)

Before proving the naturalness forfi(q), we first explain a motivation of the derivation of fi(q). To do this, we begin with the following interpretation for the set 𝒞i. For two ordered points pi-1 and pi, (i≥2), which were previously chosen, let R(pi-1,pi) be the ray with initial point pi and directional vector pi-1pi⃗ and let L(q,pi-1,pi) be the perpendicular line to R(pi-1,pi) passing through the point q∈𝒞i+1 satisfying (C.1). Also define the signed angle θ  (-π/2<θ<π/2) between pi-1pi⃗ and piq⃗ by (2.1)cosθ=〈pi-1pi⃗,piq⃗〉|pi-1pi⃗||piq⃗|,
where the sign of θ is positive if q is located on the left-hand side of R(pi-1,pi) and is negative on the right-hand side. Here, 〈·,·〉 denotes the inner product in R2. Define two functions ti:𝒞i+1→R+ and si:𝒞i+1→R by (2.2)ti(q)=|piq⃗|cosθ,si(q)=|piq⃗|sinθ.The functionti(q) is the Euclidean distance between pi and the intersection of R(pi-1,pi) and L(q,pi-1,pi), and the function |si(q)| is the Euclidean distance between q and the intersection of R(pi-1,pi) and L(q,pi-1,pi). Then we can consider the pair (ti(q),si(q)) as the new coordinates representation of q (see Figure 1).Figure 1
New coordinates for a scattered pointq with θ>0 when i=2.With the property (P.B) of Brownian motion, we further think of theti-axis as the time axis with the original point pi, and si-axis as the axis representing the value of Brownian motion. Therefore, if ti(q)=t>0, si(q) is considered as a sample point of the random variable which has the normal distribution with mean 0 and variance t as shown in Figure 2, then we consider the point q as one of the normally distributed points after t time, which is randomly diffused from original point.Figure 2
The distribution of Brownian motion after timet=t2(q).With this setting, we want to find a functionF providing the distances between pi and candidate points of pi+1, which prefer to choose a point q∈𝒞i+1 satisfying the conditions (C.1) and (C.2) where F has the minimum value. Then what is suitable for variables of F? We suggest two factors as variables of F.We adopt the functionti, called ithtime distance, as its first variable. The condition (C.1) in the previous section requires that F should be strictly increasing for ti. This implies that we prefer to choose the point taking the smaller diffusion time to pi+1.Similarly thinking, one may take the function|si| as the second variable of F. As shown in Figure 3, the probability density p satisfies that, for arbitrary ϵ>0 and two points q,q'∈𝒞i+1 such that ti(q)=ti(q')=t and |si(q)|>|si(q')|, (2.3)∫N(si(q),ϵ)p(t,0,s)ds<∫N(si(q'),ϵ)p(t,0,s)ds.Figure 3
The probabilities of theϵ-neighborhoods of two points q,q' for i=2.However, the functionsi is not enough as the second variable of F because it is not independent of the first variable ti. Assume that q,q'∈𝒞i+1 are the points having different reaching times, that is, ti(q)≠ti(q'). Since si(q)(si(q')) is interpreted as a sample point of the random variable with a normal distribution with variance ti(q)(ti(q'),resp.), we cannot compare the probability in the same way as above. For this reason, it is necessary to standardize random variables with normal distributions with the variance ti to be the standardized random variable with normal distribution with the same mean and the variance 1. So we adopt the function |si|/ti as the second variable of F. We call this function ithstandardized probability distance. Easily speaking, if we ignore the effect of the ith time distance, we think that the original point pi is more naturally attainable to q' than q whenever |si(q′)|/ti(q′)>|si(q)|/ti(q) (see Figure 4). The condition (C.2) in the previous section requires that F should be strictly increasing for this second variable, though this is not a sufficient condition for (C.2).Figure 4
Standardizations ofsi(q) and si(q') when i=2.Consequently, our problem is rewritten as the following, ifF is assumed to be C1.Chooseq∈𝒞i+1 satisfying the conditions (C.1) and (C.2) where the suitable (still undetermined) C1-function
(2.4)F(ti(q),|si(q)|ti(q))
has the minimum value. Here the function F(x,y):R+×R+∪{0}→R+ strictly increases for both variables, that is, Fx>0 and Fy>0.There are plenty of such increasing functionF with two variables. Among all, the simplest one will be the linear function of the form (2.5)F(x,y)=x+Ky,
for a positive constant K. This is mostly caused by the convenience of calculation, but the function has several good features as the solution for the point ordering problem. The reader can check these, exploring some examples in the next section.In this spirit, we define theithnatural distancefi  (i≥2) by, for q∈𝒞i+1 and a positive constant K,(2.6)fi(q)=ti(q)+K|si(q)|ti(q).
We call K the subjective weight, since it represents how much weight is given to the second factor.


## 2.2. Naturalness offi(q)

To prove the naturalness offi(q), we need to make some technical assumptions. Choosing points on the same level curve is problematic, where the points have the same natural distance from pi. If points lie on the same level curve with a different Euclidean distance from pi, we choose the closest point from pi to the Euclidean distance. Also, if two points lie on the same level curve with the same Euclidean distance from pi, we choose the point lying on the right-hand side of the direction pi-1pi⃗.Theith natural distance fi has the following properties, which can be easily checked.(P.1)
Ifq1 lies in the interior of the level curveti+K(|si|/ti)=fi(q), then fi(q)>fi(q1),(P.2)
Iffi(q)<ti(q2), then fi(q)<fi(q2),(P.3)
If23fi(q)3/2/9K<|si(q3)|, then fi(q)<fi(q3),(P.4)
Ifq4 lies on the level curve ti+K(|si|/ti)=fi(q), then fi(q)=fi(q4).Some of these can be used to simplify numerical algorithms ordering the points. Hereq,qj∈𝒞i+1 for j=1,2,3,4 (see Figure 5). (P.1) implies that the level curves do not intersect each other in (ti,si)-plane, so the natural distance fi(q) satisfies (C.1). (P.3) is derived by the fact that the maximum value of the level curve ti+K(|si|/ti)=fi(q) is 23fi(q)3/2/9K. In the following theorem, we will show that the natural distance fi(q) locally satisfies (C.2).Figure 5
The level curve passing through a pointq for i=2.Theorem 2.1.
Assume that(2.7)K>(2783+483)1/4r0
for some fixed positive r0. Then the natural distance fi(q) satisfies the condition (C.2).Proof.
To show (C.2), it is enough to show that, for any fixedc>0 and 0<r<r0, the system of equations
(2.8)x2+y2=r2,x+Kyx=c
has at most one root in the first quadrant x>0,  y>0.
The second equation of (2.8) gives the equation y2=x(x2-2cx+c2)/K2. Hence from the first equation of (2.8), we have
(2.9)g(x)=K2r2,whereg(x)=x(x2+(K2-2c)x+c2).
Thus, it suffices to prove that two curves y=g(x) and y=K2r2 meet at most one point in the first quadrant x>0,y>0. Note that, if the cubic function g(x) has three zeros, all of them must be less than zero because x2+(K2-2c)x+c2=(x-c)2+K2x>0, and hence g(x)>0 provided x>0. In this case, the intersection of two curves y=g(x) and y=K2r2 on the first quadrant x>0,y>0 is at most one.
First, assume thatg(x)=0 has only one zero at x=0. If the quadratic equation g'(x)=0 does not have solution or has negative solutions, then g(x) is a strictly increasing function for x>0, and hence the system has at most one root. Therefore the only case that has to be considered is the case
(2.10)K2<(2-3)c,orequivalentlyc>(2+3)K2.
Note that, in this case, the quadratic equation g'(x)=0 has two distinct positive solutions
(2.11)x1=2c-K2-X3,x2=2c-K2+X3,
where X=c2-4cK2+K4, and the minimal extreme value of g(x) is obtained at x2. Using the relation g'(x2)=0, we can derive
(2.12)g(x2)=-29x2(K4-4cK2+c2)-19c2(K2-2c)=-29x2X2-19c2(K2-2c)=127(-2X3+2c3+K2(15c2-12K2c+2K4)).
From (2.10) it can be easily verified that X has the maximum value c. So g(x2) is bounded such as
(2.13)g(x2)≥K227(15c2-12K2c+2K4)≥83+48327K6.
The last inequality is derived from c>(2+3)K2. Hence if the inequality
(2.14)r2K2≤83+48327K6,orequivalentlyK>(2783+483)1/4r,
holds, then the proof is complete.From Theorem2.1, we know that points lying on the same level curve with the same Euclidean distance to the points should be located symmetrically with respect to the ti-axis. Thus if there exist such points, then there are only two in N(pi,r0).Now, we need to make a practical remark concerned with Theorem2.1. As seen in its proof, the lower bound for K is not obtained optimally, so we conjecture that this bound can be smaller in most cases. For practical usage of our method, we think that it is not inevitably necessary to give a consideration for the bound, since the purpose of our point ordering is to construct (or reconstruct) meaningful shapes (or the original shape) after connecting all ordered points. For this reason, in the following experiments, we are not concerned with the lower bound for K on using the natural point ordering method.Before closing this section, we remark on the effect of the subjective weightsK on the point orderings. It is obvious that, if K is very big, the ith natural distance fi is more sensitive to magnitudes of the changes of the ith standardized probability distance |si|/ti than those of the ith time distance ti. This fact can be checked in Figure 6, which presents the level curves of (2.6) for several values of the subjective weight K. As K increases, the width between the line si=0 and level curve becomes narrower.Figure 6
Level curves for various subjective weightsK.


## 3. Practical Algorithm

In this section, we will describe a practical algorithm for ordering points in an unorganized point cloud as well as a sample point set.Let𝒫 be a set of arbitrarily scattered n points in R2. The point ordering problem aims to choose a family 𝒮={𝒫̃j} of subsets of 𝒫, where each subset 𝒫̃j is a well-ordered set satisfying the natural conditions (C.1) and (C.2). Assume that p1j,p2j,…,pmj are already ordered so that we may denote that 𝒫̃j=[p1j,p2j,…,pmj] with the last point pmj and the direction pm-1jpmj⃗. We define the connectivity tmj of an ordered subset as the mean of the lengths of edges of the ordered subset: tmj=(1/(m-1))∑l=1m-1dlj, where dlj is the distance between plj and pl+1j.We explain a process for computing the set of candidates for the next point and choosing the next point among the candidates, calledNextPointFinder. Let N(pmj,rmj) be a neighborhood with center pmj and radius rmj=atmj satisfying the following condition: (3.1)N(pmj,rmj)={q∈ℛ:d(pmj,q)≤rmj},
where ℛ is the remaining point set such that ℛ=𝒫∖⋃l=1j𝒫̃l and a is a parameter. We define the candidate set 𝒞m by (3.2)𝒞m={q∈N(pmj,rmj):pm-1jpmj⃗·pmjq⃗>0}
as shown in Figure 7. We find out the point pm+1j among the elements of 𝒞m such that fm(pm+1)=minq∈𝒞m{fm(q)}.Figure 7
The candidate points ofpm+1j are in the right half-disc 𝒞m with center pmj and radius rmj.There is a main difference between our method and VICUR [16] in the process. Our method permits all of points q∈𝒞m as a candidate for pm+1 whether [pm,q] is a Delaunay edge or not, whereas VICUR considers only the points q, where [pm,q] is a Delaunay edge. We think that it plays a role of a key to solve a nonsimple curve reconstruction problem.In order to deal with the first category problem, we assume that there is no noise in the point set𝒫.NADIAS (NAtural DIstance based Algorithm for Sample points)
Step 1.
Compute Delaunay triangulationDT(𝒫).Step 2.
Let𝒫̃j be the jth local solution generated by NextPointFinder. Let ej=[p1j,p2j] be the shortest Delaunay edge in ℛ. Apply NextPointFinder with the last point p2j and the direction p1jp2j⃗ until the candidate set is empty. Let 𝒫̃j+ be the solution of this process. Apply NextPointFinder with the last point p1j and the direction p2jp1j⃗ until the candidate set is empty. Let 𝒫̃j- be the solution of this process. Merge the two subsets 𝒫̃j+ and 𝒫̃j- into 𝒫̃j, that is, 𝒫̃j=𝒫̃j+∪𝒫̃j-. Update 𝒮=𝒮∪{𝒫̃j}. Update ℛ=𝒫∖⋃l=1j𝒫̃l.Step 3.
If|ℛ|>1, then repeat Step 2.Step 4.
If|𝒮|>1, then apply the following bridging process to a pair of 𝒫̃i and 𝒫̃j of 𝒮: for two ordered subsets 𝒫̃i=[p1i,p2i,…,pli] and 𝒫̃j=[p1j,p2j,…,pmj], if the distance between p1i (or pli) and p1j (or pmj) is less than the average of the connectivity tli and tmj, then our algorithm connects these two ordered subsets.Step2 says that our algorithm follows a type of an incremental greedy approach: at each step it chooses the next point from among the candidate points that is best under the natural distance, including “close to the last point” and “in the direction of current travel”. The bridging process is similar to the curve-curve connectivity of [16] and makes our method reconstruct curves with sharp corners.The time complexity of our algorithm isO(nlogn), where n is the number of the input points because the dominant process of our algorithm is to compute Delaunay triangulation of them and it runs in O(nlogn). The main process of our algorithm is NextPointFinder which is repeatedly to find out a candidate set 𝒞i, and to select one point that has the minimum natural distance among the candidates. It takes O(kM), where k is the number of the output points in P̃ and M is a constant.For the second category problem, we outline our algorithm as follows.NADIAC (NAtural DIstance based Algorithm for Cloud points)
Step 1.
Compute Delaunay triangulationDT(𝒫).Step 2.
Choose a pointp1∈𝒫. Compute a neighborhood N(p1,rc), where rc is a constant radius. Apply Principal Component Analysis to N(p1,rc) in order to obtain the initial direction ID⃗ which plays a role of the major principal axis in the neighborhood.Step 3.
Apply NextPointFinder with the last pointp1 and the direction ID⃗ until the candidate set is empty. Let P+̃ be a local solution generated by NextPointFinder.Step 4.
Apply NextPointFinder with the last pointp1 and the direction -ID⃗ until the candidate set is empty. Let P-̃ be a local solution generated by NextPointFinder.Step 5.
P̃=P+̃∪P-̃.


## 4. Experimental Results

In this section, we tested several reconstruction problems where each problem is focused on the following facts: (1) nonsimple curve from sample points, (2) sharp corners from sample points, (3) the difference between Natural distance and Euclidean distance, (4) the effect of the subjective weight K, and (5) the treatment of cloud sets.Figure8 shows that our method can reconstruct a nonsimple curve from sample points. Figure 8(a) is the Delaunay triangulation of the sample points. In order to explain the difference between VICUR [16] and our method, we zoom in the Delaunay triangulation as shown in 8(b). The adjacent points to P are A, B, and C, whereas Q is not adjacent to P. So VICUR does not permit Q as a candidate for the next point of P although the edge PQ is smoother to the already-ordered edge OP than the other Delaunay edges. On the other hand, our algorithm deals with all of four points as candidates for the next point of P since they belong to the neighborhood of P with radius a·t, where t is its connectivity and a=2.5 is set. Figure 8(d) shows a nonsimple curve reconstructed by our method. The red point in Figure 8(d) means the initial point of our algorithm.Nonsimple curve reconstruction: (a) Delaunay triangulation, (b) enlarged Delaunay triangulation at the dense area, (c) reconstructed curve generated by [16], and (d) reconstructed curve generated by our method.
(a)(b)(c)(d)Figure9 shows another example for a nonsimple curve from sample points as shown in Figure 9(a). In this example, we choose the initial point as that having a minimum edge length between points. In Figure 9(b), the boundary point between red line and green line is the chosen initial point. Thus, our algorithm works in two opposite directions. Figures 8 and 9 are smooth nonsimple curves.Nonsimple curve reconstruction: (a) sample points and (b) result by NADIAS.
(a)(b)Figure10 shows the process of our algorithm, called NADIAS (NAtural DIstance based Algorithm for Sample points). Figure 10(a) is an example for sample points on a piecewise smooth curve. For the sample data, NADIAS finds out the shortest Delaunay edge and then applies NextPointFinder process two times with opposite directions. Figure 10(b) shows the result which has two components of smooth curves. The boundary of the red line and the green line is the initial point of the first component, and the boundary of the black line and the blue line is one of the second component. Figure 10(c) is the result after our bridging process. This figure contains one component because the minimum distance between the end points of two components is smaller than the given threshold distance. Figure 11 shows that NADIAS is able to well extract the several components whether or not each component is open and whether or not its shape is sharp.The process of NADIAS: (a) sample points, (b) NextPointFinder, and (c) bridging.
(a)(b)(c)Examples with multicomponents.
(a)(b)(c)There are two different results of point ordering for the same set of sample points by using Euclidean distance and Natural distance in Figure12. The ordered set with Euclidean distance in (a) does not contain all sample points, contrary to that with natural distance in (b). It implies that there is an example in which parameters can be chosen for the natural point ordering that will reconstruct the curve, while parameters chosen for Euclidean distance may not.Point orderings based on the different distance measures.
(a)
Euclidean distance [5](b)
Natural distanceIn Figure13, the complicated examples for three different subjective weights are presented. For the set of scattered sample points in (a), the case K=0.5 of (c) produces a meaningful closed curve of `@' almost completely. One also finds the fact that, as K increases, our method produces smoother shapes. Figures 13(b) and 13(c) are generated by the first algorithm which regards the point data as sample points, so there are two curves. On the other hand, Figure 13(d) shows the result of the second algorithm. K is very large, so the smoothness is emphasized more than the proximity. Therefore the algorithm meets the stop condition before most of points are applied to the algorithm.A complicated example using the natural point ordering method.
(a)
sample data(b)
K=0.3(c)
K=0.5(d)
K=3.0Figure14 shows a more meaningful example of the natural point ordering problem. The sample data are generated by drawing a spiral and then adding three small circles to the spiral. One may understand that the major configuration of the dataset is a spiral. Our natural point ordering method can cut out the minor configurations such as three small circles from the spiral, so the ordered set is only on the spiral.Extraction of the major configuration: sample points (a) and the result (b) withK=0.8.
(a)(b)Figure15 shows the results of NADIAC for point clouds. The cloud data of a spiral type are generated by random process and the clouds of the right example are generated by drawing a nonsimple curve in several times. Although the set of sample points is unorganized, our natural point ordering algorithm can extract the ordered subset from the point cloud, which plays a role of representative in their local neighborhood.Natural point orderings for point clouds: a point cloud generated by random process (a), a point cloud generated by drawing with mouse (b).
(a)(b)


## 5. Conclusion

We have presented a new method for constructing curves from unorganized point clouds with noise. In general, the result of curve reconstruction depends on how to select and order the representative points to resemble the shape of the clouds. In this paper, in contradiction to the previous curve reconstruction algorithms based on Euclidean distance, we exploit a natural distance to reflect orientation to the ordering of sample points, so that our algorithm is able to reconstruct not only simple curves but also nonsimple curves. Moreover, for unorganized point clouds, this method efficiently extracts the skeletons of the clouds by cutting out the outliers, even though the result by our method is sensitive to the initial point and the initial direction. The method may be extended in two ways. The first thing is to extend the method to the surface reconstruction problem in three-dimensional space. We think that one should use the properties of two-dimensional Brownian motion in order to get a natural distance similar to that in this paper. Second, it is possible to improve our method which can control the subjective weightK to obtain the wanted shape. We conjecture that this can be fulfilled if we weaken the condition (C.1).



---

*Source: 450460-2010-05-03.xml*