soswow / fit-curve Goto Github PK

This project forked from volkerp/fitcurves

JavaScript implementation of Philip J. Schneider's "Algorithm for Automatically Fitting Digitized Curves" from the book "Graphics Gems". Converted from Python implementation.

License: MIT License

JavaScript 99.60% Shell 0.40%

fit-curve's Introduction

JavaScript implementation of Philip J. Schneider's "Algorithm for Automatically Fitting Digitized Curves" from the book "Graphics Gems". Converted from Python implementation.

Fit one or more cubic Bezier curves to a polyline. Works with 2D and 3D curves (and should work for higher dimensions too).

This is a JS implementation of Philip J. Schneider's C code. The original C code is available on http://graphicsgems.org/ as well as in https://github.com/erich666/GraphicsGems

Install

npm install --save fit-curve

Usage

var fitCurve = require('fit-curve');
var points = [[0, 0], [10, 10], [10, 0], [20, 0]];
var error = 50; // The smaller the number - the much closer spline should be

var bezierCurves = fitCurve(points, error);
// bezierCurves[0] === [[0, 0], [20.27317402, 20.27317402], [-1.24665147, 0], [20, 0]]
// where each element is [x, y] and elements are [first-point, control-point-1, control-point-2, second-point]

You can play around with that in this demo.

Changelog

0.2.0

Expose fitCubic, createTangent & add TypeScript declaration

0.1.7

Bug fix #24.

0.1.6

Bug fix #13. Use compiled (ES2015) version as main entry point.

Development

npm install - builds transpiled and minified versions into /lib

npm test - runs tests

fit-curve's People

Contributors

Stargazers

Watchers

fit-curve's Issues

fitting 3d points

I was wondering wether the algorithm is in general capable of fitting points in 3d space, so having points with three components (x,y,z) instead of two (x,y). And whether its in the scope of this library to be implemented. Would be wonderful! But I can understand if it its too complex to add that functionality.

There is no smooth transition for some cases between very sharp and too smooth solutions

@Sphinxxxx Can you check this one. I am not sure, but maybe this is related to major changes you've made. This assumption based on a fact that I had to add additional point in one of my expected results after your changes.

Here is list of points I've drawn on demo page:

var points = [[492,108],[492,111],[494,113],[496,117],[499,119],[503,122],[506,125],[508,126],[510,126],[512,126],[513,127],[515,127],[518,128],[520,128],[523,128],[525,128],[527,128],[529,128],[530,128],[532,128],[533,128],[533,128],[533,129],[534,129],[535,129],[537,129],[538,129],[539,129],[540,129],[541,130],[541,131],[541,134],[541,137],[542,141],[542,143],[542,145],[542,146],[542,147],[542,148],[543,148],[543,149],[543,150],[544,151],[544,152],[545,153],[546,154],[546,155],[547,155],[547,155],[548,155],[549,155],[550,155],[550,154],[551,154],[552,154],[552,154],[553,154],[554,154],[555,154],[556,154],[557,154],[559,154],[559,155],[560,155],[560,156],[561,156],[562,157],[563,158],[564,158],[564,159],[565,160],[566,160],[567,161],[567,161],[568,161],[568,162],[569,162],[570,163],[571,163],[571,164],[572,164],[573,165]];

Here is photos of this line:

What worries me, is that I can't made it up of just 3 points. It goes from 4 right to 2. I can see how there should be a solution with 3 points, that would lay somewhere in between 4 points and 2 point solutions.

Thoughts?

Merging repos

How do you want to proceed with moving the code from https://github.com/Sphinxxxx/fit-curve back here? May I suggest:

Delete the current /lib, /python and /src folders
Pull the new /lib and /src folders from https://github.com/Sphinxxxx/fit-curve

If so, what do you want to do with the .coffee source? Should it still be kept in the repo?

Also: I'm quite new to JavaScript development (I come from the .Net world). Do you have a link or two with a simple tutorial on setting up a good JavaScript workflow (IDE/testing/build tools...)?

Error when after filtering duplicates there are only one point left

Installed with npm and tried the demo. Only at some lines I get the following error:

fit-curve.js:535 Uncaught TypeError: Cannot read property '0' of undefined(…)
subtract	@	fit-curve.js:535
createTangent	@	fit-curve.js:499
fitCurve	@	fit-curve.js:52
(anonymous function)	@	demo.js:76
updateLines	@	demo.js:56
(anonymous function)	@	demo.js:161

A lot of null values in the generated beziers

seems to be a bug in generateBezier function somewhere as a console view at https://oro8oro.github.io/fit-curves/ shows many times values like:

generateBezier: [[609,229],[null,null],[null,null],[531,144]] which will not produce a correct path:
"M 609 229C NaN NaN, NaN NaN 531 144"

Demo, Firefox, and "Show bezier dots"

In Firefox on the demo page if you turn on the dots, it looks like the points being computed are wrong.

Strange Loop after a sharp edge

I assume that is rather an algorithmic question than one about that specification, but anyway:

