How to get all resulting parts?

[woodie2]

I have for example that to objects, red and green. Now I want simply have all resulting polygons when the clip each other, so that I get the right one with 3 polygons.

or a other example:

is that possible, or how do I go about it? whatt should I use as subjects, and what as clips?

Thanks in advance for your help and the wonderful Clipper tool.

[AngusJohnson]

Assuming you're only interested in clipping polygons (ie closed paths), then of the boolean clipping operations are ^mostly commutative - which means that subject and clip polygons can be swapped without changing the operation's result. (^The exception is Difference.)

So with your first example above, the blue triangle represents the Intersection of the red and green shapes (ie where they overlap), and it doesn't matter which shape you assign as the subject and which as the clip.

With your second example, the blue shape again represents the Intersection of the red and green shapes, but with the purple shape being a hole in the green shape. Holes are usually represented by polygons winding in the opposite direction to the paths that contains them. (So, strictly speaking, purple could also be a "hole" in the red shape as long as it wound in the opposite direction.)

Pseudo-code for your second example:

  Paths64 subject, clip, solution;
  subject.Add(MakePath(10,10, 110,10, 110,110, 10,110));
  clip.Add(MakePath(50,50, 110,160, 50,160));
  clip.Add(MakePath(55,95, 55,125, 70,125, 70,95));
  solution = Intersect(subject, clip, FillRule.NonZero);

Please note that I will rarely reply to questions about how to use the library. I simply don't have the resources to do that, and that's what the documentation is for. The exceptions, as in this case, will be where my reply will most likely become part of the documentation.

[alexisnaveros]

Maybe I misunderstood the question, my understanding was that woodie2 is asking how to perform a clipping operation and get (in one clipping operation): the intersection, the subject minus the intersection, and the clipping shape minus the intersection.

If that actually was the question, I don't think that's possible. The code tracks the "winding count" of each region as it goes, and it can't build 3 different polygon outputs in one pass (though, it would theoretically be possible to alter the code to be able to do that).

Of course, you can compute the intersection/overlap, and then subtract that intersection from each of the input shapes.

[woodie2]

Thanks for your answers.
alexisnaveros approach sounds good.

Again to the problem or the task.
I have a large number of polygons, whether they partially overlap or are separate is not known in advance. It can also be that some are completely in others.

The goal is that after cutting, I have all possible snippets without overlaps.

My approach would also be to intersect each polygon with each other individually. Then subtract the intersections from both polygons.

That would just be a lot of clipping processes. Maybe someone has done something similar before and could give some tips :)

[alexisnaveros]

That's a tricky scenario.

If your count of input shapes is low, you could get away with computing a bounding box for each input shape, and computing an intersection whenever they might overlap. If there's an actual intersection between a pair of input shapes, subtract the intersection from both. Update bounding boxes and repeat.

Sorting the bounding boxes, or building a 2D lookup structure (like binary space partitioning) could help reduce the amount of bbox overlap checks.

If you have a large amount of input shapes and/or overlaps, that might still be grossly inefficient. The "proper" solution would be for the library code to track a list of input shape IDs for each region, and output a new polygon for each unique combination of IDs. That is not a trivial change (I'm familiar with the code and it would probably take me a whole week). I hope the bounding box solution is good enough for you!

[woodie2]

Ok I will try it, is there any quick check for equal path64?
I have a list of many Paths64 and want to delete all duplicates. A Point for Point check will be slow I think.

[alexisnaveros]

To find duplicate path64s, assuming you want to detect and delete duplicates even when the contour is out-of-order, I guess I would:

• Make an array of structs with the pointer to the path64, and a "checksum" integer
• Add the x and y of all points to the checksum value
• Sort the array of structs based on checksum value
• Iterate over the sorted array; if a struct has the same checksum as the previous struct, and paths have the same count of points, we might have a duplicate
• To confirm the two path64s are identical, find the first point of A in path B (if not there, not a duplicate)
• Iterate over the two lists of points simultaneously; loop over B when reaching the end ~ if there's any difference in the points, not a duplicate

That should be pretty fast, even if you have millions of paths.

[woodie2]

thanks I will try it that way :)

[woodie2]

another question to the difference funtion, I have:

Subject: (Area 58)
((698, 258),
(719, 229),
(720, 228),
(724, 226),
(725, 226))

Clip (Area 1)
((719, 229),
(720, 228),
(724, 226))

Intersection =
((719, 229),
(720, 228),
(724, 226))

Difference =
((698, 258),
(719, 229),
(720, 228),
(724, 226),
(725, 226))

I think that clipper has a wrong differences, because it is the same like the Subject.

I think the correct differences is that:
((698, 258),
(719, 229),
(724, 226),
(725, 226))

without:
(720, 228),

or is that because of rounding? how can I get the correct differences? :)