2
$\begingroup$

I am given 4 pairs of red-green points in 2D. each pair corresponds to end points of a cubic bezier curve. My objective is to generate random control points for 4 curves (one going through each pair) such that the final curves have these two properties:

  1. Each curve should not intersect itself.
  2. Curves should not intersect each other.

Here is an example of of the output I am interested in:

An example of what I want

Now one easy way to generate bezier curves which aren't self-intersecting is to make sure the line segments between first point and first control point and the one between last point and 2nd control point do not intersect (red and blue lines in the image below). The curve can still have no self intersection if they do intersect but at least if they don't we can be sure it doesn't have any. With this in mind, for each curve I can simply generate totally random control points, and flip their order if these line segments intersect. but so far this only satisfies my 1st criteria while I might generate curves which intersect each other.

enter image description here

I was wondering if there's any joint strategy with which I can generate these control points such that both my constraits are met, while keeping in mind that I want curves to be as random as possible.

With the last remark I wanted to rule out simple solutions such as generating first curve, computing its convex hull (CH), and then generating next curve completely outside the CH, update CH to union of previous CH with the new curve's convex hull, and so on.

$\endgroup$
  • 1
    $\begingroup$ An easy way is to generate sets of three-segment polylines with no intersections, until the Bézier curves defined by the polylines are separated by some minimum distance; there are several ways to implement that check. If the polylines are non-self-intersecting, then the curves themselves are also non-self-intersecting; the curve is always fully contained in the convex hull of the control polygon. $\endgroup$ – Nominal Animal Jul 31 '17 at 14:21
  • $\begingroup$ Another option is an iterative approach: Start with straight lines, but intersections having a repellent effect on the related control points. Add some noise, too. Unfortunately, there is no guarantee this will lead to a solution, especially for hard cases (where a loop around another curve is necessary to fulfill the no-intersections requirement); nor is there any clear end condition for the iterations. $\endgroup$ – Nominal Animal Jul 31 '17 at 14:25
  • $\begingroup$ @NominalAnimal non-intersecting polylines is of course one way to go. however, it can still be the case that two polylines intersect but their bezier curves don't. I mean this produces curves which aren't intersecting but may have large gaps in between them. take for instance the two rightmost curves in my image. their polylines definitely intersect. $\endgroup$ – mmbrian Jul 31 '17 at 14:49
  • $\begingroup$ True. Of course, you could generate random (within some bounds) control points, until the set generated yields non-intersecting Bézier curves. For the intersection tests, you can initially approximate the curves with polylines, to quickly exclude those control point sets that clearly lead to intersecting curves. $\endgroup$ – Nominal Animal Jul 31 '17 at 15:17
  • $\begingroup$ @NominalAnimal Indeed I can generate curves and check them for intersections. however I was hoping this could be avoided meaning that I could somehow formulate this problem in such a way that it yields nonintersecting curves while somehow adding some level of randomness. my end goal is to use this in a realtime visualization so performing lots of intersection tests would be my last resort. $\endgroup$ – mmbrian Aug 2 '17 at 9:17

Your Answer

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

Browse other questions tagged or ask your own question.