9
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\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 Aug 30 '15 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 Sep 3 '15 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 Sep 7 '15 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 Sep 8 '15 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$ – Christian Rau Oct 1 '17 at 14:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.