<p>My postscript interpreter currently implements the <a href="https://github.com/luser-dr00g/xpost/blob/master/data/clip.ps" rel="noreferrer">Hodgeman-Sutherland clipping algorithm</a> 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. </p>

<p>The <a href="https://en.wikipedia.org/w/index.php?title=Weiler%E2%80%93Atherton_clipping_algorithm" rel="noreferrer">Weiler-Atherton algorithm</a> 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?</p>

<p>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)?</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2017-10-01T14:25:48.753Z
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.
Christian Rau
CC BY-SA 3.0
2015-08-30T18:51:35.957Z
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.
joojaa
CC BY-SA 3.0
2015-09-03T16:32:18.670Z
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?
Simon F
CC BY-SA 3.0
2015-09-07T23:21:32.447Z
@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.
luser droog
CC BY-SA 3.0
2015-09-08T09:26:11.867Z
*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  (http://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.
Simon F
<polygon><clipping><data-structure>
How to describe the bi-directional links for the Weiler-Atherton algorithm?
luser droog
# How to describe the bi-directional links for the Weiler-Atherton algorithm?

(Asked by: username_0 on 2015-08-29)

My postscript interpreter currently implements the [Hodgeman-Sutherland clipping algorithm](https://github.com/username_0-dr00g/xpost/blob/master/data/clip.ps) 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](https://en.wikipedia.org/w/index.php?title=Weiler%E2%80%93Atherton_clipping_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.

**Tags:** polygon, clipping, data-structure

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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?  
> **username_0**: @username_3 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.  
> **username_3**: *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  (http://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.  
> **username_1**: 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.  

---

## 0 answers

