Patch: Eliminate duplicate path segments

[David Turner]

This patch eliminates duplicate path segments. Say you make a path by taking two squares and lining them up so that the left edge of one is exactly congruent to the right edge of the other. Now you combine them (as in ctrl-k). Your path has eight edges, but two of them overlap for their entire length. The path can be simplified by removing the extra segments.

The use case is that I use Inkscape to design laser-cut parts. The redundant segments cause the laser to retrace the same cut, costing me money.

[su_v (suv-lp)]

Combined plain rectangles look ok (yet sometimes the effect of the stacking order when removing segments is unclear to me).

There seem to be some issues with other shapes (e.g. 'L' shaped objects) that share path segments - apparently depending on the used Inkscape version to generate the original paths (any changes in how paths are written or combined since the release of 0.47?):

[su_v (suv-lp)]

a) invalid paths (tested with Inkscape 0.47+devel r9089; SVG error with Batik 1.7, render error in Firefox 3.5.7)

Batik 1.7 error message:

 SVG Error:
 file:/Volumes/blue/img/Inkscape/test/bug/521988-removeredundant-z-order-4-r9089.svg:185
 The attribute "d" of the element <path> is invalid

[su_v (suv-lp)]

b) unexpected results (Inkscape 0.47 r22583 with identical initial path)

[David Turner (novalis)]

Ah, I was handling Z incorrectly. I am now handling it correctly, more-or-less. Note that fill will be messed up in some cases, but since this is intended for unfilled lines, that's OK with me.

It would be quite difficult to get fills correct (especially given the different possible winding rules). The simple cases would be not so bad, but the complex cases would be complex. For non-zero winding, you just need to compute which lines are on the perimeter and make sure that they're continuous and going in the clockwise direction. Evenodd winding would be worse.

[su_v (suv-lp)]

When testing different z-orders with the new version a path was created (see attached file) that crashed the new node tool in 0.47+devel. The node tool bug has been fixed in bzr trunk already and it was recommended to change the extension as well.

- thread in inkscape-devel
<http://old.nabble.com/Node-tool-crash-due-to-modified-path-data--td27603407.html>.
- Krzysztof's answer: «Fixed in 9096.
The last subpath in the problematic path has only a moveto, this should also be fixed in the extension. »

[David Turner (novalis)]

OK, paths will no longer end with moves.

[suresh (suresh-meetsme)]

Hi,

I have used this extension and found it is very useful. Not It will be little more interesting If You can add option to remove 'overlap'. For example If I draw two rectangle over each other and it should not overalp. I know it is possible with Path->Exclusion option. but with complex drawing like lots of curve with hatch apply, then it should remove overlap path.

What's your view on this?

[Matrix Color (matrixcolor)]

You should be able to use Path -> Union to remove the overlapping parts.

[suresh (suresh-meetsme)]

Hello Matrix,

Thanks for the quick reply. I tried this tricks, It works like a charm. But What About this file.

I open .ai file in InkScape, create duplicate and overlap both the file. Now I want to remove overlapping line/path.

could you please guide me on this or ow it is possible?

Attached here with please find the .ai file for the reference.

[suresh (suresh-meetsme)]

David, This is the best extensions for the people like me, as I am also using InkScape for cutting embrodery parths, this will also save time. Can you please guide me on right direction for https://bugs.launchpad.net/inkscape/+bug/521988/comments/11.

[David Turner (novalis)]

Thanks for jumping in here, Matrix.

Suresh, I haven't really thought about this in quite some time. I'm also not sure I understand what you're trying to do here. Can you give a minimal, complete example of an input file and a manually created version of the desired output file?

[suresh (suresh-meetsme)]

@David,

What I was saying was, let say I open .ai file in InkScape and make overlap on each other as shown in attached figure and then I want to remove duplicate path. Is it possible with the same python extension?

Since both the file overlap and at the same time I want to remove overlapping points.

Please let me know If it is possible with the current python extension.

[David Turner (novalis)]

Probably not, because those segments are unlikely to be identical. Why don't you try it and see if it works?

[suresh (suresh-meetsme)]

@David,

