Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!caen!spool.mu.edu!munnari.oz.au!comp.vuw.ac.nz!cavebbs!frank
From: frank@cavebbs.gen.nz (Frank van der Hulst)
Newsgroups: comp.graphics
Subject: Re: 2d polygon intersection
Keywords: 2d polygon intersection
Message-ID: <1991Jun03.071218.3698@cavebbs.gen.nz>
Date: 3 Jun 91 07:12:18 GMT
Article-I.D.: cavebbs.1991Jun03.071218.3698
References: <1991Jun02.174356.12556@eng.cam.ac.uk>
Organization: The Cave MegaBBS, Public Access Usenet, Wellington, NZ
Lines: 38

In article <1991Jun02.174356.12556@eng.cam.ac.uk> crm@eng.cam.ac.uk (Campbell Middleton) writes:
>The difficulty arises with degenerate cases of overlapping and coicident vertices and obtaining the correct set-theoretic intersection in all possible configurations.

This appears to me to be similar to a problem I had with a floodfill routine,
particularly with a polygon with lines which cross each other. In the routine
I used, I was trying to detect whether any line segments of the polygon crossed
a horizontal line, and if so, where. What I did was,
when I detected two coincident vertices, to backtrack to the previous or next
point of the polygon, and if the line segment from *there* to the other end
crossed my horizontal line, treat it as a crossing at the location of the two
coincident vertices. I used a similar approach for horizontal lines in the polygon.

I realise this is different from your problem, but hope it may spark some ideas
of your own along the same lines.

Frank.
 

>
>Surely someone MUST have such a routine that can handle 2 polygons?
>
>I would be extremely grateful for any help or suggestions with this problem.
>
>Please send replies by email to : 
>
>email address: crm@uk.ac.cam.eng
>   
>    Campbell Middleton   
>    Department of Engineering
>    University of Cambridge
>    Cambridge 
>    United Kingdom


-- 

Take a walk on the wild side, and I don't mean the Milford Track.
Kayaking: The art of appearing to want to go where your boat is taking you.