As you can see, I mixed the rules a little bit up in my previous post, sorry for that. There are actually two different results for XOR: Generating two intermediate points (RM_PTC_VATTI_INTERSECTION_ACTION_INTERMEDIATE_BOTH) if a left and a right edge intersect and generating a local maximum and a local minimum (RM_PTC_VATTI_INTERSECTION_ACTION_LOCAL_MAXIMUM_MINIMUM) if two left resp. two right edges intersect.
Last edit: Jay Tee 2020-01-06
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Good evening,
I presumed it does NOT matter which is left/right in the bounds ?.
..for odd/even winding.
Maybe ,there is optimisation using that in the clipper code rendering
paths.?.
I browsed the frequency spectrum of command invocation for NO edge horizontal in the intersections(within beam intersections). The Minimum occur as in your (8+2==10) entry table...but I was just using the add vertex to class the minima. Add vertex is to left arm or right arm and that gives the 2 diferent add local minimas.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Clipper relies on winding numbers, my code does not.
The left / right bound labeling of the subject / clip polygons does not always coincide with the left / right bound labeling of the output polygon. Another example for clarification: Consider a difference operation as in the attached image. It shows a clip polygon inside a subject polygon. The clip polygon's edges are labeled in two colors:
red for the clip polygon itself (first left, then right bound)
blue for the output polygon that is associated with it (first right, then left bound)
This is exactly what I call an "inner local minimum": The associated output polygon starts with a right bound, followed by a left bound. As you can see, it creates a hole.
I have attched a small command text (your text edited ..). I am interested in which of the 8 commands have a add vertex to left arm, and which add vertex to right arm.
After you posted I realised that minima handling is difeent between union operation and intersection/difference operations.
I have padded 2 chracter command notation for your commands.EMN is outer minimum and IMN is inner miimum.
Sorry, I did not investigate into that. My implementation handles it by testing if the edge is the left / right edge of its associated polygon. Pseudo-code below:
Aha.!..
I have 2 vatti based clippers with me(Murta derived and Angus clipper derived). I presumed that the left/right property of support edges will never be useful so I alway maintain only unordered support edges.
I had edited his old clipper before clipper2 with methods from clipper2(which you use).
I will wait for the future,to browse your ordered support edges usage. it may have some other uses also like a inclusion tree for output polygons i.e which polygon contains which polygon ....
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thank you.
The NCAR code is very very readable..It just did NOT have XOR and he coded just as you explained.He used some preprocessor for fortran.--only that code is readable--the fortran code from the preprocessor is meant only for readers from the nether worlds.
Request them specifically for kennisons Vatti code .The young developers there seem to be python converts!?
They had NOT put this particular collection for public distribution for some devilish reason.IT is available on github with some other code .
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
THe rendering paths for XOR described by you are a mix of the 2 ways a MM rendering command can be implemented.
Either of the rendering method can also be used as the only method. Doing rendering via LI,RI(left intermediate,right Intermdeiate)) reduces number of output polygons keeping #output vertices count same.
The Murta code uses maximum,Minimum exclusively.Some vatti clippers use the the other methdo exclusively. Clipper2 has a mix of both alternatives.
My workbench dables with both. I thas a option to either use( maximum,minimum) or (left intermediate,Right intermediate) for the rendering.The 1st method outputs touching polygons and the second methdo gives a polygons in which the output polygon sides touch at the event vertex.! and runs measurably faster for a unknown reason I am trying to spot.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
That's an interesting point! You are right, the two rules are completely interchangeable. I toyed around a little bit with them in terms of performance. For my code, the version that outputs a single polygon with touching vertices (RM_PTC_VATTI_INTERSECTION_ACTION_INTERMEDIATE_BOTH) runs considerably faster. The reason is the fact that it generates only one (instead of two) output polygons. That code path is much less complex, has less allocations and does not need to perform AEL lookups. I think I will purge RM_PTC_VATTI_INTERSECTION_ACTION_LOCAL_MAXIMUM_MINIMUM completely from my code base and only use the simple, faster approach.
Another interesting fact: For even-odd parity, the rules for like edge intersections (two intersecting subject edges or two intersecting clip edges) are exactly the same as XOR for unlike edges. I have adapted those like intersections to rely on intermediate output points, too.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
good luck to you.
If you are very very curious try clipping sometimes with different fill rules for subject and clip.
The vatti clippers are ,as i understand , operations on filled regions So much more playing fileds should be possible. AND that is also the reason why the result polygon collection can have output polygons with some filled polygons sharing edges without change in Areal coverage.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Err,I read your rule writeup.
Queries:
...INTERMEDIATE_SECOND corresponds to LI ?
...INTERMEDIATE_FIRST corresponds to RI ?
what is OUTER_LOCAL_MINIMUM ...is there some INNER_LOCAL_MINIMUM.
There is a simple clip transform that makes it possible to use the
same code for Intersection and Difference.(Murtas code).
Where did you pick up Symmetric Difference?..Martinez---???. All the 8
renders are identical?? same as for XOR?
....google says both are same...
1.) If two edges e0 and e1 intersect and e0 is located before e1 in the AEL, ...INTERMEDIATE_FIRST corresponds to e0 and ...INTERMEDIATE_SECOND to e1. Example: (RC x RS) for the "union" operation resolves to ...INTERMEDIATE_SECOND. Therefore, an intermediate point is appended to the second (RS) edge which is always contributing at that point.
2.) ...OUTER_LOCAL_MINIMUM spawns a local minimum where the first AEL edge (after swapping) will be the left bound of the new output polygon and the second edge will be the right bound. ...INNER_LOCAL_MINIMUM inverts that left-right-assignment and basically creates a new "hole".
3.) "Symmetric Difference" is the "same" as XOR. I prefer the term because it is - from a mathematical point of view - the set-theoretic equivalent of XOR as intersection is the equivalent of AND, union the equivalent of OR etc.
This is nit-picking, but makes the terminology more consistent because it avoids mixing boolean and set-theoretic operations.
4.) There are three kinds of "swaps" we have to talk about here:
First, all intersecting edges have to swap their (adjacent) AEL positions after the intersection. That's pretty obvious because the AEL is ordered from left to right and an intersection disturbs that order. Of course, this also applies to non-contributing edges.
Second, after each intersection, the two edges swap their associated output polygons. That step becomes a no-op for ...LOCAL_MAXIMUM because both edges will be non-contributing after handling the maximum.
Third, after handling the intersection of like edges, we also have to swap their bound types (left / right) in addition to their output polygons. This swap also occurs for non-contributing edges.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I missed your statement about holes with INNER_LOCAL_MINIMUM ... can I use that to dentify all holes in my result output.I am NOT interested in a result polygon inclusion map.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
An inner local minimum starts an output polygon where (in AEL order) the first edge is the right bound and the second edge is the left bound. By definition, this implies that the inner area of the polygon is outside of the minimum.
If such a minimum later converges at a local maximum, the output polygon will indeed form a hole. But it might as well be merged into an outer polygon.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
thank you many times over.
I am still exploring ,in the bundled edges of murta,why non contributing intresections make a apperance..just to be ignored...That is the reason I am confused with the terminology of isContributing.
XOR is rendered only if both bundles are hot.The qudrant based paths I used model a situation where I get intersections with only 1 edge Hot.sometimes e0 ,sometimes e1 .and I have to then NOT render them(gulp them ).
I do the position swaps for those intersections always. I was just wondering why the second type of swap(left/right style) is still required.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
You are welcome. But I'm sorry, I cannot help you with that problem, as it does affect neither Clipper2 nor my own code. And I am not familiar with the inner workings of GPC.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Yes, each output contour has two contributing edges, a left and a right one. Whenever I add an output point to an edge's contour, I check if it is the left or right edge.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Since you are ,currently, doing clipping only with even/odd ..have you explored starting clipping ,by choice, from a user defined scan line as the lower Y bound for the clipped ouput. ? It is easy to terminate early if wanted.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thanks, I'll do my best :) Here are my rules for "unlike" edge intersection:
As you can see, I mixed the rules a little bit up in my previous post, sorry for that. There are actually two different results for XOR: Generating two intermediate points (
RM_PTC_VATTI_INTERSECTION_ACTION_INTERMEDIATE_BOTH) if a left and a right edge intersect and generating a local maximum and a local minimum (RM_PTC_VATTI_INTERSECTION_ACTION_LOCAL_MAXIMUM_MINIMUM) if two left resp. two right edges intersect.Last edit: Jay Tee 2020-01-06
Good evening,
why 2 different types of local_minimums?. ..Advantages...! Usage...!
Last edit: Ignorant 2020-01-20
Without this distinction, how should I decide which of the edges becomes the left / right bound of the new output polygon?
Last edit: Jay Tee 2020-01-18
Good evening,
I presumed it does NOT matter which is left/right in the bounds ?.
..for odd/even winding.
Maybe ,there is optimisation using that in the clipper code rendering
paths.?.
On Sat, Jan 18, 2020 at 6:46 PM Jay Tee jay-tee@users.sourceforge.net
wrote:
I browsed the frequency spectrum of command invocation for NO edge horizontal in the intersections(within beam intersections). The Minimum occur as in your (8+2==10) entry table...but I was just using the add vertex to class the minima. Add vertex is to left arm or right arm and that gives the 2 diferent add local minimas.
Clipper relies on winding numbers, my code does not.
The left / right bound labeling of the subject / clip polygons does not always coincide with the left / right bound labeling of the output polygon. Another example for clarification: Consider a difference operation as in the attached image. It shows a clip polygon inside a subject polygon. The clip polygon's edges are labeled in two colors:
This is exactly what I call an "inner local minimum": The associated output polygon starts with a right bound, followed by a left bound. As you can see, it creates a hole.
Last edit: Jay Tee 2020-01-20
I have attched a small command text (your text edited ..). I am interested in which of the 8 commands have a add vertex to left arm, and which add vertex to right arm.
After you posted I realised that minima handling is difeent between union operation and intersection/difference operations.
I have padded 2 chracter command notation for your commands.EMN is outer minimum and IMN is inner miimum.
Sorry, I did not investigate into that. My implementation handles it by testing if the edge is the left / right edge of its associated polygon. Pseudo-code below:
This is what Clipper2 does, too (e. g. see the
IsFront()function in line 154).Last edit: Jay Tee 2020-01-22
Aha.!..
I have 2 vatti based clippers with me(Murta derived and Angus clipper derived). I presumed that the left/right property of support edges will never be useful so I alway maintain only unordered support edges.
I had edited his old clipper before clipper2 with methods from clipper2(which you use).
I will wait for the future,to browse your ordered support edges usage. it may have some other uses also like a inclusion tree for output polygons i.e which polygon contains which polygon ....
Yes, an inclusion tree (as implemented in Clipper) is part of my codebase. I will leave a post around here as soon as I am done :)
For Like Edge intersections do combinations like (LS,LS) (LC,LC) (RS,RS) (RC,RC) occur?
Thank you.
The NCAR code is very very readable..It just did NOT have XOR and he coded just as you explained.He used some preprocessor for fortran.--only that code is readable--the fortran code from the preprocessor is meant only for readers from the nether worlds.
Request them specifically for kennisons Vatti code .The young developers there seem to be python converts!?
They had NOT put this particular collection for public distribution for some devilish reason.IT is available on github with some other code .
THe rendering paths for XOR described by you are a mix of the 2 ways a MM rendering command can be implemented.
Either of the rendering method can also be used as the only method. Doing rendering via LI,RI(left intermediate,right Intermdeiate)) reduces number of output polygons keeping #output vertices count same.
The Murta code uses maximum,Minimum exclusively.Some vatti clippers use the the other methdo exclusively. Clipper2 has a mix of both alternatives.
My workbench dables with both. I thas a option to either use( maximum,minimum) or (left intermediate,Right intermediate) for the rendering.The 1st method outputs touching polygons and the second methdo gives a polygons in which the output polygon sides touch at the event vertex.! and runs measurably faster for a unknown reason I am trying to spot.
That's an interesting point! You are right, the two rules are completely interchangeable. I toyed around a little bit with them in terms of performance. For my code, the version that outputs a single polygon with touching vertices (
RM_PTC_VATTI_INTERSECTION_ACTION_INTERMEDIATE_BOTH) runs considerably faster. The reason is the fact that it generates only one (instead of two) output polygons. That code path is much less complex, has less allocations and does not need to perform AEL lookups. I think I will purgeRM_PTC_VATTI_INTERSECTION_ACTION_LOCAL_MAXIMUM_MINIMUMcompletely from my code base and only use the simple, faster approach.Another interesting fact: For even-odd parity, the rules for like edge intersections (two intersecting subject edges or two intersecting clip edges) are exactly the same as XOR for unlike edges. I have adapted those like intersections to rely on intermediate output points, too.
good luck to you.
If you are very very curious try clipping sometimes with different fill rules for subject and clip.
The vatti clippers are ,as i understand , operations on filled regions So much more playing fileds should be possible. AND that is also the reason why the result polygon collection can have output polygons with some filled polygons sharing edges without change in Areal coverage.
Err,I read your rule writeup.
Queries:
...INTERMEDIATE_SECOND corresponds to LI ?
...INTERMEDIATE_FIRST corresponds to RI ?
what is OUTER_LOCAL_MINIMUM ...is there some INNER_LOCAL_MINIMUM.
There is a simple clip transform that makes it possible to use the
same code for Intersection and Difference.(Murtas code).
Where did you pick up Symmetric Difference?..Martinez---???. All the 8
renders are identical?? same as for XOR?
....google says both are same...
render any vertex but have to be position swapped as intersections?
In your nomenclature how do you indicate which arm of a contour gets the
output vertex..Left /Right...
Last edit: Ignorant 2020-01-08
1.) If two edges e0 and e1 intersect and e0 is located before e1 in the AEL,
...INTERMEDIATE_FIRSTcorresponds to e0 and...INTERMEDIATE_SECONDto e1. Example: (RC x RS) for the "union" operation resolves to...INTERMEDIATE_SECOND. Therefore, an intermediate point is appended to the second (RS) edge which is always contributing at that point.2.)
...OUTER_LOCAL_MINIMUMspawns a local minimum where the first AEL edge (after swapping) will be the left bound of the new output polygon and the second edge will be the right bound....INNER_LOCAL_MINIMUMinverts that left-right-assignment and basically creates a new "hole".3.) "Symmetric Difference" is the "same" as XOR. I prefer the term because it is - from a mathematical point of view - the set-theoretic equivalent of XOR as intersection is the equivalent of AND, union the equivalent of OR etc.
This is nit-picking, but makes the terminology more consistent because it avoids mixing boolean and set-theoretic operations.
4.) There are three kinds of "swaps" we have to talk about here:
First, all intersecting edges have to swap their (adjacent) AEL positions after the intersection. That's pretty obvious because the AEL is ordered from left to right and an intersection disturbs that order. Of course, this also applies to non-contributing edges.
Second, after each intersection, the two edges swap their associated output polygons. That step becomes a no-op for
...LOCAL_MAXIMUMbecause both edges will be non-contributing after handling the maximum.Third, after handling the intersection of like edges, we also have to swap their bound types (left / right) in addition to their output polygons. This swap also occurs for non-contributing edges.
I missed your statement about holes with INNER_LOCAL_MINIMUM ... can I use that to dentify all holes in my result output.I am NOT interested in a result polygon inclusion map.
An inner local minimum starts an output polygon where (in AEL order) the first edge is the right bound and the second edge is the left bound. By definition, this implies that the inner area of the polygon is outside of the minimum.
If such a minimum later converges at a local maximum, the output polygon will indeed form a hole. But it might as well be merged into an outer polygon.
thank you many times over.
I am still exploring ,in the bundled edges of murta,why non contributing intresections make a apperance..just to be ignored...That is the reason I am confused with the terminology of isContributing.
XOR is rendered only if both bundles are hot.The qudrant based paths I used model a situation where I get intersections with only 1 edge Hot.sometimes e0 ,sometimes e1 .and I have to then NOT render them(gulp them ).
I do the position swaps for those intersections always. I was just wondering why the second type of swap(left/right style) is still required.
You are welcome. But I'm sorry, I cannot help you with that problem, as it does affect neither Clipper2 nor my own code. And I am not familiar with the inner workings of GPC.
with millions of inut polygons and only even/odd boolean ops..you will get to use that methdod.!
do you use a step similar to clipper to determine where to output the vertex by the rendering commands?i.e. Left/Right....of output contour?.
Last edit: Ignorant 2020-01-09
Yes, each output contour has two contributing edges, a left and a right one. Whenever I add an output point to an edge's contour, I check if it is the left or right edge.
Since you are ,currently, doing clipping only with even/odd ..have you explored starting clipping ,by choice, from a user defined scan line as the lower Y bound for the clipped ouput. ? It is easy to terminate early if wanted.