OCDots

OCDots is a javascript library for creating evenly distributed points inside a polygon

codecov CodeFactor npm version License: GPL v3

ocdots

Check the demo!

Quick Start

OCDots uses physics to maximize the distance between each point and also the distance to the walls of a polygon. It is possible to follow each step of the process calling movePoints, or call relaxPoints to run several iterations and see the final state.

Import the library, then call movePoints on a set of points to run one iteration

const polygon = [
  [0, 0],
  [0, 500],
  [500, 500],
  [500, 0],
  [0, 0],
];
const points = [
  [10, 10],
  [20, 20],
  [30, 30],
  [40, 40],
  [50, 50],
  [60, 60],
  [70, 70],
  [80, 80],
  [90, 91],
];
let momentum = points.map(() => [0, 0]);
const newPoints = ocdots.movePoints({
  points,
  momentum,
  polygon,
}); // Points closer to the relaxed position
// newPoints:
// [[13.535794548720887, 13.535273243928348],
// [23.27147728369301, 23.266677836465515],
// [31.254830565917008, 31.24699231498995],
// [41.28615235332842, 41.272681142242014],
// [51.958871850605114, 51.93302052874113],
// [63.120940102952105, 63.061513386276076],
// [73.60106973613009, 73.4687601178992],
// [83.7612857566466, 83.29434810802492],
// [93.40654447613721, 94.65998015460454]]

Or call relaxPoints to run several iterations:

const polygon = [
  [0, 0],
  [0, 500],
  [500, 500],
  [500, 0],
  [0, 0],
];
const points = [
  [10, 10],
  [20, 20],
  [30, 30],
  [40, 40],
  [50, 50],
  [60, 60],
  [70, 70],
];
const iterations = 600;
const newPoints = ocdots.relaxPoints({
  points,
  polygon,
  iterations,
}); // Points closer to the relaxed position, 600 iterations
// newPoints:
// [[102.97786539754973, 102.93913654344668],
// [249.88751973067804, 95.97842402445758],
// [95.85157380539883, 249.581118685883],
// [249.83589254388568, 250.64858636270534],
// [103.38882973892018, 396.3498058144843],
// [396.8795797129724, 103.0543405820668],
// [249.77618266302204, 404.4383179086723],
// [404.0862954198404, 249.7401659115181],
// [396.995879400969, 396.84327821075937]]

Install

Install with npm:

npm install ocdots

To use with node just import the module:

const ocdots = require("ocdots");
ocdots.movePoints(...);

In the browser import the script as a module:

<script type="module">
  import * as ocdots from './node_modules/ocdots/dist.browser/ocdots.js';
  ocdots.movePoints(...);
</script>

You can also download ocdots.js and alongside with simplify.js and import as you prefer.

Usage

ocdots provides several functions to iterate a set of points in a polygon. All functions must be called with named parameters

movePoints(config) ⇒ Array.<Array>

Moves points according to the applied forces into it. The forces are: 1) between points, 2) between the point and walls of the polygon.

The points moves according to it’s momentum up to maxMomentum. Drag reduces the momentum with the square of the momentum. Viscosity lowers the momentum of points with high forces.

Runs one iteration

Kind: global function
Returns: Array.<Array> - points, momentum - Updated points and momentum arrays

Param Type Description
config Object configuration object
congig.points Array The points to move
config.momentum Array Accumulated momentum for each point. [0, 0] when the points are stopped.
config.polygon Array Set of points that describes the polygon that contains the points. This polygon should be ordered (clockwise or anticlockwise) and closed i.e. first points equals the last point.
config.mass Array.<Number> | Number Mass or masses of the points.
config.charge Array.<Number> | Number Charge or charges of the points.
[config.baseForce] Number The force constant
[config.drag] Number The drag coeficient
[config.viscosity] Number The viscosity coeficient
[config.maxMomentum] Number Maximum momentum for each point
[config.parallelForces] Boolean Sum line segmen parallel forces as well.
[config.wallForces] Number Walls forces constant
[config.simplifyPolygon] Number Simplify polygon tolerance (0 disabled)

randomInPolygon(N, polygon) ⇒ Array

Creates N points inside the polygon

Kind: global function
Returns: Array - points N points inside the polygon

Param Type Description
N Number Number of points
polygon Array Set of points that describes the polygon. This polygon should be ordered (clockwise or anticlockwise) and closed i.e. first points equals the last point.

randomInGeoPolygon(N, geoPolygon) ⇒ Array

Creates N points inside a geo polygon,

Kind: global function
Returns: Array - points N points inside the geo polygon

Param Type Description
N Number Number of points
geoPolygon Array Polygon of geo coordinates {lat, lng}

relaxPoints(config) ⇒ Array

Runs several iterations of movePoints(). The drag increases in every iteration attenuating the movement.

Kind: global function
Returns: Array - points Last iteration points positions

