mourner / robust-predicates Goto Github PK

Fast robust predicates for computational geometry in JavaScript

License: The Unlicense

JavaScript 100.00%

computational-geometry robust-arithmetic floating-point predicates

robust-predicates's Introduction

robust-predicates

Fast robust predicates for computational geometry in JavaScript. Provides reliable 2D and 3D point orientation tests (orient2d, orient3d, incircle, insphere) that are not susceptible to floating point errors (without sacrificing performance). A modern port of Jonathan R Shewchuk's C code, an industry standard since 1996.

Figure: non-robust vs robust orient2d test for points within a tiny range (2^-42).

Demo

API

Note: unlike J. Shewchuk's original code, all the functions in this library assume y axis is oriented downwards ↓, so the semantics are different.

`orient2d(ax,ay, bx,by, cx,cy)`

Returns a positive value if the points a, b, and c occur in counterclockwise order (c lies to the left of the directed line defined by points a and b).
Returns a negative value if they occur in clockwise order (c lies to the right of the directed line ab).
Returns zero if they are collinear.

The result is also an approximation of twice the signed area of the triangle defined by the three points.

`incircle(ax,ay, bx,by, cx,cy, dx,dy)`

Returns a positive value if the point d lies outside the circle passing through a, b, and c.
Returns a negative value if it lies inside.
Returns zero if the four points are cocircular.

The points a, b, and c must be in counterclockwise order, or the sign of the result will be reversed.

`orient3d(ax,ay,az, bx,by,bz, cx,cy,cz, dx,dy,dz)`

Returns a positive value if the point d lies above the plane passing through a, b, and c, meaning that a, b, and c appear in counterclockwise order when viewed from d.
Returns a negative value if d lies below the plane.
Returns zero if the points are coplanar.

The result is also an approximation of six times the signed volume of the tetrahedron defined by the four points.

`insphere(ax,ay,az, bx,by,bz, cx,cy,cz, dx,dy,dz, ex,ey,ez)`

Returns a positive value if the point e lies outside the sphere passing through a, b, c, and d.
Returns a negative value if it lies inside.
Returns zero if the five points are cospherical.

The points a, b, c, and d must be ordered so that they have a positive orientation (as defined by orient3d), or the sign of the result will be reversed.

`orient2dfast`, `orient3dfast`, `incirclefast`, `inspherefast`

Simple, approximate, non-robust versions of predicates above. Use when robustness isn't needed.

Example

import {orient2d} from 'robust-predicates';

const ccw = orient2d(ax, ay, bx, by, cx, cy) > 0;

Install

Install with npm install robust-predicates or yarn add robust-predicates, or use one of the browser builds:

predicates.min.js (all predicates)
orient2d.min.js (orient2d, orient2dfast)
orient3d.min.js (orient3d, orient3dfast)
incircle.min.js (incircle, incirclefast)
insphere.min.js (insphere, inspherefast)

Thanks

This project is just a port — all the brilliant, hard work was done by Jonathan Richard Shewchuk.

The port was also inspired by Mikola Lysenko's excellent Robust Arithmetic Notes and related projects like robust-orientation and robust-in-sphere.

License

Since the original code is in the public domain, this project follows the same choice. See Unlicense.

robust-predicates's People

Contributors

Stargazers

Watchers

Forkers

i5anoff ani2fun y-71 crocla benbro sailing-3d lbc3402785 gonnavis jianantian tech-projects-spb usnul stevancris tybor huite jianyunli awsl12581 tinko92

robust-predicates's Issues

What's the ETA for a TypeScript version?

Great library!

Since it has the type file to be TypeScript compatible I can use this JavaScript implementation in my TypeScript code,
Unfortunately, in my tests, using jest, I am getting an error that I was not able to overcome.
Also, I'd like to use macros in my code as well and learn from the TypeScript implementation.

Error:

$ yarn test
yarn run v1.22.17
$ jest
 FAIL  test/unit/MathUtils.spec.ts
  ● Test suite failed to run

    Jest encountered an unexpected token

    Jest failed to parse a file. This happens e.g. when your code or its dependencies use non-standard JavaScript syntax, or when Jest is not configured to support such syntax.

    Out of the box Jest supports Babel, which will be used to transform your files into valid JS based on your Babel configuration.

    By default "node_modules" folder is ignored by transformers.

    Here's what you can do:
     • If you are trying to use ECMAScript Modules, see https://jestjs.io/docs/ecmascript-modules for how to enable it.
     • If you are trying to use TypeScript, see https://jestjs.io/docs/getting-started#using-typescript
     • To have some of your "node_modules" files transformed, you can specify a custom "transformIgnorePatterns" in your config.
     • If you need a custom transformation specify a "transform" option in your config.
     • If you simply want to mock your non-JS modules (e.g. binary assets) you can stub them out with the "moduleNameMapper" config option.

    You'll find more details and examples of these config options in the docs:
    https://jestjs.io/docs/configuration
    For information about custom transformations, see:
    https://jestjs.io/docs/code-transformation

    Details:

    /home/user/project/node_modules/robust-predicates/index.js:2
    export {orient2d, orient2dfast} from './esm/orient2d.js';
    ^^^^^^

    SyntaxError: Unexpected token 'export'

      1 | /* eslint-disable no-constant-condition */
      2 |
    > 3 | import {orient2d} from 'robust-predicates';
        | ^
      4 |
      5 | const EPSILON = Math.pow(2, -52);
      6 | const EDGE_STACK = new Uint32Array(512);

      at Runtime.createScriptFromCode (node_modules/jest-runtime/build/index.js:1728:14)
      at Object.<anonymous> (src/components/Delaunator.ts:3:1)

