Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

clean-pslg

Package Overview
Dependencies
Maintainers
1
Versions
5
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

clean-pslg

Remove self intersections, t-junctions and duplicate edges/vertices from a planar straight line graph

  • 1.0.1
  • Source
  • npm
  • Socket score

Version published
Weekly downloads
22K
increased by2.05%
Maintainers
1
Weekly downloads
 
Created
Source

clean-pslg

Resolves all self intersections, t-junctions, and removes duplicate vertices/edges from a planar straight line graph using iterated snap rounding.

Demo

Click on the following link to try out clean-pslg in your browser:

  • Demo link

Example

This module really only does one thing, which is clean up planar straight line graphs. You invoke it by passing it an array of points and an array of edges like so:

var cleanPSLG = require('clean-pslg')

//Create a planar straight line graph with many degenerate crossings
var points      = [
  [ 0.25, 0.5  ],
  [ 0.75, 0.5  ],
  [ 0.5,  0.25 ],
  [ 0.5,  0.75 ],
  [ 0.25, 0.25 ],
  [ 0.75, 0.75 ],
  [ 0.25, 0.75 ],
  [ 0.75, 0.25 ]
]

//These are the edges of the graph
//They are defined by pairs of indices of vertices
var edges       = [
  [0, 1],
  [2, 3],
  [4, 5],
  [6, 7]
]

//Run clean up on the graph
if(cleanPSLG(points, edges)) {
  console.log('removed degeneracies from graph')
}

//clean-pslg operates on the graph in place, so after running it the points/edges will be modified
console.log('points = \n', points)
console.log('edges = \n', edges)
Output

The program will output the following text:

removed degeneracies from graph
points =
 [ [ 0.25, 0.5 ],
  [ 0.75, 0.5 ],
  [ 0.5, 0.25 ],
  [ 0.5, 0.75 ],
  [ 0.25, 0.25 ],
  [ 0.75, 0.75 ],
  [ 0.25, 0.75 ],
  [ 0.75, 0.25 ],
  [ 0.5, 0.5 ] ]
edges =
 [ [ 8, 0 ],
  [ 1, 8 ],
  [ 8, 2 ],
  [ 3, 8 ],
  [ 8, 4 ],
  [ 5, 8 ],
  [ 8, 6 ],
  [ 7, 8 ],
  [ 8, 8 ] ]

Visually, this corresponds to the following refinement of a planar graph:

Install

npm i clean-pslg

API

require('clean-pslg')(points, edges)

Processes an unoriented planar straight line graph defined by points and edges in place.

  • points is an array encoding the vertices of the planar straight line graph as pairs of numbers
  • edges is an array encoding the edges of the planar straight line graph as pairs of indices

The following degeneracies are handled:

  • Duplicate points are merged
  • Duplicate edges are merged
  • T-junctions are split
  • Edge crossings are split

The resulting graph meets all invariants required by cdt2d, so it may be triangulated. Note that this procedure does not preserve orientation.

Returns true if repairs were necessary, otherwise false

Note This is a destructive procedure, which means that the contents of points and edges may change. If you don't want this to happen, you should make a deep copy of points and edges before calling clean-pslg

License

(c) 2015 Mikola Lysenko. MIT License

Keywords

FAQs

Package last updated on 28 Jun 2015

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc