The problem of point localization in an arbitrary polygon is considered in relation to the problems of geophysics and ecology. An analytical solution to the problem is obtained using mathematical analysis based on the Cauchy's integral formula from the theory of functions of a complex variable. On the basis of the obtained solution a program was developed for data sampling according to a given zoning of water areas, the further development of which will make it possible to assess the ecological state of the marine environment of Ukraine.
The zoning of the Black Sea, especially its
northwestern part, according to various ecological
and geographical processes or performed
according to a certain parameter, has been devoted
to a large number of works, in particular, this can
be found in the literature review of [
Several algorithms are known for solving the
point localization problem in a polygon, the main
of them are ray tracing (counting the number of
intersections), summing angles, point localization
for convex and star polygons, stripe method, chain
method, triangulation detail method, trapezoid
method and others [
Ray tracing is one of the easiest ways to determine whether a point belongs to an arbitrary simple polygon. The algorithm is based on the idea of counting the number of intersections of a ray outgoing from a given point in the direction of the horizontal axis, with the sides of a polygon. If it is even, the point does not belong to the polygon. A problem arises in the algorithm when a ray crosses the vertex of a polygon or an edge that partially coincides with the ray. The method is simple, but generally not recommended.
The summing angle method is also simple. The
algorithm is based on the idea of calculating the
sum of the signed angles formed at a given point
by the endpoints of each edge of a given polygon.
If the sum is close to zero, the point is outside the
polygon, if not, then it is inside. The number of
turns can be calculated by finding the closest
multiple of 2π. The problem with this scheme is
that it includes the square root, inverse cosine,
division, point, and cross product for each edge
tested. However, this method is very impractical,
as it requires calculating expensive operations for
each
edge
(inverse
trigonometric
functions,
square roots, division), and was even called the
"worst algorithm in the world" for this problem
[
Point localization for convex and star polygons can be determined using binary search. For a convex polygon, segments are drawn from an arbitrary point inside it to the vertices of the polygon. Due to its convexity, the polygon will be split into disjoint wedges. Wedges are ordered by polar angle counterclockwise. Then a binary search is applied for the desired wedge. After the wedge is found, it is checked whether the point lies inside the wedge or outside. The target point lies inside the wedge if and only if a right turn is performed. If the turn is left, then the specified point is outside the polygon. A star polygon contains at least one arbitrary point, such that the segment from it to the desired point lies entirely inside the polygon for any vertex from the polygon. This method is quite laborious to implement.
One of the reasons for the wide variety of methods for solving this problem is that each known method, along with its advantages, has its own disadvantages and limitations, which are usually quite significant. Namely, this is the occurrence of exceptional situations, slowness, requirement of convexity, complexity in software implementation.
In [
Cauchy's integral theorem
and
formula from the theory of functions of a complex
variable. This approach was also discussed on the
forums [
From the Cauchy's formula (1) it follows that:
0, 0 ∉ = {2 , 0 ∈
∞, 0 ∈ ∆
However, the final expression obtained in the
indicated
works
[
[
cumbersome calculations or a technical error. To verify this, it is enough to consider an example from these works and check if the point with coordinates (1; 1) falls into the triangular region defined by the points (0; 0), (0; 1), and (1; 0). In this work, the correct expressions for calculating the value of K are obtained using
mathematical analysis, without using special mathematical packages.
The integral in (1) is represented as the sum of two curvilinear integrals of the second kind: = ∫ ∆ Thus, ( , ) ≡
( , ) ( , )
)2]2 −2( − 0)( − 0 )
( , ), so, the first integral in (2) is equal to zero and expression (2) will now take the following form: + ,
(1) (2) = ∫ + ∫
+ ( − 0) Let's find the partial derivatives: = ∫ straight line passing through these two points (segment) has the form:
2 21ℎ where ℎ = ( 10 21 − 21 10), and, therefore, its solution, the form of which after a series of transformations, will be: 0 +
− 1 − 0 + 0 1 − 0 +
0 0 − 0 + 1 0 + 0 − 1
+ 0 0 whence we have the following expressions: = = 2 − 1 2 − 1 ( − 1)+ 1, 2 − 1 2 − 1 ( − 1)+ 1, = 2 − 1 ,
2 − 1 = 2 − 1 .
2 − 1 − 1 = 2 − 1 − 1 2 − 1 ,
2 1 ( − 0)2 + ( 2211 ( − 1)+ 10) (4)
Thus, the integral for side AB will be equal to the following sum: ∫ 1 ( − 0)2 + ( 2211 ( − 1)+ 10)
2 = ∫
2 1 2 + ( 2211 ( − 10)+ 10) , 2 = We will consider the first integral in the last given by the coordinates: (0; 0), (1; 0) and (0; 1), we have the following expression:
It's useful to note that in [
For the test triangular region from [
The considered mathematical method makes it
possible to solve the formulated problem of a
point localization with respect to curvilinear
polygonal regions. So, in studies [
From expression (3), we can obtain the following integral of the function of a complex variable for a parabola from 0 to 1:
( − 0) − ( − 0) ∫ − 0 = ∫ ( − 0)2 + ( − 0)2 =
| = 1 = ∫ 0
1 = ∫ 2 ( − 0)− ( 2 − 0) ( − 0)2 + ( 2 − 0)2
= 2 − 2
0 + 0 ( − 0)2 + ( 2 − 0)2 0
Solving the resulting integral, one can obtain an expression for a given curvilinear side.
The obtained solution (6) of the problem of a point localization in a polygon is quite simple and can be implemented in any suitable programming language, for example, C ++, C #, Fortran, Python. Unfortunately, the author of this work is not aware of another similar analytical method for solving this problem.
Applied to ecological and geographical problems, a program was developed in the C ++ language in the visual object-oriented programming environment Borland C++Builder6, which allows to distribute the coordinates of points and the corresponding values of hydrological and hydrochemical parameters based on the results of monitoring or satellite observations for further analysis of the ecological state of sea waters in specified areas. Within the
The coordinates of the peaks (longitude and latitude) of each water area (polygon) were entered into text files. Also, text files of satellite observation data on temperature, chlorophyll, transparency (longitude, latitude, parameter), as well as monitoring observations were formed in advance. The program first loads the coordinates of the vertices of the polygon. Then the observational data is loaded, a sample is performed over a given area, and the results are written to a new text file.
Further work will be aimed at clarifying the boundaries of these areas, especially coastal water bodies. developing a software package based on the developed program, which includes a database of basic hydrological and hydrochemical parameters for each water body. The database will store a table of polygons with the following columns: identifier, name and coordinates of the polygon. Taking into account the fact that there are a large number of zoning options for the Black and Azov Seas according to various characteristics, it is assumed that the database will be able to provide the user with the ability to store several zoning options. Such a software package will make it possible to assess the long-term dynamics of both average annual and monthly average changes in the parameters of the marine environment, the ecological state, eutrophication trends and the quality of waters of specific water bodies using the complex indicators E-TRIX and BEAST. The author hopes that the results obtained in this work will also find application in geographic information systems.
As a result of the study, the following
conclusions were made:
An analytical solution to the problem of
point localiziation in an arbitrary polygon is
obtained by methods of mathematical analysis
based on the Cauchy's integral formula
As noted in [