home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!spool.mu.edu!olivea!mintaka.lcs.mit.edu!ai-lab!fiber-one!sundar
- From: sundar@fiber-one.ai.mit.edu (Sundar Narasimhan)
- Newsgroups: comp.graphics
- Subject: Re: Polygon-polygon intersection
- Message-ID: <1iadoeINN2hj@life.ai.mit.edu>
- Date: 4 Jan 93 22:29:34 GMT
- References: <7418@tivoli.UUCP> <1993Jan4.195436.2889@cis.uab.edu>
- Sender: sundar@fiber-one (Sundar Narasimhan)
- Reply-To: sundar@ai.mit.edu
- Organization: MIT Artificial Intelligence Laboratory
- Lines: 34
- NNTP-Posting-Host: fiber-one.ai.mit.edu
-
- |> In article <7418@tivoli.UUCP> twb@tivoli.com (Tom Bereiter) writes:
- |> >I'm looking for an efficient test for whether two 2D polygons intersect.
- |> >The brute force approach seems to be: do a point-in-polygon test for each
- |> >point of polyA in polyB, but if that says false you still have to check for
- |> >line intersections. This feels like the sort of problem, like area of
- |> >a polygon, which has a non-obvious trivial answer.
- This seems to come up repeatedly, and it DOES have a simple answer,
- (simple, oh no, there's that word again :-) -- maybe this should be in the
- FAQ.
-
- Polygon intersection can be reduced to point in polygon in linear time.
- Basically convolve A & B, reducing A to a point and growing B by the
- corresponding amount. Now test if the reference point of A is within the
- grown B. In 2-D the convolution of two polygons is still a polygon, and in
- 3-D two polyhedra convolved will give another polyhedron and the problem
- reduces to point in polyhedron.
-
- Note that in 2-D a polygon has 3 degrees of freedom. Thus, if only one
- of your polygons is moving, you can construct a convolution in 2+1D
- and test for intersection extremely fast just given the moving polygon's
- configuration.
-
- I have code to do this which I am presently using for my thesis, but I
- can strip out the convolvers if you are desparate. (In 2-D my algorithm
- is essentially that of Guibas et al. the reference to whose paper, I've
- included below).
-
- %Y Conference
- %A Guibas, L., Ramshaw, L., and Stolfi, J.
- %T A Kinetic Framework for Computational Geometry
- %J Proc. of the 24'th Annual IEEE Conference on the Foundations of Computer Science
- %C Tucson
- %P 100-111
- %D 1983
-