search

linebender / kurbo

A Rust library for manipulating curves
Apache License 2.0
701 stars 68 forks source link

Segment/segment intersections #194

Open simoncozens opened 3 years ago

simoncozens commented 3 years ago

We currently have a line/segment intersection method, which is great, but I think a generic segment/segment intersection trait would be very useful: line/line, line/curve, curve/curve. I have this code in beziers.py and not having it in kurbo is a blocker for me in moving some projects to kurbo.

The only problem is that segment/segment intersections have many gnarly edge cases, and I'm not 100% convinced that my code handles all of them.

simoncozens commented 3 years ago

I have got most of this implemented, leaning on intersect_line for everything apart from the curve/curve intersection case, but I'm having problems terminating the bisection at the right point. (Which I think was a problem with the Python implementation too.)

tylers-epilog commented 2 years ago

Hi Simon.

Is this still being worked on? I'd like to contribute to this library by providing a way to add operators to paths. For example, get the union of two paths, or subtracting filled shapes of one path from another. Intersections between Beziers/line is necessary to do this.

If you have any code that you can provide for a starting point, that would be great. If not, I plan to add the GeoClip intersection algorithm. I have quite a bit of experience in a similar algorithm, BezClip, so I'm not going into this completely blind, but if you have any tips from your past experience on doing this, please let me know

Thanks, Tyler

simoncozens commented 2 years ago

I implemented it in #199; waiting for review...

raphlinus commented 2 years ago

Ah, I should take a look at that. On quick skim, it looks pretty good. I'm uneasy about adding a new trait, as those are really intended for user-defined curves (think Euler spirals and similar) and I doubt that trait will get implemented for anything other than existing beziers. (See #6 for thoughts). But that's not a showstopper.

If someone else knowledgeable were to go through that code carefully, I'd be happy to approve after another light skim myself.

StudioLE commented 2 months ago

Are there any plans for this issue to be picked up again?

It sounds like @simoncozens implemented a solution in #199

simoncozens commented 2 months ago

219 supersedes #199.