We propose and implement an algorithm to compute the exact cumulative density function (CDF) of the distance from an arbitrary reference point to a randomly located node within an arbitrarily shaped (convex or concave) simple polygon. Using this result, we also obtain the closed-form probability density function (PDF) of the Euclidean distance between an arbitrary reference point and its neighbor node when nodes are uniformly and independently distributed inside the arbitrarily shaped polygon. The implementation is based on the recursive approach proposed by Ahmadi and Pan [1] in order to obtain the distance distributions associated with arbitrary triangles. The algorithm in [1] is extended for arbitrarily shaped polygons by using a modified form of the shoelace formula. This modification allows tractable computation of the overlap area between a disk of radius centered at the arbitrary reference point and the arbitrarily shaped polygon, which is a key part of the implementation. The obtained distance distributions can be used in the modeling of wireless networks, especially in the context of emerging ultra-dense small cell deployment scenarios, where network regions can be arbitrarily shaped. They can also be applied in other branches of science, such as forestry, mathematics, operations research, and material sciences.

1. Introduction

Wireless networks are generally modeled as a finite region in Euclidean space (this article considers those regions that are simple polygons in two-dimensional Euclidean space ) with nodes independently and uniformly distributed throughout the region. The random distances between nodes or users, therefore, significantly affect the modeling of the wireless network, since the received signal power and interference depend critically on the distances between the transmitter and the receiver nodes [2]. As shown recently in [3], when nodes are independently and uniformly distributed within the network, the important distance distribution is the cumulative density function (CDF) of the distance from an arbitrary reference point to a randomly located node within the polygon (in this article, we use the phrase distance distribution to denote this CDF distribution). It can be obtained by finding the ratio of the overlap area between a disk of radius centered at the arbitrary reference point and the area of the polygon. This CDF can then be used to obtain the probability density function (PDF) of the Euclidean distance between an arbitrary reference point and its neighbor node when nodes are uniformly and independently distributed inside the polygon.

Recently, there has been increasing interest in wireless communications to model the distance distributions in polygonal regions. In traditional cellular networks, the network region is often modeled as an equilateral triangle, a square, a hexagon, or a disk. For regular -sided polygons, the distance distributions were obtained for the special case when the arbitrary reference point is located at the center of the polygon in [4] and for the general case when the arbitrary reference point is located anywhere inside the polygon in [3]. Note that a Mathematica implementation of the algorithm in [4] is available [5]. In emerging wireless network paradigms, such as ultra-dense small cell deployments, the network regions can be arbitrarily shaped. For arbitrarily shaped convex polygons, when the arbitrary reference point is located anywhere inside the polygon, an algorithm to obtain the distance distributions was proposed in [6]. For triangular regions, when the arbitrary reference point is located anywhere, an algorithm to obtain the distance distributions was proposed in [1]. The authors in [1] argued that since any polygon can be triangulated (i.e., broken up into non-overlapping triangles), their approach in principle could be applied to determine the distance distributions for the general case of arbitrary reference point location and arbitrarily shaped (convex or concave) polygons.

In this article, we extend the algorithm in [1] for arbitrarily shaped polygons by using a modified form of the shoelace formula. The shoelace formula, also known as Gauss’s area formula, is a well-known mathematical method to determine the area of a polygon whose vertices are described by ordered pairs in [7]. Our modification of the shoelace formula allows tractable computation of the overlap area between a disk of radius centered at the arbitrary reference point and the arbitrarily shaped polygon, allowing the algorithm in [1] to be generalized and implemented.

This article is organized as follows. In the remainder of Section 1, we briefly summarize the algorithm in [1] and define the commonly used notation. In Section 2, we discuss the shoelace formula and its proposed modification. In Section 3, we present the proposed algorithm and its Mathematica implementation. The simulation results, which are used to verify the analytical results, are discussed in Section 4. An example illustrating the proposed Mathematica implementation is discussed in Section 5. Finally, conclusions are presented in Section 6.

1.1 Overview of Algorithm in [1] for Triangle Regions

Calculating the distance distribution (i.e. the CDF) evaluated at is equivalent to finding the ratio of the area within the polygon that is less than a distance from the reference point to the area of the polygon. The latter area is readily calculated if the polygon vertices are known. (Generally the polygon defining the network area has known coordinates, so the area may be calculated.) Hence, the challenge is calculating the former area.

