Pincer parametric intersector
View Patent ↗A system, method, and computer program for a finding an intersection for geometrically coincident curves, comprising selecting a curve pair where at least one curve in said curve pair is a parametric curve; determining a curve parameter for each curve in said curve pair; splitting each of said curves into a plurality of candidate segments; recursively subdividing each of said candidate segments into a pair of finalized segments that are sufficiently straight; intersecting an approximation for each of said finalized segments; obtaining a plurality of next parameter values from said intersecting step; and testing for a terminating condition and appropriate means and computer-readable instructions.
1. A method to find an intersection for geometrically coincident curves, comprising:
identifying a first rectangular box containing a first segment of a first curve and a second rectangular box containing a second segment of a second curve, the first segment and the second segment having a set of current parameters, wherein said first rectangular box intersects with said second rectangular box;
calculating a plurality of tangents from said set of current parameters;
determining, using a processor, whether tangents calculated from the first segment intersect with tangents calculated from the second segment; and
recording a plurality of parameter values to said current parameters that corresponds to an intersection of said tangents calculated.
2. The method of claim 1 , wherein calculating of said plurality of tangents occurs utilizing n-order Taylor series approximations.
3. A method to determine an intersection of two curves, the method performed by a data processing system, comprising:
identifying a first curve with a first set of parameter values, and a second curve with a second set of parameter values;
calculating, using the data processing system, a plurality of tangents of the first set of parameter values and the second set of parameter values;
identifying a tangent calculated from the first set of parameter values that intersects with a tangent calculated from the second set of parameter values to form a pair of intersecting tangents;
identifying a next pair of parameter values from the pair of intersecting tangents; and
solving for a discrete intersection of said first curve with said second curve at a rate of convergence using the next pair of parameter values.
4. A data processing system for determining an intersection of two curves, the data processing system comprising:
a storage device storing program code;
a processor operably connected to the storage device, wherein the processor is configured to execute the program code to identify a first curve with a first set of parameter values, and a second curve with a second set of parameter values; calculate a plurality of tangents of the first set of parameter values and the second set of parameter values; identify a tangent calculated from the first set of parameter values that intersects with a tangent calculated from the second set of parameter values to form a pair of intersecting tangents; identify a next pair of parameter values from the pair of intersecting tangents; and solve for a discrete intersection of said first curve with said second curve at a rate of convergence using the next pair of parameter values.
5. A computer-program product for determining an intersection of two curves, the computer-program product comprising:
at least one non-transitory storage device;
program code, stored on the at least one storage device, to identify a first curve with a first set of parameter values, and a second curve with a second set of parameter values;
program code, stored on the at least one storage device, to calculate a plurality of tangents of the first set of parameter values and the second set of parameter values;
program code, stored on the at least one storage device, to identify a tangent calculated from the first set of parameter values that intersects with a tangent calculated from the second set of parameter values to form a pair of intersecting tangents;
program code, stored on the at least one storage device, to identify a next pair of parameter values from the pair of intersecting tangents; and
program code, stored on the at least one storage device, to solve for a discrete intersection of said first curve with said second curve at a rate of convergence using the next pair of parameter values.