Test Suites: 1 failed, 1 total
Tests:       0 total
Snapshots:   0 total
Time:        16.894 s
Ran all test suites.
error Command failed with exit code 1.
info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.

Possible bug in orient2d

I'm not sure if this is a bug in concaveman or robust-predicates but I'm getting different results when trying to replace robust-orientation with this library (see rationale).

I've published a runkit here or the same thing is inline below

const rpOrient = require('robust-predicates/umd/orient2d.min.js').orient2d;

const orient = require("robust-orientation")

function intersects(p1, q1, p2, q2) {
    return p1 !== q2 && q1 !== p2 &&
        orient(p1, q1, p2) > 0 !== orient(p1, q1, q2) > 0 &&
        orient(p2, q2, p1) > 0 !== orient(p2, q2, q1) > 0;
}

function intersectsWithRp(p1, q1, p2, q2) {
    return p1 !== q2 && q1 !== p2 &&
        rpOrient(p1, q1, p2) > 0 !== rpOrient(p1, q1, q2) > 0 &&
        rpOrient(p2, q2, p1) > 0 !== rpOrient(p2, q2, q1) > 0;
}


const edge1 = [[-122.0607, 37.3849], [-122.0610, 37.3841]]

const edge2 = [[-122.0607, 37.3847], [-122.0607, 37.3848]]

console.log('with robust-orientation', intersects(edge1[0], edge2[0], edge1[1], edge2[1]))
// => with robust-orientation, true

console.log('with robust-predicates', intersectsWithRp(edge1[0], edge2[0], edge1[1], edge2[1]))
// => with robust-predicates, false

If was to hazard a guess I'd say it's something to do with appearance of -122.0607 three times, indicating one edge is vertical. Here is a pic of the edges being tested

I'm not the best at maths so I though I'd submit for consideration so whether this is an issue with robust predicates or the edge intersection function, not sure :)

Hope the narrow test case helps
Cheers
Rowan

index.d.ts isn't found in the NPM package

The package.json points to an index.d.ts but that file doesn't exist in the package.

Better test coverage for orient3d

Current coverage stats (using npm run cov):

incircle.js: 28.37%
insphere.js: 51.21%
orient2d.js: 98.8%
orient3d.js: 17.58%
util.js: 96.77%

The tests for incircle, insphere and orient3d are pretty basic and don't exercise a lot of the harder cases — it would be great to improve the coverage here. PRs for that are welcome!

Undocumented: `orient2d` returns -0, not +0

For all the cases I tested, orient2d returns -0, not +0 as I would have assumed, since the readme doesn't specify a sign. Is this always the case? If not, under what circumstances would it not be?

One interesting (although possibly out-of-scope) idea for remedying this asymmetry for collinear points would be to return +0 if b is between a and c, and -0 otherwise (or vice versa). That would allow distinguishing between 0º and 180º angles, which might be kinda cool. (Like for example, one use-case for that could be checking the convexity of a polygon... you can make only same-sign turns and 0º turns, but not 180º turns). Effectively that would mean the half-open interval [0º, 180º) would be positive-signed and [180º, 360º) would be negative-signed, which seems a bit more symmetric & informative than the current behavior of the open interval (0º, 180º) positive-signed and closed interval [180º, 360º] negative-signed. Food for thought 😄

Adding repository url

On webjar.org, deployment failed because of missing repository.url.

Please refer: webjars/webjars#1909 , for more information.

In order resolve missing url repo, package.json must be added repository.url

"repository": {
    "url": "git+https://github.com/mourner/robust-predicates.git",
    "type": "git"
  }

Orient3d: Clarification needed on behavior of Y axis

The README says:

All the functions in this library assume y axis is oriented downwards ↓, so the semantics are different

However when I looked at the code for orient3d, it seems completely identical to Shewchuk's original code (no negations etc. as seen in orient2d)... does this mean the Y axis is right-side up again or am I missing something?

(As far as I'm concerned, the closer to replicating the exact semantics of the original code, the better... so I have no concerns about the Y axis being in the correct orientation, as it makes porting code way easier without having to negate everything. Just want to make sure that's the case... and if so the documentation might need a clarification.)