It is clear that the CDF has an obvious geometric interpretation; if we let be a polygon and be the disc of radius centered at some reference point , then the CDF is the area of divided by the area of the polygon. Ahmadi and Pan [1] perform this calculation for an arbitrary triangle and arbitrary reference point by first establishing the case for which the reference point is one of the triangle vertices, as illustrated in Figure 1.

Figure 1. Depiction of the two characteristic cases considered by Ahmadi and Pan [1]. (a) shows the case that the altitude from to the side is inside the triangle. (b) shows the case that the altitude from to the side is outside the triangle.

They assume, without loss of generality, that the side length of is less than or equal to the side length of . The possible cases are then characterized by whether the altitude from to the side is inside or outside the triangle, and considered separately (see Figure 1). For a disc centered at , the area of intersection of the triangle and the disc as a function of the radius is derived for each case. The result for the former case is

(1)

and for the latter case the result is

(2)

All the symbols in (1) and (2) are defined in Figure 1. The equations (1) and (2) are extended to an arbitrary triangle with an arbitrary reference point using triangle decomposition and adding and subtracting the areas appropriately [1]. The three possible cases are that the reference point is inside the triangle, the reference point is outside the triangle and in the area formed by the extension of two edges from a vertex, or otherwise (see Figure 2). For these three cases, the area is given by

respectively, where the individual intersection areas can be found using (1) and (2) appropriately.

Figure 2. Possible cases for triangle decompositions given an arbitrary triangle and reference point. (a) is the case of an interior reference point. (b) and (c) show the case for an exterior reference point. (c) is the case that the reference point is in the area formed by the extension of the edges from one vertex.

Using this result, an algorithm to compute the CDF for the general case of an arbitrary polygon and arbitrary reference point is proposed and implemented. This is achieved by first establishing a modification of the shoelace formula, which is described and proved in Section 2.

1.2 Definitions

In this subsection, we define some functions and notation that are used throughout this article.

Definition 1

The area of a region is denoted by . In the case of a triangle with vertices , the area can be calculated as in [8].

(3)

Definition 2

The signed area of a triangle with vertices is denoted by , and is given by

(4)

(The subscript stands for “signed”.) We note that from the above definition, has the same magnitude as the area of the triangle, , but is positive if the vertices are given in counterclockwise order, and negative if the vertices are given in clockwise order.

Definition 3

The signed area of the region defined by the intersection of a triangle and a region , that is, , is denoted and is given by

(5)

where is the signum function.

Essentially, this says that , where is positive if the signed area of is positive and negative if the signed area of is negative.

2. Shoelace Formula and Its Modification

The shoelace formula is a useful formula for calculating the area of a polygon (see the illustration in [6] for an explanation of the name). It is stated in the theorem below [9].

Theorem 1

The shoelace formula: Let be an ordered set of vertices in the plane that define an -sided polygon. Define the triangles as the triangles formed from two adjacent points from and the origin. That is,

(6)

where for simplicity we let and .

The shoelace formula holds if instead of using the origin to define each , we used an arbitrary point in .

Notice that

Hence, the shoelace formula can alternatively be stated as

(7)

A visual illustration of (7) is shown in Figure 3. The triangles with positively signed area are shaded in green and shown in (a), and the triangles with negatively signed area are shaded in orange and shown in (b). In both cases, the darker regions indicate where triangles overlap. We can thus think of the shoelace formula as stating that if we add the green regions and subtract the orange regions, we obtain the region defined by the polygon (shown in (c)). In the given example in Figure 3 we can see this visually because the green regions outside the polygon “cancel” with the orange regions outside the polygon, and the dark green regions inside the polygon are “canceled” by orange regions inside the polygon.

Figure 3. Visual illustration of the shoelace formula for calculating the area of a polygon.

We now build upon the shoelace formula in (7) to obtain a useful modification.

Theorem 2

The modified shoelace formula: Let be an ordered set of vertices in the plane that define an -sided polygon. Let be a disc of radius centered at the point . Define the triangles as the triangles formed from two adjacent points from and the reference point . That is,

(8)

