![]() To speed up the operations, we assign each vector a number code and derive two iterative formulas using differential calculus. We also prove several theorems guaranteeing the correctness of algorithms. This allows a parallel implementation of each algorithm to be made very easily. Consequently, they process all edges one by one in any order for input polygons. They do not have to sort the vertices clockwise or counterclockwise beforehand. Our algorithms are applicable to any polygon that may be self-intersecting or with holes nested to any level of depth. ![]() Using geometric probability and straight-line equation F ( P ) = ( y i − y i + 1 ) ( x p − x i ) − ( y i − y p ) ( x i + 1 − x i ), it optimizes our two algorithms that avoid the division operation and do not need to compute any intersection points. This also creates the prerequisites and basis for our novel boolean operations algorithm that inherits all the benefits of the serial algorithm. It describes all degenerate cases and simultaneously provides a corresponding solution to each degenerate case to ensure the stability and reliability. The serial algorithm can quickly determine whether a point is inside or outside a polygon and accurately determine the contours of input polygon. So I can go back to my simulation, having once more found that OSM provides the tools I need.This paper provides a full theoretical and experimental analysis of a serial algorithm for the point-in-polygon test, which requires less running time than previous algorithms and can handle all degenerate cases. ![]() Overall the error rate is extraordinarily low given that most OSM contributors are, like me, probably don't do formal checks on the geometry of their data. Many are buildings (400 or so, as seen in the screen-shot above), with the rest more or less evenly distributed between landuse, woodland ( natural=wood) and water ( natural=water). Of these about 80% are self-intersecting and the rest are mainly self-intersecting rings. Great Britain has around 1500 badly formed polygons (based on data from Jan 22) or about 0.2% of the total data. Just another illustration of the rich endowment of the OSM ecosystem. Of course, Jochen Topf and Frederik Ramm thought about this sort of problem long ago and I could instantly see the exact location of the problems, and even click on an icon to start-up Potlatch in the right location. I'd never found a use for these in the past. I left the issue for a couple of days, until, whilst checking some address data, I noticed Geofabrik's OSM Inspector had a set of Geometry validation tools. I had tried the JOSM validator on the data but it did not report any problems, so I was still uncertain if it was a hidden bug in osm2pgsql or a data problem. It's really much better to find the problem at source and resolve it there. Running this on the landuse polygons got rid of the intersections, so problem solved. Even better a quick search found a nifty function called CleanGeometry (link to code here) which I have now installed in my template OSM database on Postgres. A bit of delving in the PostGIS manual led me to the ST_ IsValid and ST_IsValidReason functions. When I tried to perform the clipping in PostGIS the error messages were much more explicit. They were successfully rendered by mapnik. ![]() In all cases the Bingham and Radcliffe polygons could be retrieved and displayed in QGIS but disappeared on clipping. I reimported the data with a different version of osm2pgsql I used an older data set I even rendered the area using a modified version of the OSM mapnik stylesheet (see image to right with the missing polygons highlighted). ![]() I was not at all sure where the problem lay. The image above shows the Harlequin area of Radcliffe with residential landcover (red), but the polygon for the rest of the village has gone. Specifically I noticed that the residential landuse for the two large villages (or small towns) of Bingham and Radcliffe-on-Trent were missing. The polygons get created and load fine, but once I started clipping sets of data I noticed that I was losing some landuse polygons. In using osm2pgsql, I relied on it for conversion of OSM data to polygons in PostGIS. I'd hoped to get further with my Urban Atlas simulation, but have been distracted by badly formed polygons. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |