# Good algorithm to detect "wrong" features in a vectorial coverage

I am working with a bunch of shapefiles. Each shapefile consisting in rectangles with an integer attribute representing the strength of a signal. I serve these vector files as overlays on a base map, applying different colors based on the integer attribute (like a heat map, or a coverage map).

I have a problem with data: it contains "holes". The term "hole" here can be easily explained with an image: That is a screenshot of a portion of my data loaded in QGIS. I've applied a simple style: just use orange for a range of values between X and Y. Otherwise, no color applied.

The white squares surrounded by blue circles are probably measurement errors. Each square represent 250m in the real world. It doesn't really make sense getting a measure of X in a point (i.e.: -55 dbM) and 250 meters beyond a value way lower (or higher), out of the represented range.

So, I'm basically looking for an algorithm to "detect" this pattern: One vector containing a integer value of -10000 (the "anomaly") but surrounded by vectors containing "normal" and coherent values. I want to avoid a simple dumb loop, checking all the vectors based on their position. I manage several GBs of data, and this can take forever.

Is there any known algorithm to detect this kind of problem in vectorial files?

UPDATE: There are some suggestions in comments. But I missed one important part: the space that surrounds the shapefile (the big white space around the shapefile) is considered "water", and a value of "no coverage" is allowed. So, I just need to get rid of the small holes (in blue in the image), but keep the surrounding space unchanged. That makes things more difficult...

This problem should be solved with rasters. So I would merge all the SHPs, then rasterize the resulting SHP in order to have an array of signals, manipulate the resulting raster (Raster calculator or similar) in order to have 1s for good signals and 0s for NoData and bad signals and, finally, apply a 3x3 filter (Laplace) to detect the bad signals with a kernel like this:

``````1/8 1/8 1/8
1/8 -1  1/8
1/8 1/8 1/8
``````

The filtered raster will have 0s where the signal is good, 1s where it's bad. It can be also vectorized again and will clearly show the signals quality. Hope this helps.

• This is a good solution but it might reflect a slight misunderstanding: the attributes of the "good" squares are not constant. (Otherwise, why go to all the bother and not just display the merged polygon once and for all?) Thus, the filter values will be relatively small but usually nonzero at good squares and have extreme values (positive or negative) at bad ones. BTW, an easy way to compute this result--or at least a functionally equivalent one--is to subtract a neighborhood mean from the original grid. That method does not require weighted neighborhoods. Oct 11 '13 at 17:54
• @whuber The attributes of the "good" squares are not constant, however they are included in a range. So they can be normalized using Map Algebra before applying the filter. On the other side, the filtered values would be less than 1 on the boundary of signals, if the external pixels are represented as zeros instead of NoData. Your proposal of subtracting a neighborhood mean is equivalent to the application of my filter, with the exception of the sign. Oct 11 '13 at 20:42
• When polygons are converted to grids, cells outside the polygons are usually left as NoData (null) values; if not, they easily can be. Every raster GIS platform I have met provides a way to ignore NoData values in its filters, so there should not be any significant problem at the edges, either. There is no need to normalize anything: the "bad" cells can be discovered as outliers within the univariate distribution of filtered values. Oct 11 '13 at 21:34
• Sounds promising. Actually, next step of my work was to rasterize the vector data. I thought it would be easier to face this problem using the vector data, but I understand the logic of this solution. I just need to wait the funding to continue with this. Many thanks! Oct 14 '13 at 22:26

How about using a Z score calculation to identify extreme outliers? If you're not familiar with it a Z score is calculated by subtracting the population mean from the raw score and then dividing by the population standard deviation. Here is a link to a more technical description:

http://en.wikipedia.org/wiki/Standard_score

Since a Z score has an average of 0 and standard deviation of 1 it's very easy to identify extreme outliers.

• I was not familiar with it, but I'll check the link. Many thanks! Oct 14 '13 at 22:23