A more precise polygon_overlap()

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

This might be a possible fit:
http://www.magic-software.com/Applications.html
(see "Boolean operations on 2D polygons. Based on BSP trees" near the
bottom of the page).

The license agreement might be acceptable. I'm not a lawyer, so I can't
be sure how free it really is to use from reading this:
http://www.magic-software.com/License/free.pdf

It would probably be good to contact the author.
http://www.magic-software.com/CompanyInfo.html

See http://www.vividsolutions.com/jts/jtshome.htm for a robust set of
algorithms in Java which do all the spatial predicates (the 3x3
Egenhofer matrix). Also union, difference, and buffer. It is licenced
LGPL. Also see PostGIS (http://postgis.refractions.net) (licenced GPL)
for a set of PostgreSQL GIS objects. We are currently working on porting
JTS algorithms to C++ for use in PostGIS.

P.

Dann Corbit wrote:

This might be a possible fit:
http://www.magic-software.com/Applications.html
(see "Boolean operations on 2D polygons. Based on BSP trees" near the
bottom of the page).

The license agreement might be acceptable. I'm not a lawyer, so I can't
be sure how free it really is to use from reading this:
http://www.magic-software.com/License/free.pdf

It would probably be good to contact the author.
http://www.magic-software.com/CompanyInfo.html

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/users-lounge/docs/faq.html

--
__
/
| Paul Ramsey
| Refractions Research
| Email: pramsey@refractions.net
| Phone: (250) 885-0632
\_