Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have to query polygons that intersect with one another. Our polygons occasionally contain intersections that aren't intended (meaning just a few vertices cross boundaries). I want to filter out these anomalies.

My current algorithm is to take the intersection of the two shapes and compare the area of the intersection with the area of the original polygon. If the intersection area is 1/16th the original, I'm considering it valid for our business rules.

I have found sdo_intersection to be very slow (~30 seconds for 50 records). I'm performing this operation against a national landgrid so the process runs for several days.

I've already fine-tuned my algorithm to exclude polygons with the 'inside' relationship and just work on the ones that I know have overlapbdyintersect.

Any ideas on how to make this faster. At the end of the day, I want to know if there is any significant overlap between two polygons (not just a few vertices crossing over).

share|improve this question
1  
What if a polygon A is overlapped by two other larger polygons (B and C) such that the total amount of A that is overlapped is 1/10 (1/20th from B and 1/20th from C). And since B and C are larger than A, they would be overlapped by A < 1/20th too. Seems like you would still want to catch that case. –  Kirk Kuykendall Jan 20 '11 at 20:43
    
In SQL Server slow intersection queries are often a sign that no spatial index has been added to the geometry column, or the spatial index uses non-optimal parameters. –  geographika Jan 27 '11 at 15:12
    
The geometry column has a spatial index. In Oracle, you can't perform most geometric operations without a spatial index. As far as optimizing the parameters, I'll try to see if I can make it more efficient. With the benchmarking I've done, my bottleneck is not finding intersections, but calculating 1/16 of the intersected area after I've found a relationship. The sdo_intersection function is what is so slow. –  Jordan Parmer Jan 28 '11 at 14:17
add comment

1 Answer

up vote 1 down vote accepted

I would preprocess your polygon set, applying the rule using only the rectangular extent first.

It is very easy to calculate the area of a rectangle, and fairly easy to obtain the bounding rectangle of an arbitrary polgyon.

If the area of the union of the two extents is 1/16 or more of the area of the subject extent, put them on the list of polygon pairs to compare.

EDIT: This will only work well for simple regular polygons... long, diagonal polygons or crescents will have a large rectangular extent but very small area, so will get skipped when they should be analyzed.

share|improve this answer
    
This is a good suggestion. If I take the intersection of the MBRs as opposed to the union, it gives me what I want (even with crescents and narrow polygons). –  Jordan Parmer Jan 20 '11 at 22:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.