computational geometry - Reliable test for intersection of two Bezier curves -

-

how reliably find out whether 2 bezier curves intersect? "reliably" mean test answer "yes" when curves intersect, , "no" when don't intersect. don't need know parameters intersection found at. use floating-point numbers in implementation.

i found several answers here use curves' bounding-boxes test: not i'm after such test may report intersection if curves don't intersect.

the closest thing found far "bounding wedge" sederberg , meyers "only" distinguishes between at-most-one , two-or-more intersection, whereas want know if there at-most-zero , one-or-more intersections.

i assuming cubic bezier curves.

the reliable method reporting intersections, using floating point computation, find them, combined error analysis.

the main problem, when floating point computations involved, inconsistency in computed results w.r.t. topology. unfortunately unavoidable, if need compute in computational geometry within reasonable amount of time.

so instead of stressing on right algorithm intersection calculation, picking simple 1 , implementing error analysis solution.

i try implement efficient subdivision algorithm bezier-clipping (or variant of quadratic clipping –nicholas north's geo-clip), , running error analysis compute tight error bounds don't "miss" intersections.

to elaborate, main sources of floating-point (double prec.) error in these subdivision based algorithms are:

  1. truncation error: error in input coefficients etc. finite —we can't here within algorithm.
  2. roundoff error during de casteljau subdivision , point evaluation.

i have used running error bounds de casteljau's algorithm —explained here, along geo-clip algorithm. fast , robust. (b.t.w. theses, in general, read if want make polynomial/bezier algorithms more robust)

assuming, know basics of bezier clipping algorithm, general idea expand hybrid bezier curve (in first paper linked) , fat line appropriately error bounds each clip.

some other unrelated ideas:

  • you can try variant of bentley-ottmann sweepline algorithm. first have split bezier curves x monotone segments; , @ y orderings sweep across them. method has few disadvantages, since bezier curves capable of intersecting multiplicity of more 1 - think of tangential intersection. doing error analysis may difficult here (when compute y value, there floating point error involved)
  • interval projected polyhedron algorithm: uses rounded interval arithmetic robustness. algorithm 2d bezier curves gets quite complicated

there few cases might come across:

  1. self intersections
  2. overlapping (coincident) curves: subdivision algorithms keep going in case. can easy to check though.

good luck :)


Comments

Post a Comment

Popular posts from this blog

Hatching array of circles in AutoCAD using c# -

-
i beginner in autocad plugins .i have created array of circle using following code. now, have hatch circles in array .how that??how hatch circles @ once? moreover, how can return hatch method , use hatch objects.sorry language.thanks in advance. [assembly: commandclass(typeof(beamsection.class1))] namespace beamsection { public class class1 { //class1 obj = new class1(); [commandmethod("beamatsupport")] public void addlightweightpolyline() { // current document , database document acdoc = application.documentmanager.mdiactivedocument; database accurdb = acdoc.database; promptpointresult ppr = acdoc.editor.getpoint("\nselect starting point "); var ucs = acdoc.editor.currentusercoordinatesystem; point3d startingpt = ppr.value.transformby(ucs); list<double> radius = new list<double>(); radius.add(0.5);
Read more

ios - UITEXTFIELD InputView Uipicker not working in swift -

-
hello trying pop uipickerview view programmatically when user clicks on textfield. have tried doesn't doing anything. isn't working. nothing happening when click textfield class userprofiletableviewcontroller: uitableviewcontroller,uitextfielddelegate,uipickerviewdelegate,uipickerviewdatasource { var itempicker: uipickerview! = uipickerview() @iboutlet weak var gendertxtfield: uitextfield! var gender = ["male","female"] override func viewdidload() { super.viewdidload() gendertxtfield.delegate = self itempicker!.delegate = self itempicker!.datasource = self itempicker!.backgroundcolor = uicolor.blackcolor() self.gendertxtfield.inputview = itempicker } func numberofcomponentsinpickerview(pickerview: uipickerview) -> int{ return 1 } // returns # of rows in each component.. func pickerview(pickerview: uipickerview, numberofrowsincomponent component:
Read more

Python Pig Latin Translator -

-
so have been working on @ codecademy.com while trying learn python. don't know if blind , can't see why won't work or what. here's code won't let me use. function print variable if had typed in , print "empty" if didn't type anything. print "welcome english pig latin translator!" original = raw_input("what's name?") if len(original) > 0 print original else print "empty" if len(original) > 0 else the above lines contains syntax errors. try: if len(original) > 0: else: note added colons, ( : ).
Read more