I have tried but it doesn't works. So just wanted to know If this is possible with current python extension. Let me know Is there any other possible workaround are there.

[David Turner (novalis)]

I can't really think of another work-around. Sorry.

[Andrew Baxter (highfellow)]

I've been trying to burn the attached svg file to plywood using a laser cutter, and wanted to use removeredundant.py to remove the overlapping lines. However this causes inkscape to crash. The following lines are printed in the terminal I ran inkscape from:

"Emergency save activated!
Emergency save completed. Inkscape will close now.
If you can reproduce this crash, please file a bug at www.inkscape.org
with a detailed description of the steps leading to the crash, so we can fix it.
Segmentation fault (core dumped)"

Any ideas why this is happening? I'm willing to spend some time testing and debugging the plugin, as I'd really like to see this working.

[su_v (suv-lp)]

Doesn't crash with Inkscape 0.48.4 and 0.48+devel r12481 on OS X 10.7.5, but doesn't reduce partially redundant path segments either AFAICT (this is likely to be expected: duplicate outline segments of the sample tree do not overlap for their entire length, and even if they do, they are probably not exactly identical).

> However this causes inkscape to crash.

Which version of Inkscape do yo have installed (see Inkscape menu 'Help > About Inkscape'), on which OS?
(If you happen to use Inkscape 0.48.3.1, you are likely experiencing bug #944077 - the SVG file seems to originate from a PDF based on the 'transform' attribute of the lop-level group.)

[Alvin Penner (apenner)]

on Windows XP, Inkscape rev 12472, I get the following result:

- open fractree-detail-5.0
- select All objects, perform Object->UnGroup
- select All objects again, perform Object->UnGroup
- get 3319 objects of type Path
- perform Modify->Remove Redundant
- get the following crash message

Traceback (most recent call last):

  File "removeredundant.py", line 82, in <module>

    e.affect()

  File "C:\InkscapeBZR\inkscape\share\extensions\inkex.py", line 263, in affect

    self.parse()

  File "C:\InkscapeBZR\inkscape\share\extensions\inkex.py", line 187, in parse

    self.document = etree.parse(stream)

  File "lxml.etree.pyx", line 2692, in lxml.etree.parse (src/lxml/lxml.etree.c:49594)

  File "parser.pxi", line 1522, in lxml.etree._parseDocument (src/lxml/lxml.etree.c:71582)

  File "parser.pxi", line 1552, in lxml.etree._parseFilelikeDocument (src/lxml/lxml.etree.c:71892)

  File "parser.pxi", line 1435, in lxml.etree._parseDocFromFilelike (src/lxml/lxml.etree.c:70807)

  File "parser.pxi", line 997, in lxml.etree._BaseParser._parseDocFromFilelike (src/lxml/lxml.etree.c:67948)

  File "parser.pxi", line 539, in lxml.etree._ParserContext._handleParseResultDoc (src/lxml/lxml.etree.c:63824)

  File "parser.pxi", line 625, in lxml.etree._handleParseResult (src/lxml/lxml.etree.c:64745)

  File "parser.pxi", line 565, in lxml.etree._raiseParseError (src/lxml/lxml.etree.c:64088)

lxml.etree.XMLSyntaxError: Document is empty, line 1, column 1

[su_v (suv-lp)]

There's one step missing (see original description):

Alvin Penner wrote:
> …
> - get 3319 objects of type Path

Ctrl+K (Path > Combine)

> - perform Modify->Remove Redundant

[Alvin Penner (apenner)]

sorry about that, I didn't read the full thread:

- so now I get 3319 objects of type Path as before
- perform Path->Combine, get 11737 nodes in Path
 - perform Modify->Remove Redundant
 - get 11737 nodes in Path as before.

so no crash but no change in the Path either. Apparently nothing was done.

[Andrew Baxter (highfellow)]

I've uploaded a simplified version of the tree design, rendered at a much lower level of detail. It will probably give the same results, but should be more useful for testing purposes. It still crashes on my setup.

Incidentally, I'm running inkscape 0.48.3.1 on ubuntu, which is the one mentioned earlier as having a bug.

[Andrew Baxter (highfellow)]

I've now install the devel version of inkscape from the ubuntu ppa, and I'm getting the same results as you - the plugin runs OK, but doesn't appear to have any effect.

The quickest way to see for sure if the plugin has worked is to use path->break apart, then pull some of the fragments apart. You can see the places where there was a double line.

Is it likely that the plugin could be modified to deal with this kind of shape? I would be up for doing at least some of the work.

[Andrew Baxter (highfellow)]

I was thinking about a possible algorithm for this. One way that I think would work would be:

- for each path segment in the drawing, look to see if there are any nodes in other paths which are on the segment. (I.e. less than a certain distance from the segment)
  - if any are found, add new nodes to the path segment you're looking at, at the closest point to each node in the other paths.

- then go through as before looking for similar path segments and deleting all but one. (Possibly using a fuzz factor to allow close matches).

[Alvin Penner (apenner)]

@Andrew, thanks for the demo file, fracTree.svg.
 I have looked at the code in the file removeredundant.py, and as far as I can tell, it will not work if the overlap between two lines, or the overlap between two Bezier curves, is a partial overlap. In order for it to work it seems to be necessary for the endpoints to agree perfectly, both for Bezier curves and for lines.
 In your case this will almost never happen. All of the duplicate paths appear to come from intersections of two Beziers, which will typically never happen at endpoints. Attached is a typical duplicate path, file fracTree_reduced.svg. The left object contains the original path with duplicates. The right object is the same path where I have manually moved one sub-path to show the duplication. It is clear that what happened is that an intersection of Beziers was detected. Then a portion of one Bezier curve was spliced at an intermediate t value, and was copied and pasted onto the other Bezier curve, so as to avoid the intersection. To undo this operation after the fact would, in my opinion, be extremely difficult. You would need to detect the intersection, or near intersection, after the fact, and then match the Bezier curves, not only at the endpoints, but also at the intermediate points, by matching both slopes and curvatures. There are tools available for doing some of this work. For example, bezmisc.py has some tools for splicing Beziers, and lib2geom probably has routines (in C) for detecting intersections of Beziers.
 However, I think it would be more effective to pursue a solution at the source, in the Field program, before these modifications occur. When these modifications were made, in Field, all of the necessary information was available, including intersection points, t values, etc. Perhaps the developers of Field could be contacted to see if they have a solution to this issue. Field is apparently written in Java, and in Python, so perhaps they could point you to some Python code where you could nip the problem in the bud, which would be a lot easier, imho, than retroactively trying to undo the damage.

[Andrew Baxter (highfellow)]

OK thanks for looking at it. You're right that it was generated that way. I did have a go at sorting it out at source, and have not found it so easy. It just occurred to me that patching the plugin might be worth a try. Also that if this did work, then it would be more generally useful to people than a fix to a program only I'm using.

Cheers for the advice - I'll have a think about what I want to do.

[Brynn (brynn4inks-deactivatedaccount)]

I'm not sure how to get support for this extension. But since this is where I downloaded it from, maybe someone can help?

Attached is a file with a number of overlapping lines. But this extension doesn't seem to work on it. I've used this extension on the output from the Random Tree extension, and it works great there!

I wondered if it might not be working in this file, because the paths are closed? (they are open in Random Tree) So I broke 1 node in all the subpaths, so that they are all open paths. But I still didn't get any results.

Then I wondered if it might be because there are compound paths here. So I broke all apart. Still doesn't work.

Next I wondered whether it needs to be all 1 single compound path, so I combined everything. In the array of 45 object, approx 82 instance of overlapping segments (164 segments in all, approx) only 5 or 6 instances of redundent segments were fixed. The other ~40 still exist. So something happened. But it doesn't fix them all.

Then I thought maybe if they were individual, 2-node, path segments. So I broke all the nodes apart. Still no luck.

Note that I used Undo between each of the above tests, to make them fair tests. The only thing I can think of, that I didn't try, is making it all 1 single connected path, which would be a lot of work to create. Also none of those tests are in the attached file. But you can use the file for testing.

Why doesn't it work in this file? Is there anything I can do, to make it work (I mean except for hacking on the code, which I don't know how)? Or if there's a better place to get support for this extension, please let me know.

