Given an arbitrary two-dimensional shape represented (and thus representable) by a finite sequence of closed NURBS, what is the most efficient way to check whether the line between any two points located on the outline of the shape is completely contained in the shape's interior?

We assume that

  • a point on the outline of the shape is contained in the shape.
  • a shape's outline never intersects itself.
  • there cannot be more than two control points of anys NURBS on one position.$^1$
  • the shape is comprised of one closed set of curves. The perimeter is always closed and there cannot be a second closed loop in the same shape.

This image shows some of above requirements in visual form, in case my wording is ambiguous. I hope the edit clarified some aspects of the problem. Thanks to John Hughes for the assistance.

$^1$ I believe this rules out cases where two subregions of a shape could only be connected by one point.

  • $\begingroup$ Nurbs cannot outline an arbitrary 2-dimensional shape. (Example: the set of all pairs $(x, y)$ with $0 \le x, y \le 1$ and $x, y \in \Bbb Q$.). $\endgroup$ – John Hughes Dec 21 '17 at 18:38
  • $\begingroup$ @John Hughes Thank you for the hint. As I am only considering shapes described by NURBS, shapes that cannot be described by NURBS fall out of scope. What would be a better wording than "arbitrary" here? $\endgroup$ – Orphevs Dec 21 '17 at 19:22
  • $\begingroup$ I don't know a compact way of describing this, but if I were you, I'd say "the interiors of simple closed curves that comprise a finite number of NURBS segments." (If that's what you mean, of course...I don't want to put words in your mouth). $\endgroup$ – John Hughes Dec 21 '17 at 20:10
  • $\begingroup$ That does indeed sound as if it better describes what I intended. Thank you for your time and have some happy holidays :) $\endgroup$ – Orphevs Dec 22 '17 at 5:49
  • $\begingroup$ You've edited, but you still haven't mentioned "finite", which is important if you want to avoid the equivalent of the topologist's sine curve, or the Hawaiian earring, or other such tricky cases. $\endgroup$ – John Hughes Dec 22 '17 at 23:14

For a simple closed nurbs curve, you can check that ONE point of the segment is within the curve (shoot a ray to infinity that crosses the curve transversely, and check that the number of crossings is odd). Then you just check that for some subdivision of the control hull, the segment and the control hull are disjoint.

This depends on the notion of "shape" or "never leaves the shape" meaning that the segment is strictly in the interior of the nurbs curve, so that its minimum distance from the nurbs curve is positive rather than 0; for the weaker case of the segment being in the closure of the interior of the nurbs curve, the problem is far more difficult.

