Re: A more precise polygon_overlap()

> -----Original Message-----
> From: Kenneth Chan [mailto:kkchan(at)technologist(dot)com]
> Sent: Wednesday, May 22, 2002 12:24 PM
> To: pgsql-hackers(at)postgresql(dot)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(at)cacs(dot)usl(dot)edu

Walid G. Aref
Department of Computer Sciences
Purdue University
West Lafayette, IN 47907
aref(at)cs(dot)purdue(dot)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.