Thus, just as the area of the polygon was equal to the sum of the signed areas of the triangles in the original shoelace formula, we have that the area of intersection of the polygon and a disc is given by the sum of the signed areas of intersection of each and the disc in the modified shoelace formula. A visual illustration of this modified formula is shown in Figure 4. If we consider the same example as in Figure 3 but with the addition of a disc, as depicted in Figure 4, then the orange regions (areas with negative signed area, shown in (b)) “cancel” the green regions (areas with positive signed area, shown in (a)) that are outside the polygon and “cancel” the darker regions inside the polygon, giving the desired area of intersection, shown in (c). We prove theorem 2 using induction.

Figure 4. Visual illustration of the modified shoelace formula for calculating overlap areas.

Proof of Theorem 2

We use strong induction on (the number of sides of the polygon). The base case is immediate, as Ahmadi and Pan [1] show exhaustively in their paper. We now assume that the result is true for all for some , and let be an arbitrary -sided polygon. We may choose two vertices , of the polygon such that the straight line joining and is contained within the polygon (for a proof of this fact, see [10]).

To complete the induction step, let and pick any diagonal contained within , where appears before in the list. Then let , where and are the two polygons formed by adding the diagonal. We can thus write and . These two polygons correspond to (a) and (b), respectively, in the example given in Figure 5.

Figure 5. Example polygon decomposition given the diagonal . The arrows denote the order of the vertices.

Since both and have at most sides (say and sides, respectively), then for any and any , we know that for the disc of radius centered on (denoted ), we have

where and are the triangles defined in the same way as in the statement of the theorem for the polygons and , respectively. From their construction, the vertices in and are either both in clockwise order, or both in counterclockwise order. So and are either both positive or both negative. Hence

(9)

But all of the triangles are precisely the analogous triangles for the polygon , and also include the triangles added by the diagonal, namely and . Thus

But and have opposite orientation, so , so that

3. Proposed Algorithm and Implementation

In this section, we extend the algorithm in [1] for arbitrarily shaped polygons by using the modified form of the shoelace formula in theorem 2. Since any polygon can be triangulated, the area of intersection of a disc of radius centered at a reference point and the polygon can be found by summing the areas of the intersections of the disc and each triangle of the triangulation. Since the latter areas can be found using theorem 2, the generalization follows.

3.1 Algorithm

We know that given a polygon and a reference point , the CDF is

(10)

Using the modified shoelace formula, we may write (10) as

(11)

where and

In (11), we can calculate using the shoelace formula in theorem 1. The method to calculate each was given in [1] and is summarized in Section 1.1. Once the CDF is found, the corresponding PDF can be found by differentiation.

3.2 Implementation

In this section, we describe the implementation of the algorithm. The functions in (1) and (2) are implemented as the functions InsideAltitudeArea and OutsideAltitudeArea, respectively. These functions return the piecewise functions (1) and (2) as a function of the argument . Each function returns a list of sublists; here each sublist is of the form , where is the piece of the function that corresponds to the range . The function (1) has four pieces and so InsideAltitudeArea returns a array. Similarly, OutsideAltitudeArea returns a array, as it corresponds to (2), which has three pieces.

The function PolygonArea, given the vertices, calculates the area of a polygon with the shoelace formula.

CombinePieces is responsible for simplifying a “pseudo-piecewise” function by determining the distinct ranges of the equivalent piecewise function, sorting these ranges, and finding the corresponding function for each range. This piecewise function is then converted to either the CDF or the PDF, depending on the argument case. The function takes four arguments: is a “pseudo-piecewise” function of the form that is returned by InsideAltitudeArea and OutsideAltitudeArea, namely, a list of sublists, where each sublist is of the form where is the piece of the function that corresponds to the range . The argument area is set equal to the area of the polygon. The returned CDF is a function of the argument . Finally, case is a Boolean argument that determines whether the CDF or PDF is returned; when it is true the function returns the CDF, and when it is false the function returns the PDF.

This gives the sign of a triangle’s area.

AltitudeInsideQ returns True if the altitude of the triangle intersects the opposite edge inside the triangle.

PolygonCDF is the main function used to compute the CDF; it uses the method outlined in Subsection 3.1.

4. Simulation Aspects

This section discusses how to generate the simulation results, which are used to verify the analytical results. In general, we need uniformly distributed points inside arbitrarily shaped polygons.

Generating uniformly distributed points inside a triangle is straightforward and can be accomplished in a number of ways [11, 12]. The method used here selects two numbers at random from to measure off lengths on two sides of the triangle to use as weights on the vertices. RandomPointsTriangle has two arguments: T is a list of three vertices describing a triangle and n is the number of points to generate.

