Skip to content

Detect self-intersecting polygons in Javascript. An implementation of the Bentley–Ottmann sweep line algorithm for detecting crossings in a set of line segments.

Notifications You must be signed in to change notification settings

calvinmetcalf/sweepline

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Detecting polygon self-intersection in Javascript

An implementation of the O((n + k) log n) Bentley–Ottmann sweep line algorithm for detecting crossings in a set of line segments. The aim was to make something to speedily detect self-intersecting polygons for client side validation before serialisation and storage, but there's not much to stop it being used serverside (except it being more a statement of intent than actual production ready code).

Despite intending it for the browser, it probably still needs some fettling to make sure the CommonJS-esque code I've written works in your target browser.

Development

  • node.js 0.45
  • expresso
  • underscore

Tests

To run the tests, ensure you have node.js and the expresso npm installed:

$ Make test

Note that this implementation currently doesn't validate polygons that share the same start and end vertex. Look at the tests for workarounds to this issue.

Licence

free

About

Detect self-intersecting polygons in Javascript. An implementation of the Bentley–Ottmann sweep line algorithm for detecting crossings in a set of line segments.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • JavaScript 75.9%
  • CSS 24.1%