Finding the hull along a path

I have a series of top and bottom points (at arbitrary resolution) that I use to create a twisted “band” shape.

Now I’d like to calculate the implicit edges that are orthogonal to every midpoint (marked by the dark blue bars in the image below):

How can I go about this? If possible, I’d like to avoid solutions that require rasterization, but suggestions for libraries are also very welcome.

Thank you!

1 Like

Maybe I can get away with additional sampling. :thinking:

Leaving this here as reference for myself, and as food for thought:

Just trying to wrap my head around your input and desired output. You’ve got a sequence of points that determine a path (like the smaller black points in the image below). For each pair of points (like the points P1 and P2 in the image), you wish to determine a segment perpendicular to the path at the midpoint between the two given points (like the segment drawn through the red midpoint.

If this interpretation is correct, first define the vector d = P2-P1. That should point in the direction from P1 to P2. To obtain a perpendicular vector n, write

d = [d[0],d[1]]
n = [-d[1],d[0]]

The vector n will then be perpendicular to your path.

From a mathematical perspective, P2-P1 is the numerator of a difference quotient approximating the direction vector for the path at the midpoint. There are higher order difference quotients using more points on the path, if more accuracy is required. Perhaps that’s built into D3 somewhere; I’m not sure.

I’m not 100% sure I’ve understood your question and there might be more to it. In particular, I’m not sure what the point behind the light red and blue “twisted” line segments is.

1 Like

Sorry for not explaining it better. Please let me try again:

I have two paths, pred and pblue:

Because both are SVG paths, I can call .getTotalLength() and .getPointAtLength() to calculate the position for any relative path length [0…1].

These paths are used as “rails” for a scaling/translating projection whereby x on the horizontal axis is mapped to a path offset t. The transformation for each t is determined by getting the point at offset t for each path and connecting these points:

Finally I can apply the projection to a circle shape:

The black line represents the average of pred and pblue at each offset.

Now, whenever pred and pblue cross each other, the projected shape will also self-intersect. I need to create a second projection for which the shape will not self-intersect (except for projections with zero-width scale).

And for that I need to find, for a given offset, the two points on pred and pblue that lie perpendicular to the average direction of pred and pblue for the offset.

So the primary problem is: How do I calculate the intersection point of that perpendicular line with an arbitrary path, given the information that I have available?


Please let me know if there are still things that are unclear. I want to make this explanation as comprehensible as possible.

I think there are two parts to this:

How do I calculate the intersection point of a line with an arbitrary path, given the information that I have available?

The first part (which you may already be OK with, given the phrasing above) is to compute the lines that are orthogonal to the black path given some offset. @mcmcclur’s answer explains how to find a direction vector that is orthogonal to a particular segment between two black points. Note that with the “1st order” difference quotient used there, the orthogonal direction vector for a black point P_i could be either the one coming from the segment joining P_i to the previous black point P_{i-1} or the following black point P_{i+1}. If you really need lines coming out of the black points themselves, as opposed to arbitrary points on the segments between them, you could average the two choices of direction vector, which is effectively “higher order”. In any case, given these direction vectors and choices of points for them to pass through, you have enough data to compute points on the lines.

The second part is actually computing the intersection(s) of these orthogonal lines with the red and blue paths. There are some nice algorithms out there for segment intersection using sweep line techniques (e.g. https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm) but maybe for your purposes just checking whether a line intersects any of the path segments is good enough. See this nice bl.ock:

Hope this is helpful…

1 Like

Thank you both for your input, I appreciate it! After digging further into the core problem and trying to reframe it, I found out that there doesn’t seem to be a sensible solution in 2D that is worth pursuing.

To give a bit more context:

The transformation (done on 2D canvas) was supposed to look like a flip in 3D space. My hope was that I could somehow project and render a “backface” to fill the space where the shape flips over. But on closer inspection I can see clearly now the rain has it’s not even remotely that simple.

Trying to do procedural animation in the style of liquid motion in pure 2D (and with warpjs) was a nice experiment. But I’ll have to go 3D for the real thing. :confused:

I’m not sure when (or if) I’ll finish up the notebook, so in the meantime, here’s the link:

1 Like

I had a feeling this was a 3D thing after I read your second post. It does look pretty cool as it is!

1 Like