Light

mikolalysenko / robust-orientation Goto Github PK

View Code? Open in Web Editor NEW

23.0 4.0 5.0 16 KB

Robustly computes the orientation of a tuple of points

License: MIT License

JavaScript 100.00%

robust-orientation's Introduction

robust-orientation

Robust orientation test for n-simplices. Based on the work of Jonathan Shewchuk:

Shewchuk, J. "Adaptive precision floating point arithmetic predicates for computational geometry"

This implementation is robust in the sense that the answers returned are exact, but it is not fully adaptive. Basically an initial test is computed, and if the accuracy of this is too low then an exact version of the test is executed. Compared to Shewchuk's original C code this is slower, but eventually I hope to make improvements that bring the performance closer in line to his version.

Example

var orientation = require("robust-orientation")

console.log(orientation([0, 0], [1e-64, 0], [0, 1]))

Install

npm install robust-orientation

API

var orient = require("robust-orientation")

`orient(p0, p1, p2, ...)`

Exactly computes the orientation of a collection of (n+1) points in n-dimensions.

p0,p1,p2,... is a list of points

Returns The orientation of the point set:

<0 if the tuple of points is positively oriented
>0 if the tuple of points is negatively oriented
=0 if the points are coplanar

Note For up to 5 points, you can directly call an optimized orientation routine, thus avoiding an extra dispatch/switch statement by calling orient[d], where d is the number of points. Eg.

orient[3](p0, p1, p2) === orient(p0, p1, p2)

Credits

(c) 2013 Mikola Lysenko. MIT License

robust-orientation's People

Contributors

Stargazers

Watchers

Forkers

nvdnkpr muscla87 js-van jthrilly mngr777

robust-orientation's Issues

Possible orientation4 bug

The second test case seems to be inconsistent with WolframAlpha, returning +ve instead of -ve.

var orient = require("./");

// WolframAlpha says this should be -ve: http://www.wolframalpha.com/input/?i=determinant%28%7B%7B-0.5257311121191329%2C-0.5257311121191329%2C0.32491969623290584%7D%2C+%7B-1.3763819204711716%2C-0.3249196962329062%2C-0.8506508083520389%7D%2C+%7B0.850650808352039%2C0.850650808352039%2C-0.5257311121191329%7D%7D%29
console.log(o(
  [-0.5257311121191329,-0.5257311121191329,0.32491969623290584],
  [-1.3763819204711716,-0.3249196962329062,-0.8506508083520389],
  [0.850650808352039,0.850650808352039,-0.5257311121191329]
));

// WolframAlpha says this should be -ve: http://www.wolframalpha.com/input/?i=determinant%28%7B%7B-0.5257311121191329%2C0.32491969623290584%2C0%7D%2C+%7B-1.3763819204711716%2C-0.8506508083520389%2C-1.7013016167040775%7D%2C+%7B0.850650808352039%2C-0.5257311121191329%2C0%7D%7D%29
console.log(o(
  [-0.5257311121191329,0.32491969623290584,0],
  [-1.3763819204711716,-0.8506508083520389,-1.7013016167040775],
  [0.850650808352039,-0.5257311121191329,0]
));

function o(a, b, c) {
  return orient(a, b, c, [0, 0, 0]);
}

Orientation [4] reports 0 for not quite degenerate case

require('robust-orientation')[4]([0, 0, 0], [1e-256, 0, 0], [0, 0, 1], [0.5, 1e-256, 0.5]) evaluates to zero, but it should be nonzero because they aren't coplanar and no three are colinear, right?

polygon winding order

I'm trying to use this with polygons to determine the winding order. However, it seems to be suited for a small number of points (triangles and such mostly?).

In Chrome, the following with a larger set of points (e.g. 20+) tends to crash the browser:

var orientation = require('robust-orientation')
orientation.apply(orientation, path)

Is there a module better suited for this?

Consider unrolling functions explicitly, or in build step.

I'm running into issues using TurfJS, which depends on this package, because of a CSP issue: unsafe-eval (Turfjs/turf#261). This looks related to the use of new Function(...). Would it be possible to generate these functions as a build step, or write them out explicitly in the file?

My dependency tree is:

.
└─┬ @turf/[email protected]
  └─┬ @turf/[email protected]
    └─┬ [email protected]
      ├─┬ [email protected]
      │ └── [email protected]  deduped
      └── [email protected]

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.