Thank you very much :-)
brynn

[David Turner (novalis)]

Brynn, I apologize for this. Let me explain what's going on, and how you can work around it, and why I'm probably not going to fix it.

1. The extension only works if all paths with redundant edges are combined. I know that you tried that and it didn't work -- it's necessary, but not sufficient.

2. The extension requires that edges to be combined be *precisely* identical. In your path, for example, there are some points with x coordinate 861.66656 and others with x coordinate 861.66657, 861.66658, and 861.66659. Those should probably all be the same. If I take your path and round off to the nearest hundredth of a unit, the extension appears to work.

3. To test this, I actually hacked the rounding into the extension. I don't want to code this hack in permanently, because the "hundredth" bit is just a guess. I don't know how precise anyone's laser cutter is, so I don't want to guess at which two points are actually the same. And because people use different units (millimeters vs inches vs ...), what "one hundredth" of a unit means can vary dramatically between drawings. I could guess based on internal evidence within the path, but that seems error-prone too. If someone else has any ideas, please let me know (or, even better, provide a new version).

tl; dr: combine all paths and make sure your endpoints are actually identical.

[Brynn (brynn4inks-deactivatedaccount)]

Oh wow, thanks for your help!

Regarding your comment about laser cutter precision, people may want to use this extension for projects besides laser cutters. As mentioned somewhere in this (long) thread, one example is for designs for embroidery machines. And any kind of cutter/plotter, from the home/craft machines to CNC.

