crm@eng.cam.ac.uk (Campbell Middleton) (06/03/91)
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 Kingdommg@godzilla.cgl.rmit.oz.au (Mike Gigante) (06/03/91)
Since you are in the UK, you can probably contact Alan Middleditch at the Polytechnic of Central London (School of Engineering and Science) who has worked on robust set operations for (convex) 2d polygons. One reference is in "Theoretcal Foundations of Computer Graphics and CAD" Edited by R.A. Earnshaw. The publisher is Springer (NATO ASI series) Alan lso had a few TRs which I can't lay me hand on just now (moving pains) Mike Gigante ACGC Royal Melbourne Institute of Technology
frank@cavebbs.gen.nz (Frank van der Hulst) (06/03/91)
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.