Param Type Description
config Object configuration object
config.points Array The points to move
config.momentum Array Initial momentum. [0, 0] for all points if ommited
config.polygon Array Set of points that describes the polygon that contains the points. This polygon should be ordered (clockwise or anticlockwise) and closed i.e. first points equals the last point.
config.iterations Number Number of iterations to run
[config.callback] function Callback function to run at every iteration (optional). Callback args: points, momentum, polygon, baseForce, currentDrag, viscosity, maxMomentum
config.mass Array.<Number> | Number Mass or masses of the points.
config.charge Array.<Number> | Number Charge or charges of the points.
[config.baseForce] Number The force constant
[config.drag] Number The drag coeficient
[config.viscosity] Number The viscosity coeficient
[config.maxMomentum] Number Maximum momentum for each point
[config.parallelForces] Boolean Sum line segmen parallel forces as well.
[config.wallForces] Number Walls forces constant
[config.simplifyPolygon] Number Simplify polygon tolerance (0 disabled)
[config.attenuation] Number Rate of attenuation

relaxNPoints(config) ⇒ Array

Calls relaxPoints for N random points placed inside the polygon.

Kind: global function
Returns: Array - points Last iteration points positions

Param Type Description
config Object configuration object
config.N Number Number of points
config.polygon Array Set of points that describes the polygon that contains the points. This polygon should be ordered (clockwise or anticlockwise) and closed i.e. first points equals the last point.
config.iterations Number Number of iterations to run
[config.callback] function Callback function to run at every iteration (optional). Callback args: points, momentum, polygon, baseForce, currentDrag, viscosity, maxMomentum
config.mass Array.<Number> | Number Mass or masses of the points.
config.charge Array.<Number> | Number Charge or charges of the points.
[config.baseForce] Number The force constant
[config.drag] Number The drag coeficient
[config.viscosity] Number The viscosity coeficient
[config.maxMomentum] Number Maximum momentum for each point
[config.parallelForces] Boolean Sum line segmen parallel forces as well.
[config.wallForces] Number Walls forces constant
[config.simplifyPolygon] Number Simplify polygon tolerance (0 disabled)
[config.attenuation] Number Rate of attenuation

relaxGeoPoints(config) ⇒ Object

Converts geoPoints and geoPolygon to a points and polygon, then calls relaxPoints, returning the last position of the points.

Kind: global function
Returns: Object - { polygon, points, geoPoints } Last iteration geo points positions

Param Type Description
config Object configuration object
config.geoPoints Array Points in geo coordinates {lat, lng}
config.geoPolygon Array Polygon of geo coordinates {lat, lng}
config.width Number Width of the polygon
config.iterations Number Number of iterations to run
[confi.callback] function Callback function to run at every iteration. Callback args: points, momentum, polygon, baseForce, currentDrag, viscosity, maxMomentum
config.mass Array.<Number> | Number Mass or masses of the points.
config.charge Array.<Number> | Number Charge or charges of the points.
[config.baseForce] Number The force constant
[config.drag] Number The drag coeficient
[config.viscosity] Number The viscosity coeficient
[config.maxMomentum] Number Maximum momentum for each point
[config.parallelForces] Boolean Sum line segmen parallel forces as well.
[config.wallForces] Number Walls forces constant
[config.simplifyPolygon] Number Simplify polygon tolerance (0 disabled)
[config.attenuation] Number Rate of attenuation

relaxNGeoPoints(config) ⇒ Object

Calls relaxGeoPoints for N random points placed inside the polygon.

Kind: global function
Returns: Object - { polygon, points, geoPoints } Last iteration geo points positions

Param Type Description
config Object configuration object
config.N Number Number of points
config.geoPolygon Array Polygon of geo coordinates {lat, lng}
config.width Number Width of the polygon
config.iterations Number jNumber of iterations to run
[config.callback] function Callback function to run at every iteration. Callback args: points, momentum, polygon, baseForce, currentDrag, viscosity, maxMomentum
config.mass Array.<Number> | Number Mass or masses of the points.
config.charge Array.<Number> | Number Charge or charges of the points.
[config.baseForce] Number The force constant
[config.drag] Number The drag coeficient
[config.viscosity] Number The viscosity coeficient
[config.maxMomentum] Number Maximum momentum for each point
[config.parallelForces] Boolean Sum line segmen parallel forces as well.
[config.wallForces] Number Walls forces constant
[config.simplifyPolygon] Number Simplify polygon tolerance (0 disabled)
[config.attenuation] Number Rate of attenuation

buildPolygon(geoPolygon, width) ⇒ Object

Transforms a set of coordinates into a polygon with a known width

Kind: global function
Returns: Object - { polygon, minLat, minLng, delta }

Param Type Description
geoPolygon Array Polygon of geo coordinates {lat, lng}
width Number Width of the polygon

License

OCDots Copyright (C) 2020 Luiz Eduardo Amaral luizamaral306@gmail.com

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License


Check out the repo

me

The world is a complex puzzle, and I love using data and code to decode it. Data scientist and developer by day, problem-solver always.