The method for triangles is extended to arbitrary polygons by triangulating the polygon , uniformly picking a triangle, and then generating a point in that triangle. Uniformly picking a triangle means choosing each triangle with probability such that the points generated are uniform for the whole polygon; this means that the probability of picking a triangle must be proportional to its area. Precisely, the probability is . This is done efficiently using TriangulateMesh.

5. Examples

For convenience, here is a list of the different special examples that have been considered in the literature that can be verified using our implementation. The polygon vertices must be specified in clockwise order.

1. Example 1 in [1]: equilateral triangle with interior reference point

2. Example 2 in [1]: equilateral triangle with exterior reference point.

3. Section 2.5.1, p. 263 in [13]: triangle with reference point at a vertex.

4. Example in [3]: square with reference point on the boundary.

5. Example in [4]: hexagon with reference point at the center.

6. Example in [6], [14], and [15]: arbitrarily shaped convex polygon.

7. Example in [18]: arbitrarily shaped convex polygon.

8. Example in this report: arbitrarily shaped polygon shaped like the letter N.

9. Example in this report: star-shaped (concave) polygon region with reference point at the center.

10. Example in this report: arbitrarily shaped concave polygon with exterior reference point.

We illustrate using Example 10.

The simulation data is calculated. The code checks to see if the polygon is convex. If it is, the points are simulated using RandomPointsConcave, which is faster than RandomPointsPolygon. Otherwise, the code uses RandomPointsPolygon.

This shows the simulated uniformly distributed points for the given polygon.

A function that converts the simulated points to the CDF is defined. The number of simulation trials
is .

The closed form of the CDF is displayed as calculated by the algorithm.

Also find the corresponding closed form of the PDF, which is needed for the neighbor PDF.

The analytical result for the CDF (red) is compared with the result obtained from simulations (blue).

Using the CDF, the PDF of the Euclidean distance between an arbitrary reference point and its neighbor node can be found.

Define the neighbor PDF: equation (12) in [4].

The result can be plotted as follows.

6. Conclusion

In this article, we have reported on the use of Mathematica for distance distribution modeling in wireless networks. We have proposed and implemented an algorithm to compute the exact cumulative density function (CDF) of the distance from an arbitrary reference point to a randomly located node within an arbitrarily shaped (convex or concave) polygon. Examples of how the obtained distance distributions can be used in the modeling of finite-area wireless networks are provided in [6], [15–19]. The distance distribution results can also be applied in other branches of science, such as forestry, mathematics, operations research, and material sciences [13], [20].

Acknowledgments

We would like to thank the anonymous reviewer for his comments, especially for suggesting an efficient method of uniformly distributing points in a triangle. We would also like to thank Ms. Maryam Ahmadi (University of Victoria, Canada) and Prof. Jianping Pan (University of Victoria, Canada) for their constructive feedback, which helped us to further improve the implementation.

References