Let me give an example: consider the region $R$ strictly outside two disks of diameter 1, the first centered at $(+1, 0)$, the second at $(-1, 0)$[these are tangent at the origin], but strictly INSIDE the disk of radius $3$ centered at $(1,0)$ [which is tangent to the second disk at $(-2, 0)$]. That region is simply connected, but if you let $S$ be the closure of $R$, then $S$ contains the segment connecting the points $(0, \pm 1)$. Think for a moment or two about how you'd verify that numerically. If it seems easy, move everything to the right by $a/2$, where $a$ is the smallest number representable on your computer.

  • $\begingroup$ Thank you for your quick answer. As seen in the example image, intersections between the line and shape may never occur besides in the start- and endpoints. If we assume that all subregions of the shape are connected by not only one point (as given in your example) but a 'channel', and that there cannot be more than two control points at one position (e.g where one curve ends and another begins), how would I compute whether two points are connected (as described in the OP)? This will be used for image analysis, so a) multiple curves for one shape and b) no such pinpoint connections are likely. $\endgroup$ – Orphevs Dec 21 '17 at 19:43
  • $\begingroup$ In that case, I'd say you need to ask a different question, and you need to think really hard about the constraints you're putting on the external curve before you ask other people to spend time on the problem for you. For instance, if you intersect my example with the upper half plane, then the segment from $(0,0)$ to $(0, 1)$ lies within it, but could be really tough to detect/confirm as lying within it. This stuff is hard, which is part of why topology was invented. :( $\endgroup$ – John Hughes Dec 21 '17 at 20:13
  • $\begingroup$ Okay, I will do that. Thank you for your advice so far. I believe I might be misunderstanding some of the issues you point out, as I am no native speaker. If the curves describing my shape can only ever share two control points, so that self-intersections and one-point pinholes may never occur, how can we run into issues with checking for a connection inside the shape's boundaries (floating point accuracy and memory limits aside)? Even better yet, could you recommend any literature regarding my problem? I will resort to the sandbox to refine my question. $\endgroup$ – Orphevs Dec 21 '17 at 20:57

Order the segments so that the outline curve is drawn counterclockwise. This lets you evaluate the outline curve and its tangent vector ($\vec{d}(t)$, equation $\eqref{NA5}$ below) at the start and end points of the line. If the line is clockwise compared to the tangent vector at either point, the line is not contained within the shape. (This checks allows you to very quickly rule out a large number of cases.)

Let's say the starting point of the line is at $(x_0 , y_0)$, and end point at $(x_1 , y_1)$. Define a rotation matrix $\mathbf{R}$, $$\mathbf{R} = \left [ \begin{array}{c} u & v \\ v & -u \end{array} \right ], \qquad \begin{cases} u = \frac{x_1 - x_0}{(x_1 - x_0)^2 + (y_1 - y_0)^2} \\ v = \frac{y_1 - y_0}{(x_1 - x_0)^2 + (y_1 - y_0)^2} \end{cases} \tag{1}\label{NA1}$$ so that point $\vec{p} = (x , y)$ is transformed using $$\vec{p}^, = \mathbf{R}\left ( \vec{p} - \vec{p}_0 \right ) \tag{2}\label{NA2}$$ This transformation moves the starting point to origin $(0,0)$, and end point to $(1, 0)$.

If any transformed curve segment passes through $0 \lt x \lt 1$, $y = 0$, then the line segment is not contained within the shape. In other words, you need to find if any of the curve segments cross the $x$ axis at $0 \lt x \lt 1$.

Because the general form of a NURBS curve is $$\vec{C}(t) = \sum_{i=0}^k R_{i,n}(u) \, \vec{P}_i \tag{3}\label{NA3}$$ it can be trivially written as functions separate to each coordinate axis. If $\vec{P}_i = ( X_i , Y_i )$, then $$\vec{C}(t) = \left( x(t), y(t) \right), \quad \begin{cases} x(t) = \sum_{i=0}^k R_{i,n}(u) \, X_i \\ y(t) = \sum_{i=0}^k R_{i,n}(u) \, Y_i \end{cases} \tag{4}\label{NA4}$$ The range $t$ is typically constrained to $0 \le t \le T$.

Note that the tangent vector I mentioned in the beginning is $$\vec{d}(t) = \left ( \frac{d \, x(t)}{d \, t} ,\, \frac{d \, y(t)}{d \, t} \right ) \tag{5}\label{NA5}$$

Here, in the transformed coordinates, the problem simplifies to handling each NURBS curve segment at a time, solving their $y(t) = 0$ for $t$, and if such $t$ exist with $0 \le t \le T$, if the corresponding $x(t)$ fulfills $0 \lt x(t) \lt 1$. If there is even one such, then the curve passes through the $y$ axis within $0 \le x \le 1$, and the line is not contained within the outline curve.

(Technically, you should allow the line to pass tangentially along the outline curve, without rejecting it. This means not rejecting $y(t) = 0$ if it is a local extrema, i.e. the curve is either $y(t) \le 0$, or $y(t) \ge 0$, within the range $t$ where $0 \lt x(t) \lt 1$.)

You'll find that depending on what kind of NURBS curves you have (fixed degree etc.), solving the $y(t) = 0$ should be easy. The transformation does cost four multiplications and four additions or subtractions per control point, but in practice that cost is neglible; this approach should yield quite efficient numerical solution to the stated problem.

  • $\begingroup$ Thank you, I believe this is what I was looking for. I will attempt to implement something in this manner after christmas. I sadly can't upvote any of the answers yet, but I will accept yours after I checked its applicability. Happy holidays :) $\endgroup$ – Orphevs Dec 22 '17 at 5:47
  • $\begingroup$ @Orphevs: No worries! If you do find any issues with the approach, do let me know in a comment. $\endgroup$ – Nominal Animal Dec 22 '17 at 5:50
  • $\begingroup$ Suppose that the NURBS curve is tangent to your transformed segment at $x = 1$. (This is the case I mentioned in the last comment to my own answer.) Then how do you know whether there's a crossing? $\endgroup$ – John Hughes Dec 22 '17 at 13:13
  • $\begingroup$ @JohnHughes: I tried to explain that in the next-to-last paragraph, in parentheses. It all boils down to examining how the curve and line diverge, if they diverge; if they do not, then the line is along the outline curve. If the curve diverges to different sides of the line, the line is not contained in the shape. If, as I suggest in my answer, the curve is defined (continuously) in counterclockwise order, then that examination only requires one to remember the side from which the curve entered the line; even if multiple segments are parallel to the line. Should I add example (psuedo)code? $\endgroup$ – Nominal Animal Dec 22 '17 at 22:37
  • $\begingroup$ Your parenthesized paragraph explicitly ruled out the very case I cited, by requiring $0 < x < 1$, while my example involves $x = 1$. And that case is subtle. Even if it weren't, your code involves, in an essential way, testing whether a float is zero. I'll bet you know why that's a bad idea. $\endgroup$ – John Hughes Dec 22 '17 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.