# Evaluate minimum points required to define polygons based on an error threshold

I need to build a model or write an algorithm to do this.

here is my cadastral problem: I have plenty of polygons and I need to make a report of coordinations of their vertices. This is pretty easy: I can extract vertices using ArcGIS toolbox and add XY coordinate to each point again using ArcGIS toolbox. However, since each polygon has 20-30 vertices, I need to condense the information. I need to make reports of the most important vertices which define a polygon. The problem here is that these are polygons with irregular shapes. Some can be defined by using 4 points and some require 10 for example. Moreover, my datasets are huge and I definitely need an automated approach to this.

Here is what I thought I have to do:

1) Polygone to vertices > add XY to vertices

2) for each set of polygon vertices use an iterative approach as follows:

2.1) start with 4 vertices

2.2) calculate area

2.3) evaluate area error percentage (area error/correct area = abs(real area-calculated)/correct area)

2.4) if area error < desired threshold (say 0.05)

then end step 2, go to next polygon

else add one vertex, go to 2.2

3) Make a report of selected vertices

However, I have a problem with this. How should I select the correct vertices in step 2.1 and 2.4. For example, a polygon having 20 vertices, may not be defined using 4 of its vertices, while it can be very well defined using another 4 vertices.

I have access to Arcinfo+python, Xtools, and Matlab+Mapping toolbox. I don't know if I have to use Matlab for this problem or not, since I doubt the efficiency of ArcPy in calculation of new polygon areas.

• You mentioned this was cadastral information. Removing vertices will likely violate the shared borders of the cadastral polygons. You'll end up with overlapping polygons or gaps between polygons (theoretically, if you were to recreate polygons from the resultant vertices), unless you're careful to remove the same vertices from adjacent polygons. Is this not a concern for the report you have to create? – user3461 Apr 13 '13 at 13:09
• What is the purpose of this analysis? Would it be beneficial to define each polygon by its centroid? – Aaron Apr 13 '13 at 13:37
• A report in form of a table, should be added to each cadastre map, which contains coordinations of the parcel's critical points. (We produce maps for each parcel separately). However, the reason behind this is not recreating the exact polygons. Prior to using LIDAR, we had smooth parcels which could be defined by using few points. Now parcels have far more details and some are redundant. Nevertheless, we must make map reports with the same map template we were using before: a handful of points should be reported on it. – Edi Gosilbang Apr 13 '13 at 18:56
• @Aaron So the centroids would not be that "representative". The centroids have no "area" information, unless there be no gaps and polygons can be recreated using thiessens. – Edi Gosilbang Apr 13 '13 at 18:57

## 1 Answer

For a different approach to the problem, you can start with the Simplify Polygon (Cartography) tool in your model or ArcPy code. This will handle the simplifications before extracting vertices, meaning only the "critical" vertices will be extracted.

The `error_option` parameter will also allow you to maintain the topology (shared borders) of the polygons if necessary.

• Simplify polygon tool was very useful. "Remove point" method was exactly what I was looking for. It removes vertices from the source polygons and preserves the critical ones. I estimated the total area error to be 0.2%, while the number of vertices is significantly reduced. Since the points are located exactly on the polygon borders, this can perfectly be my representative points. A hint for anyone who reads this in future, you should find the maximum allowable offset value by trial and error. More offset results in less points and higher errors. – Edi Gosilbang Apr 13 '13 at 19:16
• Hi Kevin, Surely it works as it should. But since the reason behind choosing the points is providing some sort of benchmarks for each parcel and some of parcels still have more point than it is needed, I'm looking for a better algorithm. I'm working on it and I will report my progress here and continue exchanging ideas with you guys. – Edi Gosilbang Apr 15 '13 at 6:32
• You could add an iterative step where you reexecute simplify polygon until the points do not change. Realistically, maximum allowable offset should be defineable by a parameter, not just trial and error. Not sure off the type of my head how I would go about figuring out the correct level, but I'll look through some spatial stats ideas on critical bends to see if I can figure that out, – blord-castillo Apr 15 '13 at 13:11
• @blord-castillo I guess the threshold values here (distance and area) are pretty straightforward. The algorithm removes points for each polygon until it reaches the threshold value (That's why I wonder if reiterating the algorithm would remove any other point). Nevertheless, since every polygon has a different area and the error in each polygon is close to the threshold value, the overall error would be surely dependent on average polygon areas. Maybe the threshold should be equal to "average polygon area x desired overall error percentage". – Edi Gosilbang Apr 20 '13 at 5:29
• But as I somehow mentioned earlier, besides being bounded by the overall error, I'm equally bounded with the number of points on my map reports. It might be interesting for you that I feel more like simplifying the convex hull of each polygon, since it gives me "relatively" critical points and in comparison with remove point it may reduce the number of points by a factor of 2 (the total and average area error are now about 11% and on average I yield 5.5 points per polygon instead of 9.9). – Edi Gosilbang Apr 20 '13 at 6:00