The following point set creates a very strange loop on the lower stroke (plus a step):
[[708.0, 389.5],[728.0, 386.0],[751.0, 380.5],[780.0, 373.5],[805.5, 367.0],[826.5, 362.0],[847.5, 357.5],[862.5, 355.0],[874.0, 353.5],[879.5, 352.5],[882.0, 352.5],[875.5, 354.0],[857.5, 360.0],[837.0, 366.5],[810.0, 374.0],[788.5, 381.0],[766.5, 387.5],[746.0, 393.5],[726.5, 398.5],[709.0, 404.5]]
(This is a subset of some real world sampling)

The result looks like this (green line + control points):

Any idea how to tackle that?

Klaus

computeMaxError()/bezier.q() often calculates the wrong value

From @Sphinxxxx on July 17, 2016 2:6

computeMaxError() finds the (squared) distance from a source point to a Bezier curve using bezier.q() to find a positon along the curve to compare with(?) But sometimes the position returned from bezier.q() isn't a point on the curve at all, and we miss curves that are actually very good.

Example: http://codepen.io/Sphinxxxx/pen/YWYOJK?editors=0010#302

Green curve: Currently fitted curve segment
Green circle: Point from bezier.q(), should be on the curve(?)
Black arrow: Source point for distance calculation, and the squared distance

Copied from original issue: Sphinxxxx#6

Bug when splitting at a (presumably) really sharp corner

From @Sphinxxxx on July 15, 2016 17:30

When fitting points where there's a sharp corner, and the points at either side of that corner are equal, fitCubic() isn't able to calculate the centerTangent when splitting the curve.

Example points (2 x [70,50] at either side of [72,40]):

[[15,20], [25,50], [50,75], [70,50], [72,40], [70,50], [80,80], [95,90]]

Copied from original issue: Sphinxxxx#4

Splitpoint can be a floating point number which cause the script to crash

Looks like your calculation of the splitPoint here can return a floating point number, which later is be used to get a point from a list. In the original code it is defined as an int. Easiest fix would be

splitPoint = Math.floor(points.length / 2);

But maybe I miss something here.

[Feature Request] Separate error tolerances per dimension

I was considering using an extra dimension to encode metadata of 2D paths, such as pen pressure, and have that be approximated by curves as well.

The problem is that these metadata values might be of much larger magnitude than my point coordinates, making the fit suffer spatially just to fit the extra dimension better.

Would it be possible to have a separate error metric per dimension, or even per group of dimensions? Or would that just be a simple scaling of values on one dimension to be more similar to the others?

Thanks!

[Feature Request] Option for closed mode

New option for closed/ loop mode, where start point and end point supposed to be connected.

// Sample points
let points = [[169.08327661184504,100],[164.13682344149368,108.10236504087167],[158.6808325624972,115.06667699209477],[155.08373798899495,121.80919469911817],[150.82185297687838,127.93955010709587],[144.32724655475414,132.20562977140798],[138.11231161900426,135.7898428514393],[133.92334323717515,141.0062778054169],[130.92249863175175,148.72606104386634],[127.38245066461353,158.1906697084441],[121.92416058194807,167.4756280894482],[114.33817063332049,175.16332267719181],[104.99781519950876,179.43799780994365],[95.0246280840088,179.08127203363017],[85.86550319805295,174.09562706246345],[78.92673646229865,164.85683626453897],[73.77562359010429,155.7296366446203],[67.12747390471083,151.7988126464155],[57.86690053241443,150.93016833546463],[50.36693528035536,146.60855012703126],[49.209156638785366,136.9017077351812],[51.92425736063002,126.42986317361597],[52.00199247029985,119.0037555474922],[47.40659458858676,113.50369135277877],[40.46132833731972,107.52148338465331],[33.885621141836396,99.99999999999999],[31.658556367626133,91.36646790381246],[36.81803895223029,83.77762964047915],[46.061053480502366,78.6440603078885],[52.8676595756433,74.08877658297655],[54.93583885835325,67.25897044170699],[54.210729519951535,57.00101292345075],[54.6107491601339,45.1338207939469],[59.2514596766335,35.79057478860891],[68.14451674606336,32.303652177186734],[78.58988363379659,34.106437330729335],[87.69012980479268,35.4694005770497],[95.73740314283884,32.24796310253261],[104.54151772280292,27.81464289570043],[113.92483949803129,27.00343501378434],[122.5496246533553,30.59939143488714],[129.80609096804073,36.65883247394953],[136.7636163108876,42.06981027341028],[143.45036072986937,47.47753632719585],[147.56790731897257,55.33076175655141],[148.5280059052866,64.74233991051405],[149.52511172309568,72.77333942986147],[153.8532232469118,78.67800055251107],[161.17936128863602,84.29180986590764],[168.0284647657436,91.40600632950067]];

Sorry for my broken english.

Uncaught ReferenceError: bezier is not defined

First, thanks for this nice lib !
I am trying to use it from ES2015 code, but I have the following error :