jorice@maths.tcd.ie (Jonathan Rice) (05/28/91)
As part of an algorithm I'm doing, I need to intersect two convex polygons in 2D to yield a third polygon. The vertex order in the original polygons must be able to be both clockwise, both counterclockwise or one clockwise and the other counterclockwise. Yes, it shouldn't be *that* hard, and there *must* be some algorithm from the 60s or 70s which does it, but I haven't been able to find any references on the specific problem. I suppose a modified clipping algorithm would work, but I'd rather not reinvent the wheel. One solution which I can easily implement is to scan-convert the two polygons and then process the scan-line definitions: For each scanline, startx := max(startx1,startx2), stopx := min(stopx1,stopx2). All I need the intersection polygon for is scan-conversion anyway, so I'm not losing any precision by doing this. But how would this compare in terms of speed with creating the exact, vertex-based intersection polygon and then scan-converting? By the way, I'm dealing with polygons which are generally simple (few vertices) but big (cover maybe hundreds of thousands of pixels). Thanks, -- JOR o----------------------o----------------------------o--------------------------o | Jonathan Rice | Email: jorice@cs.tcd.ie | He was a common fly | |----------------------| Tel: 353.1.772941 x2156 (w)| With a taste for fashion | |Computer Science Dept.| 353.1.6245415 (h)| They were thrown together| | Trinity College | Fax: 353.1.772204 | In a heat of passion | | Dublin 2, | woof /\___/ | - "Human Fly", | | Ireland. | /| |\ | The Horseflies | o----------------------o----------------------------o--------------------------o