For me, I just like to have a nice clean file, no matter what I'm using it for. I know from using it on the Random Tree extn, that it doesn't have much effect on the number of nodes. So it's no use for optimising in that way. But for me, when I view an image like this (black paths on white bg) with overlapping paths, it's easy to see those overlapping parts, without any zoom at all. Perhaps it's because of those 0.00001 discrepancy that makes them look slightly wider? I'm not sure. I just want to avoid manually editing to remove the doubles.

I used snapping to both draw, and arrange the pattern units for the test file. All this time I thought snapping was absolutely precise. But I guess it's only relatively precise?

In an unrelated subject in a forum, Inkscape Preferences > Input/Output > SVG Output > Numeric Precision was mentioned, and briefly discussed in a very general way. I guess it's set to 8 by default. But would it work to set it to 5 or 6? Would that be a way to make the extension recognize the nodes are precisely in the same place, even though they might be off by one or two 0.000001? Or would it be just the opposite, and make sure it doesn't work at all??

Thanks again :-)

[David Turner (novalis)]

Numeric Precision might fix it -- try it and see!

[Brynn (brynn4inks-deactivatedaccount)]

Hah! Yes, it does! I changed numeric precision from 8 to 6 (since I wasn't sure exactly how "off" the nodes were). And it worked flawlessly, as far as I can tell.

[Brynn (brynn4inks-deactivatedaccount)]

Oh wait -- no it doesn't. Sorry about that. I can't see how to edit messages here, but I was looking in the wrong place. It doesn't seem to help at all, actually.

But thanks anyway :-)

[Jin Choi (jinschoi)]

In Inkscape 0.92.2, it seems this extension works best when SVG output format is Absolute instead of Relative or Optimized.

[Jin Choi (jinschoi)]

I made a small adjustment to the extension to consolidate all points within a certain distance from a previously seen point to that point, using a variant of a fixed radius nearest neighbor algorithm. I also moved the seenSegments set outside of the paths loop so you do not have to combine multiple paths, only have them selected.

The default radius is 0.1 units. X and y axes are considered separately, so it is not a Euclidean distance, but that could be easily changed. The radius is set within the code, I do not know enough to provide an Inkscape dialog to adjust parameters.

[David Turner (novalis)]

Thanks, Jin. I would like to make the FixedRadiusSeach optional, and have a regular dict for those with exact data.

I am a little skeptical of get_or_add, because I worry about the following case (one-dimensional, for simplicity). Imagine that r=0.1, and the first point we encounter is 0.11. There are also points at 0.2 and 0.29. All points are within a 0.1 unit radius of 0.2, but since we happened to see 0.11 first, 0.29 is left out. This is somewhat surprising. I don't know what the right thing to do is here.