[1]	M. Ahmadi and J. Pan, “Random Distances Associated with Arbitrary Triangles: A Recursive Approach with an Arbitrary Reference Point,” UVic-PanLab-TR-14-01, 2014. dspace.library.uvic.ca//handle/1828/5134.
[2]	J. G. Andrews, R. K. Ganti, M. Haenggi, N. Jindal, and S. Weber, “A Primer on Spatial Modeling and Analysis in Wireless Networks,” IEEE Communications Magazine, 48(11), 2010 pp. 156–163. doi:10.1109/MCOM.2010.5621983.
[3]	Z. Khalid and S. Durrani, “Distance Distributions in Regular Polygons,” IEEE Transactions on Vehicular Technology, 62(5), 2013 pp. 2363–2368. doi:10.1109/TVT.2013.2241092.
[4]	S. Srinivasa and M. Haenggi, “Distance Distributions in Finite Uniformly Random Networks: Theory and Applications,” IEEE Transactions on Vehicular Technology, 59(2), 2010 pp. 940–949. doi:10.1109/TVT.2009.2035044.
[5]	S. Durrani, J. Guo, and Z. Khalid, “Mathematica and Matlab Software for Computing Distance Distributions,” (May 12, 2015). users.cecs.anu.edu.au/~Salman.Durrani/software.html.
[6]	J. Guo, S. Durrani, and X. Zhou, “Outage Probability in Arbitrarily-Shaped Finite Wireless Networks,” IEEE Transactions on Communications, 62(2), 2014 pp. 699–712. doi:10.1109/TCOMM.2013.122913.130298.
[7]	Wikipedia. “Shoelace Formula.” (Jun 18, 2015) en.wikipedia.org/wiki/Shoelace_formula.
[8]	E. W. Weisstein. “Triangle Area” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/TriangleArea.html.
[9]	E. W. Weisstein. “Polygon Area” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/PolygonArea.html.
[10]	J. O’Rourke, Art Gallery Theorems and Algorithms, New York: Oxford University Press, 1987.
[11]	E. W. Weisstein. “Triangle Point Picking” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/TrianglePointPicking.html.
[12]	G. Turk, “Generating Random Points in Triangles,” in Graphics Gems (A. S. Glassner, ed.), Boston: Academic Press, 1990 pp. 24–28. inis.jinr.ru/sl/vol1/CMC/Graphics_Gems_1,ed_A.Glassner.pdf.
[13]	A. M. Mathai, An Introduction to Geometrical Probability: Distributional Aspects with Applications, Amsterdam: Gordon and Breach Science Publishers, 1999.
[14]	J. Guo, S. Durrani, and X. Zhou, “Performance Analysis of Arbitrarily-Shaped Underlay Cognitive Networks: Effect of Secondary User Activity Protocols,” IEEE Transactions on Communications, 63(2), 2015 pp. 376–389. doi:10.1109/TCOMM.2014.2385065.
[15]	J. Guo, S. Durrani, and X. Zhou, “Characterization of Aggregate Interference in Arbitrarily-Shaped Underlay Cognitive Networks,” Proceedings of IEEE Global Communications Conference (GLOBECOM), Austin, TX: IEEE, 2014. pp. 961–966. doi:10.1109/GLOCOM.2014.7036933.
[16]	M. C. Valenti, D. Torrieri, and S. Talarico, “A Direct Approach to Computing Spatially Averaged Outage Probability,” IEEE Communications Letters, 18(7), 2014 pp. 1103–1106. doi:10.1109/LCOMM.2014.2317740.
[17]	Z. Khalid, S. Durrani, and J. Guo, “A Tractable Framework for Exact Probability of Node Isolation and Minimum Node Degree Distribution in Finite Multi-hop Networks,” IEEE Transactions on Vehicular Technology, 63(6), 2014 pp. 2836–2847. doi:10.1109/TVT.2013.2293580.
[18]	K. B. Baltzis, “Distance Distribution in Convex -Gons: Mathematical Framework and Wireless Networking Applications,” Wireless Personal Communications, 71(2), 2012 pp. 1487–1503. doi:10.1007/s11277-012-0887-9.
[19]	D. Moltchanov, “Distance Distribution in Random Networks,” Ad Hoc Networks, 10(6), 2012 pp. 1146–1166. doi:10.1016/j.adhoc.2012.02.005.
[20]	U. Basel, “Random Chords and Point Distances in Regular Polygons,” Acta Mathematica Universitatis Comenianae, LXXXIII(1), 2014 pp. 1–18. www.emis.de/journals/AMUC/_vol-83/_no_1/_baesel/baesel.html.
R. Pure and S. Durrani, “Computing Exact Closed-Form Distance Distributions in Arbitrarily Shaped Polygons with Arbitrary Reference Point,” The Mathematica Journal, 2015. dx.doi.org/doi:10.3888/tmj.17-6.

About the Authors

Ross Pure is a second-year Bachelor of Engineering (Research & Development)/Bachelor of Science student in the Research School of Engineering, the Australian National University (ANU), Canberra, Australia.

Salman Durrani (SMIEEE, SFHEA, MIEAust) is a Senior Lecturer in the Research School of Engineering, ANU. He has coauthored more than 80 publications to date in refereed international journals and conferences. He currently serves as an editor of IEEE Transactions on Communications. His research interests include wireless and mobile communications, wireless energy harvesting, and synchronization and signal processing on the unit sphere.

Ross Pure
Research School of Engineering
The Australian National University
Canberra, Australia
u5349749@anu.edu.au

Salman Durrani
Research School of Engineering
The Australian National University
Canberra, Australia
salman.durrani@anu.edu.au