Re: A more precise polygon_overlap() - Mailing list pgsql-hackers

> -----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.