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