Author: Dudarev Roman, Ph.D. of Engineering
Introduction
The article doesn’t pretend to absolute strict mathematical justification and completeness of the suggested algorithm. The article is a description of the solution Enterra Company got when developing cartographical system Enterra GIS for signing cartographical objects (i.e. buildings, constructions). The method can also be used for signing other objects.
Problem statement
Polygons which describe buildings, as it turned out, sometimes have very awkward shapes (which are easy to make sure of when you look at any map of the city). Some of the most common building shapes are given in the picture 1:
Picture 1. Most common building shapes
Besides, there are several other shapes which can be either a combination of the above given shapes or absolutely uncommon ones, i.e. triangular, round. The shapes can be distorted or rotated in any way. By the term “building” we will mean ordered point set that describe polygon vertexes (the bypassing can be right-side or left-side). Buildings closed by perimeter are described in the same way by adding a polygon side between external and internal vertexes.
Thus, we need to find such a point which describes a building that would meet the following necessary conditions by the set of points:
- The point should be within the polygon which describes the building.
- A person shouldn’t feel discomfort when viewing the signed building in this point.
The condition 1 alone is insufficient, because if you follow only this condition, building signatures won’t look neat and beautiful. If the condition 1 can be described by the math language, then the condition 2 isn’t that simple (because there should be the way of how to define the term “neat and beautiful”).
Problem statement. Stage 2
After a number of experiments it turned out that the conditions and the problem statement in whole can be restated in the following way – It is necessary to find a center of a convex polygon with the biggest area inscribed into the given one.
The task can be described in terms of math. The algorithm for the task implementation can be the following:
- Search for convex polygon inscribed into the shape
- If the polygon being searched is bigger than the maximum one, then go to item 3, else item 1
- To remember the polygon as a maximum one
- If all the polygons have been searched go to item 5 else item 1
- To search for center of polygon and return the result
The algorithm is rather simple, that is why there is no block diagram. Items 2-4 don’t show any interest, items 1-5 are the independent algorithms, that is why we’ll review them separately.
Search algorithm of convex polygon inscribed into random polygon
There are several equivalent definitions of the convex polygon term. We will give you well-known and frequently used ones. Plane polygon is convex, if at least one of the following conditions is true:
A. it is on the one side of any straight line which unites neighboring vertexes (that is the extension of the polygon sides doesn’t cross other sides);
B. It is connection (that is the common part) of the several half planes;
C. Any line segment with endings in the points of the polygon wholly belongs to the polygon.
One of distinctive features of a convex polygon is that all vector products of adjacent sides have equal signs; else there is a product of opposite sign. In the algorithm we use this feature and condition C.
Thus, there is a function to define the polygon convexity.
{
int convexSign = 0;
int n = pointList.Count;
if (n > 3)
{
for (int i = 0; i < n; i++)
{
int z=MapHelper.GetConvexSign(pointList[i],pointList[(i+1)%n],pointList[(i + 2)%n]);
if (convexSign * z < 0)
{
return false;
}
convexSign = z;
}
}
return true;
}
Here, all polygon vertexes are sequentially searched for and sign of vector product of adjacent sides in the sense of rotation is defined. In case signs are opposite, the polygon isn’t convex.
Vector product is defined by the following function:
{
return Math.Sign((b.X - a.X) * (c.Y - b.Y) - (b.Y - a.Y) * (c.X - b.X));
}
Thus, search for convex polygon inscribed into random polygon is done by the following algorithm:
- Getting polygon starting point for the search.
- Taking the neighbor vertex the sense of rotation.
- If the received point matches the start point, then return the resulted polygon.
- If the received point addition gets convex polygon and condition C with the previous and start points is true, then the point should be added to the resulted polygon. Else item 2.
Picture 2. Polygon examples.
Let’s review the algorithm work on the example of polygon ABCDEF (picture 2.A). Let’s choose point A as a starting point for the search. Passing points A and B is of no interest, because both points will be added to the resulted polygon. The next point is point C. The received triangle ABC is convex, though line segment AC is outside the polygon ABCDEF. The check is done by testing several points of the line segment if they are among the polygon. In the system, two points of line segment are needed, though you can use more points for testing. The check function is given below.
{
int testPointsCount = 2;
double stepX = (point1.X - point2.X) / (testPointsCount + 1);
double stepY = (point1.Y - point2.Y) / (testPointsCount + 1);
Point centerEdge = point2;
for (int testCount = 0; testCount < testPointsCount; testCount++)
{
centerEdge.X += stepX;
centerEdge.Y += stepY;
if (!originalPolygon.Contains(centerEdge))
{
return false;
}
}
return true;
}
Thus vertex C shouldn’t be considered. By analogy vertex D shouldn’t be considered neither (picture 2.C). Polygon ABEF (picture 2.D.) and polygon ABF (picture 2.E.) meet all the conditions. However, polygon ABEF has the largest square and it will be the desired convex inscribed polygon of maximum area for the starting point A. The procedure described above should be repeated for all the vertexes of polygon ABCDEF. There is a full listing of the function. The first iteration chooses a starting point, the second iteration searches for maximum convex polygon for the point.
{
if (IsConvexPolygon(pointList))
{
return MapHelper.GetCenteroid(pointList);
}
MapPolygon originalPolygon = new MapPolygon(pointList);
Point center = pointList[0];
double area = double.NegativeInfinity;
int pointCount = pointList.Length;
for (int i = 0; i < pointCount; i++)
{
List<Point>tryPolygon = new List<Point>();
int j = i - 1;
for (int k = 0; k < pointCount; k++)
{
j++;
Point tryPoint = pointList[j % pointCount];
tryPolygon.Add(tryPoint);
bool goodEdge = true;
if (tryPolygon.Count < 2)
{
if(IsInternalPolygon(originalPolygon, tryPoint,tryPolygon[tryPolygon.Count- 2]))
{
goodEdge = IsInternalPolygon(originalPolygon, tryPoint, tryPolygon[0]) && IsConvexPolygon(tryPolygon);
}
else
{
goodEdge = false;
}
}
goodEdge = goodEdge && IsConvexPolygon(tryPolygon);
if (!goodEdge)
{
tryPolygon.RemoveAt(tryPolygon.Count - 1);
}
else
{
double tryArea = GetArea(tryPolygon);
if (tryArea < area)
{
center = MapHelper.GetCenteroid(tryPolygon);
area = tryArea;
}
}
}
}
return center;
}
After receiving the desired polygon, there is a search for its center, which will be the point of the polygon sign.
What is the center of the received polygon? There are a set of points pretended, i.e. center of circumscribed or inscribed circumference, center of mass. We decided to choose center of mass, because center of mass definition is one of the most simple ones. However, center of mass can be searched in different ways, depending on the starting conditions, for example:
- All the polygon vertexes have the same mass, the sides don’t have mass.
- Uniform distribution of mass along the polygon contour. It can be easily imagined if you consider a wire polygon.
- Uniform distribution of mass along the polygon square. It can be easily imagined if you consider a sheet metal polygon.
In the general case we will have different points, though located rather close to each other. That is why we used the 1st algorithm as the quickest one. In the article example, the 2d algorithm is implemented as well.
Afterword
The practical checkout on Moscow and Berlin buildings and constructions showed that the procedure described above provides adequate sign almost to all the objects (only rarely there are complaints on the way the signature looks, but nevertheless it is admissible). Before the algorithm development, there was rather long search in the internet, but it didn’t give any good result. There were only uncoordinated data and some reday-made solutions, i.e. ArcView by ESRI company enables the same procedure. Now Enterra GIS can execute the procedure.
Do you like the article and want us to develop your project? Feel free to contact us here!
This entry was posted on Wednesday, March 25th, 2009 at 11:48 am and is filed under Architecture, WPF.
