> -----Original Message-----
> From: Kenneth Chan [mailto:kkchan@technologist.com]
> Sent: Wednesday, May 22, 2002 12:24 PM
> To: pgsql-hackers@postgresql.org
> Subject: [HACKERS] A more precise polygon_overlap()
> 
> 
> Gents,
> 
> I am looking for a more precise polygon overlap test and any 
> comment/pointers/suggestions are appreciated.  Attached is 
> the modified poly_overlap in geoops.c.  
> 
> If the polygons pass the bounding box check, the following 
> tests will be carried out.  The tests are terminated as soon 
> as one of them returns true:
> 
> 1) At least one of the vertex in polygon a is inside polygon b
> 2) At least one of the vertex in polygon b is inside polygon a
> 3) At least one edge of polygon a intersects with an edge on polygon b
> 
> All these tests could be expensive for polygons with lots of 
> vertices.  Would anyone know where I can find information on 
> a more efficient way of determining polygon overlap.  
> 
> Efficiency aside, is there anything obivious I have missed 
> which could lead to an incorrect result?
> 
> The end game for me is to be able to test if a path enters a 
> polygon and this is a first step as I am new to postgresql.  
> Looks like postgresql converts the path to a polygon and call 
> poly_overlap(), which could lead to incorrect result.  At 
> some stage, I might add an overlap operator that accepts a 
> path and a polygon.

For convex polygons, it is very simple.  Unfortunately, most polygon's
don't fall into that category.  For polygons of arbitrary shape, it is
an incredibly complex problem.  This is a very good article on the
subject:

"On Local Heuristics to Speed Up Polygon-Polygon Intersection Tests"

by:

Wael M. Badawy
Center for Advanced Computer Studies
University of Southwestern Louisiana
Lafayette, LA 70504
wmb@cacs.usl.edu

Walid G. Aref
Department of Computer Sciences
Purdue University
West Lafayette, IN 47907
aref@cs.purdue.edu
A link to the above paper is here:
http://www.cs.purdue.edu/homes/aref/spdb.html


The big problems come from:
1. polygons which are self intersecting
2. polygons that have holes

Here is a paper one one sort of idea:
http://www.me.cmu.edu/faculty1/shimada/gm97/24700b/project/venkat/projec
t/

Here is a list of links that may prove helpful:
http://citeseer.nj.nec.com/aref95window.html

The most general method I know of is the Weiler-Atherton polygon-polygon
clipping algorithm.
Here is some stuff on it:
http://www.cs.buffalo.edu/faculty/walters/cs480/NewLect10.pdf


Here is a fun one:
+-------------------+
|                  /|
|  +--------------+ |
|  |     /\       | |
|  |    /  \      | |
|  |   /____\     | |
|  |              | |
|  +--------------+ |
|                   |
+-------------------+

A triangle lives in a box.  The upper right hand corner of the box has
an enclave. Detail:

---------------------+ +
                    / /|
                   / / |
                  / /  |
                 / /   |
                / /    |
               / /     |
              / /      |
             / /       |
            / /        |
           / /         |
          / /          |
         / /           |
        / /            |
-------+ +             |
         |             |
         |             |
         |             |


The point of the triangle on the top nearly touches one line of the
enclosing box.  To answer questions about interesection are tricky even
with a simple example like this.  When the polygons are
self-intersecting, it can be even more outrageous.

Wed, 22 May 2002 13:45:50 -0700
"Dann Corbit" <DCorbit@connx.com>
Re: A more precise polygon_overlap()