What is a border point?

Earlier postings considered how to define the degree of intersection between two PCs. Needless to say, that previous and also this treatment is valid for both 2D and 3D, although 2D is used to create a plane of communication. 

Just like a property of inhabiting an intersection of two PCs, one can design a degree of 'insiderness' or 'borderliness' to points in a solo PC, and then smooth the result a bit. A handy insidedness measure was to count, how many natural neighbors of a point (center one in the Fig. below) are from the same set. Below (again) is an image of a measure $0\le\lambda'(p)\le 1$, which is naturally granular, e.g. the midmost situation has $\lambda'(p)=2/5$. Points from the own set are counted against points in the natural neighborhood: \[ \lambda'(p)= \frac{|NN(p,A\cup B) \cap A|}{|NN(p,A\cup B)|}\], where $NN(p,A)$ was a set of natural neighbors of $p\in A$. Note that the set $A$ is blue and the set $B$ is green.

Naturally, one could make this measure somewhat 'more continuous' by e.g. counting the halves of triangle tip angles: \[ \lambda'(p)= \frac{\sum_{t\in C} \alpha_{p,t}}{4\pi} \], where
$C= \{t\in T\,|\, p\in t, 2 \le |t\cap A|\}$ holds to all triangles, which contain $p$ and least one $a\in A$. (In 3D, the denominator is $8 \pi$ The denominator $4\pi$ is because we end up counting twice too much of angular mass. A drawing below illustrates this a bit. When $t= (a,b,p)$, $\alpha_{t|p}$ is the tip angle marked with one arc. Likewise, when $t=(b,c,p)$, the corresponding tip angle is marked with two arcs. Now, point $b$ 

has a presence $(\alpha_{(abp)|p}+\alpha_{(bcp)|p})/2$, not the whole sum of tip angles of both triangles.  

This raises a question: what about the border points? They do not have a full 360$^o$ neighborhood. And that is a trigger to this posting: how to define border points and a degree of 'being a border point'. There is no other set $B$ now helping to judge the star neighborhoods of points.   

 

An approach is to imitate alpha shapes algorithm, and eliminate from a Delaunay triangulation those triangles, which have an edge longer than a certain threshold. The above figure illlustrates the approach. Having $l_0=mean_{e\in E} \|e\|$ the mean length of edges $e\in E$ in a Delaunay triangulation $G= (A,E,T)$ of a PC $A$, one can define a relative edge pruning limit $\chi$ so that the maximum allowed edge length equals $\chi l_0$. Let's math-verbalize it: \[E':= \{e\in E\,|\, \|e\| \le \chi l_0(E')\}.\]
The self-referental measurement of $l_0$ from the resulting set $E'$ is just a notational inconvenience. the real implementation triggers usually none or only one reiteration. Choosing a large $\chi$ makes the triangulation smooth and solid, forming almost a convex profile. A small $\chi$ fragmentates the triangulation. This way we get an almost continuous sortiment of boundary shapes and boundary points.

But how to choose a correct $\chi$? There is a criterion, one can measure the number of border points per each $\chi$ and stop in a convenient moment depending the application in mind. E.g., one may need the above blue shape to be relatively solid from inside, so that $\chi$ is chosen just before holes are there. A generic choice with no special needs can be automated: observe the number of border points $|partial A|$ and/or the lenggth of the silhouette. Here is a summary when experimenting with the same PC as shown previously.

The effect of $\chi$ to two border descriptors and mean distance $l_0$.

In this case $\chi= 2.2...2.4$ is a good choice, since the decline of the number of border points changes and especially the border length and point distance are stabilized there for some time. And as the age-old saying of geomorphologists goes: A useful feature shows stability over a significant range of scale. (Even the scale in this case is logically somewhat mixed rejection limit $\chi l_0$.

Now, it is time to reveal one borderliness measure: at how wide range of distance scales a point is a part of the silhouette line? This is computationally cheap since one does not need to do but one Delaunay triangulation (with a cost $\mathcal{O}(n\log n)$) and order triangles by their largest edge lengths (with a cost $\mathcal{O}(n\log n)$). The last step is an $\mathcal{O}(n)$ removal of the triangles.
 

Border points are recorded over a range of $\chi$ and the last occurrence as a border point registers the limit $\chi$ value of the point. E.g. the yellow points are border points at $\chi< 4.5$, when the isolated stripe at right starts to get ripped off. It gets completely cut off at $\chi= 3.4$. A final 'borderliness' $b(p)$ os a point $p\in A$ could be given as scaled to the $\chi$ interval:\[ b(p)= \frac{\chi_{cutoff}(b) - \chi_{min}}{\chi_{max}-\chi_{min}}\]. If the tendency of a point to stay a part of border is high, the 'borderliness' is high. The definition also binds the borderliness to the scanned scale used. 

This is just one way of defining a border and an intrepid reader may come up with many other definitions. So why to bother? And there are PC NN methods which could learn these concepts and start to produce better judgements than any of these individual definitions.  And that is the point... We need to understand a concept and be able to provide various definitions (read: 'labelings' or gold standards) for NN's to learn, and hopefully, to generalize.

PS: There is one little detail omitted here: how to detect when a point is at a border of a given triangularization. There are variations of 'drunken walker' algorithm, which are good for a 2D case, but are somewhat loopy and hairy in 3D. To cover also 3D, one should use counting angular view $\omega$ from a point to its neighborhood: \[ \omega(p)= \sum_{t\in T(p)} \omega_{t|p}\], where $T(p)= \{t\in T\,|\, p\in t\}$ is the triangular star neighborhood of $p$ (those triangles or tetrahedra it belongs to) and $\omega_{t|p}$ is a spatial (or planar angular) view to $t$ fro $p$. A point is on a border if $\omega(p) < 4\pi$ (3D) or $\omega(p) < 2\pi$ (2D).