[Jin Choi (jinschoi)]

I went with a greedy approach in the interest of efficiency. In my case, I was trying to simplify some free online USA maps, which had an occasional jitter of exactly .1 px, and for my purpose it was sufficient.

When you're talking about moving nodes around automatically and deleting segments, I think some amount of ordering-based inconsistency is acceptable.

You could optimize this to be more consistent by doing two passes, the first in which you record the number of visible nearest neighbors for each node using the bin and search approach, then a second where you retain and consolidate starting with the nodes with the highest neighbor counts. But I think the number of scenarios where this situation occurs and is significant is likely to be vanishingly small. Especially for tool paths for CNC and laser cutting, the incoming data will be clean and have exact overlaps, or will be very slightly messy and just need a little jostling.

[Zhart (zhart)]

Unfortunately, "removeredundant" extension doesn't help with duplicated (overlapped) nodes:
https://bugs.launchpad.net/inkscape/+bug/1759577

Any suggestions?

[Jin Choi (jinschoi)]

Are the nodes in question exactly redundant? Check their coordinates in the saved file or using the XML node browser. If there is any difference, you might try my modified version in #35 above and see if that helps.

[Elizabeth Powell (elizabethrpowell)]

Hello, thanks for this bug/extension, it's exactly what I needed... aside from the problem I'm about to describe (and I hope it's appropriate to describe it here, since this is where I found the extension).

I'm finding it doesn't remove duplicates when the path is a curve. I've attached a sample file - some text converted from a TTF font where both lines of the glyph overlap each other to simulate a single line font.

The top, in black, is the unmodified paths. The bottom, in red, is the paths after Jin's "remove redundant paths" has been applied (I've tried both versions with no luck). You'll see it works perfectly on letters composed of straight lines and circles, like 'p', but the nodes are still doubled on letters that contain curves, like 'h'.

I can clean these up manually by breaking the path at each 'end' node, then breaking the path apart and deleting one of the duplicates, but it would be nice to have an automated solution.

[David Turner (novalis)]

Yeah, it turns out that curves are a bit tricky because curves with different control points can look quite similar. I guess we could rasterize the curves, or just ignore those cases.

I should really get around to messing with this again at some point, but I have to admit it's not super-likely any time soon. Sorry.

[Tekchik (techchick)]

Can someone help be run this?

Also I created an svg file and when I got to upload it to Design Space it shows the file but also some text off to the side that I can't see when I'm in inkscape. Do you why I can't see it in Inkscape and why its not deleted. I tried ctrl + A and there's nothing to select. I tried to highlight but nothing shows up.

Please HELP!!!

[Brynn (brynn4inks-deactivatedaccount)]

I'm not clear what your problem has to do with this bug or bug report.

You could get support for Inkscape on the User mailing list, forums, or IRC. Find info here: https://inkscape.org/en/community/

[mkoniecz (matkoniecz)]

How I am supposed to run this extension?

I put it into folder as advised at https://inkscape.org/gallery/=extension/ but I see no change,

Earlier comments mention "perform Modify->Remove Redundant" but I see "Modify" nowhere.

I am unsure whatever extension failed to apply in 0.91 or whatever its action is available and I missed it. I see nothing in extensions menu, Inkscape is not complaining at startup.

[Brynn (brynn4inks-deactivatedaccount)]

"Modify" means "Modify Path". Do you see it in Extensions menu > Modify Path > Remove Redundant Edges ?

[Brynn (brynn4inks-deactivatedaccount)]

Even though there is a good bit of technical discussion in this report, I've attempted to migrate it. Mostly because I hope someone can make it work, when nodes are not precisely on the same coordinates, but as close as they can get by snapping.

As far as I can understand, one of the attached PY files (the last one) is supposed to do that. But it didn't work for me.

So I'm migrating in hopes that it can be done.

Migrated to: https://gitlab.com/inkscape/inbox/issues/1348

Closed by marking Invalid.

Migrated and closed by brynn.