My postscript interpreter currently implements the Hodgeman-Sutherland clipping algorithm but this is limited to simpler shapes and doesn't have a provision for utilizing various winding-number rules. So it doesn't help me to implement even-odd filling or handle complex self-intersecting shapes.

The Weiler-Atherton algorithm promises to offer all these features, but every time I sit down with it, I get hung up on implementing the basic constructs. Specifically it requires making bi-directional associations between nodes which can then be traversed in either direction. But, how do you do that?

If I implement my path lists in Postscript (or any dynamic object-based language) as an array of points, the points themselves implemented as an array of coordinates, do I make a list of index pairs and do a linear search for traversing? Or can I use an associative array to make a mapping, and is it sufficient to add both (node1->node2) and (node2->node1)?

Or what if the paths are in a linked-list in a C like language with pointers to the next vertex and a NULL pointer designating the end, do you just add more links (pointers) to the nodes?

You don't need to address all my questions here, it should be sufficient to describe the strategy for building this data structure for any 1 language (not necessarily Postscript or C), and I should be able to apply it to my specific case which is usually to prototype in Postscript and translate to C if necessary for speed.

  • $\begingroup$ Welcome to Compiter Graphics.SE, glad to see a familiar face im sure you will be a great addition to our small community. Sorry I cant answer your question though. $\endgroup$
    – joojaa
    Commented Aug 30, 2015 at 18:51
  • $\begingroup$ Sorry, but I'm a bit lost as to what you are aiming to do. Are you trying to write an "arbitrary polygon" filling routine that also, say, clips to the sides of the viewing rectangle? $\endgroup$
    – Simon F
    Commented Sep 3, 2015 at 16:32
  • $\begingroup$ @SimonF Sorry I didn't notice your comment till now. I'm trying to implement a fully-generalized clipping routine for complex self-intersecting shapes AND complex self-intersecting clipping-regions and parameterized with a winding-number rule. But if I could visualize the data structure in concrete terms, that usually works to get me moving. $\endgroup$
    – luser droog
    Commented Sep 7, 2015 at 23:21
  • $\begingroup$ If you have solved the fill problem for an "unclipped" arbitrary polygon, then you 'only' need to do CSG with an intersection (i.e. AND) operator to then clip it against another arb. poly. Does that make sense? In screen/scanline space the CSG is relatively easy. OTOH if you need a vector model, it seems to me that a scanline model could be extended so that you construct sets of trapezia (mathworld.wolfram.com/Trapezium.html - British definition (i.e. correct def)) for each that describe the interiors. It should be relatively easy to intersect those to generate the final model. $\endgroup$
    – Simon F
    Commented Sep 8, 2015 at 9:26
  • $\begingroup$ As it happens I just recently implemented this algorithm (in C++) and it's really not that difficult, I found a much better short explanation than the one on Wikipedia. I'll see if I can come up with a pseudocode answer that hopefully adresses your concerns. But then again, I also had the luxury of one of the polygons being a triangle. $\endgroup$ Commented Oct 1, 2017 at 14:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.