Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!ukc!cam-eng!crm
From: crm@eng.cam.ac.uk (Campbell Middleton)
Newsgroups: comp.graphics
Subject: 2d polygon intersection
Keywords: 2d polygon intersection
Message-ID: <1991Jun02.174356.12556@eng.cam.ac.uk>
Date: 2 Jun 91 17:43:56 GMT
Sender: @eng.cam.ac.uk
Organization: cam.eng
Lines: 18
Nntp-Posting-Host: tw601.eng.cam.ac.uk

I am urgently seeking a program ( preferably in C) that can intersect 2 general (not necessarily convex) 2D polygons. I have approached a number of Universities and software firms without success as all seem to only have such routines tucked away inside a large solid modelling package and not in readily accessible form. Having also found no listings in the literature I resorted to writing a program based on the theory presented in a computer graphics book by an American academic as this purported to presen






t a method for doing such tasks. Unfortunately I have found this riddled with omissions and logic errors and have wasted considerable time trying to correct these.

The difficulty arises with degenerate cases of overlapping and coicident vertices and obtaining the correct set-theoretic intersection in all possible configurations.

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