How do I make an algorithm for tracing lines given a set a points?
I need an algorithm to position lines on a set of points in a 2D environment. The algorithm should identify collinear points within a specified tolerance and place lines accordingly. Each resulting line should include its position, orientation, and length as part of the output. Points will be given in a table all being in order one after the other.
The points will be ordered in a sequence one after the other, just like this: Example of points placement & order
// Example input for testing
const table = [
{ Position: [0.849999487, -1.47224224] },
{ Position: [0.848479152, -1.01117814] },
{ Position: [0.842648506, -0.707066119] },
{ Position: [0.848704576, -0.489999771] },
{ Position: [0.845723033, -0.307818025] },
{ Position: [0.846934378, -0.149337426] },
{ Position: [0.859999716, 0] },
{ Position: [0.846934378, 0.149337381] },
{ Position: [0.845723033, 0.307817996] },
{ Position: [0.848704517, 0.489999801] },
{ Position: [0.842648506, 0.707066059] },
{ Position: [0.848479271, 1.01117814] },
{ Position: [0.599999666, 1.03923011] },
{ Position: [0.376222014, 1.03366148] },
{ Position: [0.184067041, 1.04389584] },
{ Position: [0, 1.0399996] },
{ Position: [-0.184066996, 1.04389584] },
{ Position: [-0.376221985, 1.03366148] },
{ Position: [-0.599999726, 1.03922999] },
{ Position: [-0.874190629, 1.04181993] },
{ Position: [-1.24099123, 1.04131532] }
];
Here's an example of what I'm looking for: Example of desired behavior
You can write the algorithm in any language of your preference.
Currently, I am using the area of the triangle formed by 3 consecutive points to check if it is lower than the tolerance. This works, but it's not perfect. I need a more robust method. I will show you below some of the results I get, and how they're problematic.
Errors with this algorithm:
1. The points are almost perfectly colinear, but when there's a change in direction the algorithm thinks that the next point is still part of the sequence, because of how close they are: Issue 1
2. The first & last point are considered to form a line, but they don't because of how much space there is between one and the other: Issue 2
function getBoundaryWalls2(points) {
const COLLINEAR_TOLERANCE = 0.05; // How strict the line detection is
const MIN_LINE_LENGTH = 1; // Minimum length for a valid line
const walls = [];
// Checks if 3 points form a nearly straight line by calculating triangle area
function areCollinear(p1, p2, p3) {
const x1 = p1.position.x, y1 = p1.position.y;
const x2 = p2.position.x, y2 = p2.position.y;
const x3 = p3.position.x, y3 = p3.position.y;
// If area of triangle is near 0, points are almost collinear
const area = Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2);
return area < COLLINEAR_TOLERANCE;
}
// Gets angle between two points in degreesS
function getAngle(p1, p2) {
const dx = p2.position.x - p1.position.x;
const dy = p2.position.y - p1.position.y;
return (Math.atan2(dy, dx) * 180 / Math.PI);
}
// Gets distance between two points
function getDistance(p1, p2) {
const dx = p2.position.x - p1.position.x;
const dy = p2.position.y - p1.position.y;
return Math.sqrt(dx * dx + dy * dy);
}
let i = 1;
while (i < points.length - 1) {
// Start a new potential line with two points
const currentLine = {
startPoint: points[i],
endPoint: points[i + 1],
points: [points[i], points[i + 1]]
};
// Try to extend the line by adding more collinear points
let j = i + 2;
while (j < points.length) {
if (areCollinear(currentLine.startPoint, currentLine.endPoint, points[j])) {
currentLine.endPoint = points[j];
currentLine.points.push(points[j]);
j++;
} else {
break;
}
}
// If line is long enough, create a wall
const length = getDistance(currentLine.startPoint, currentLine.endPoint);
if (length >= MIN_LINE_LENGTH) {
// Calculate wall center
const centerX = (currentLine.startPoint.position.x + currentLine.endPoint.position.x) / 2;
const centerY = (currentLine.startPoint.position.y + currentLine.endPoint.position.y) / 2;
// Get wall orientation
const orientation = getAngle(currentLine.startPoint, currentLine.endPoint);
// Create wall object
const wall = {
position: { x: centerX, y: centerY },
orientation: orientation,
length: length,
points: currentLine.points
};
walls.push(wall);
}
// Skip to next unprocessed point
i += currentLine.points.length - 1;
}
return walls;
}
Solution
Here is my C++ code to check for three points on a line
bool cLinify::isLine(
const cxy &p1,
const cxy &p2,
const cxy &p3)
{
const double COLLINEAR_TOLERANCE = 0.005;
// triangle area method
//(x2−x1)(y3−y1)=(x3−x1)(y2−y1)
// https://math.stackexchange.com/questions/38338/methods-for-showing-three-points-in-mathbbr2-are-colinear-or-not/221530#221530
return abs((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)) < COLLINEAR_TOLERANCE;
}
Here is my code to find lines in between points using this method
void cLinify::solve()
{
cxy lp1, lp2;
for (int k = 0; k < myPoints.size() - 2; k++)
{
if( k == 0 )
{
lp1 = myPoints[0];
lp2 = myPoints[1];
continue;
}
if (isLine(myPoints[k-1], myPoints[k], myPoints[k + 1]))
{
// extend line
lp2 = myPoints[k+1];
}
else
{
// line ended
myLines.push_back(std::make_pair(lp1, lp2));
lp1 = lp2;
}
}
myLines.back() = std::make_pair(lp1, myPoints.back());
}
Here is the output produced from your sample points
The complete application code
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <wex.h> // https://github.com/JamesBremner/windex
#include "cStarterGUI.h"
#include "cxy.h" // https://github.com/JamesBremner/raven-set
struct cLinify
{
std::vector<cxy> myPoints;
std::vector<std::pair<cxy, cxy>> myLines;
cLinify(const std::vector<cxy> &points);
void solve();
void displayLines();
bool isLine(
const cxy &p1,
const cxy &p2,
const cxy &p3);
std::vector<double> box();
bool test();
std::vector<cxy>& getPoints()
{
return myPoints;
}
std::vector<std::pair<cxy, cxy>> getLines()
{
return myLines;
}
};
bool cLinify::isLine(
const cxy &p1,
const cxy &p2,
const cxy &p3)
{
const double COLLINEAR_TOLERANCE = 0.005;
// triangle area method
//(x2−x1)(y3−y1)=(x3−x1)(y2−y1)
// https://math.stackexchange.com/questions/38338/methods-for-showing-three-points-in-mathbbr2-are-colinear-or-not/221530#221530
return abs((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)) < COLLINEAR_TOLERANCE;
}
cLinify::cLinify(const std::vector<cxy> &points)
: myPoints(points)
{
}
void cLinify::solve()
{
cxy lp1, lp2;
for (int k = 0; k < myPoints.size() - 2; k++)
{
if( k == 0 )
{
lp1 = myPoints[0];
lp2 = myPoints[1];
continue;
}
if (isLine(myPoints[k-1], myPoints[k], myPoints[k + 1]))
{
// extend line
lp2 = myPoints[k+1];
}
else
{
// line ended
myLines.push_back(std::make_pair(lp1, lp2));
lp1 = lp2;
}
}
myLines.back() = std::make_pair(lp1, myPoints.back());
}
void cLinify::displayLines()
{
for (auto &l : myLines) {
std::cout
<< "( " << l.first.x << ", " << l.first.y
<< " ) to ( " << l.second.x << ", " << l.second.y
<< " )\n";
}
}
std::vector<double> cLinify::box()
{
cxy topleft;
topleft = myPoints[0];
for (auto &p : myPoints)
{
if (p.x < topleft.x)
topleft.x = p.x;
if (p.y < topleft.y)
topleft.y = p.y;
}
cxy wh(0, 0);
for (auto &p : myPoints)
{
if (p.x - topleft.x > wh.x)
wh.x = p.x - topleft.x;
if (p.y - topleft.y > wh.y)
wh.y = p.y - topleft.y;
}
std::vector<double> ret;
double xscale = 400 / wh.x;
double yscale = 400 / wh.y;
if (yscale < xscale)
ret.push_back(yscale);
else
ret.push_back(xscale);
ret.push_back( topleft.x);
ret.push_back( topleft.y);
return ret;
}
bool cLinify::test()
{
cLinify L({cxy(1, 1),
cxy(2, 2),
cxy(3, 3)});
if (!L.isLine(cxy(1, 1), cxy(2, 2), cxy(3, 3)))
return false;
if (L.isLine(cxy(1, 1), cxy(2, 2), cxy(3, 3.1)))
return false;
std::cout << "unit test passed\n";
return true;
}
class cGUI : public cStarterGUI
{
public:
cGUI(cLinify &L)
: cStarterGUI(
"Linify",
{50, 50, 1000, 500}),
myLinify(L)
{
show();
run();
}
virtual void draw(wex::shapes &S);
private:
cLinify &myLinify;
};
void cGUI::draw(wex::shapes &S)
{
auto thebox = myLinify.box();
S.color(0);
for( auto& p : myLinify.getPoints() )
{
int x = 10 + thebox[0] * ( p.x - thebox[1] );
int y = 10 + thebox[0] * ( p.y - thebox[2] );
S.circle( x, y, 5 );
}
S.color(0x0000FF);
for( auto& l : myLinify.getLines())
{
std::vector<int> vl
{
10 + thebox[0] * ( l.first.x - thebox[1] ),
10 + thebox[0] * ( l.first.y - thebox[2] ),
10 + thebox[0] * ( l.second.x - thebox[1] ),
10 + thebox[0] * ( l.second.y - thebox[2] )
};
S.line(vl);
}
}
main()
{
/*
// Example input for testing
const table = [
{ Position: [0.849999487, -1.47224224] },
{ Position: [0.848479152, -1.01117814] },
{ Position: [0.842648506, -0.707066119] },
{ Position: [0.848704576, -0.489999771] },
{ Position: [0.845723033, -0.307818025] },
{ Position: [0.846934378, -0.149337426] },
{ Position: [0.859999716, 0] },
{ Position: [0.846934378, 0.149337381] },
{ Position: [0.845723033, 0.307817996] },
{ Position: [0.848704517, 0.489999801] },
{ Position: [0.842648506, 0.707066059] },
{ Position: [0.848479271, 1.01117814] },
{ Position: [0.599999666, 1.03923011] },
{ Position: [0.376222014, 1.03366148] },
{ Position: [0.184067041, 1.04389584] },
{ Position: [0, 1.0399996] },
{ Position: [-0.184066996, 1.04389584] },
{ Position: [-0.376221985, 1.03366148] },
{ Position: [-0.599999726, 1.03922999] },
{ Position: [-0.874190629, 1.04181993] },
{ Position: [-1.24099123, 1.04131532] }
];
*/
cLinify L({cxy(0.849999487, -1.47224224),
cxy(0.848479152, -1.01117814),
cxy(0.842648506, -0.707066119),
cxy(0.848704576, -0.489999771),
cxy(0.845723033, -0.307818025),
cxy(0.846934378, -0.149337426),
cxy(0.859999716, 0),
cxy(0.846934378, 0.149337381),
cxy(0.845723033, 0.307817996),
cxy(0.848704517, 0.489999801),
cxy(0.842648506, 0.707066059),
cxy(0.848479271, 1.01117814),
cxy(0.599999666, 1.03923011),
cxy(0.376222014, 1.03366148),
cxy(0.184067041, 1.04389584),
cxy(0, 1.0399996),
cxy(-0.184066996, 1.04389584),
cxy(-0.376221985, 1.03366148),
cxy(-0.599999726, 1.03922999),
cxy(-0.874190629, 1.04181993),
cxy(-1.24099123, 1.04131532)});
L.test();
L.solve();
L.displayLines();
cGUI theGUI(L);
return 0;
}
Complete VSCODE project at https://github.com/JamesBremner/linify
- Efficient calculation of Fibonacci series
- What is the best algorithm for overriding GetHashCode?
- Picking a random element from a set
- How to generate combinations in chunks
- How do I check if an array includes a value in JavaScript?
- Why is O(n) better than O( nlog(n) )?
- Geometric series: calculate quotient and number of elements from sum and first & last element
- Algorithm to find all the exact divisors of a given integer
- Fastest way to generate binomial coefficients
- Enumerate all full (labeled) binary tree
- What's the best way to write `indexBy` in Scala?
- In Dijkstra's algorithm why must it first expand nodes with the current least cost?
- Distance between every Vertices in Graph
- Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
- Is there any easy way to do modulus of 2³² - 1 operation?
- Difference between Big-O and Little-O Notation
- Solving a simultaneous equation through code
- Number of paths using k coins
- Infix to postfix algorithm that takes care of unary operators
- What would cause an algorithm to have O(log log n) complexity?
- Algorithm to create a singly linked list
- Why does cache use Most Recently Used (MRU) algorithm as evict policy?
- How to check if a number is a power of 2
- How to define a normal Markov algorithm (NMA) to swap two ternary numbers separated by the symbol "^"?
- Enumerating all paths in a directed acyclic graph
- Segmented Sieve of Eratosthenes?
- what is the output of this simple recursive function? can you explain in detail?
- Does lower_bound() return the same result with reverse iterators of a vector in increasing order vs forward iterators of a vector in decreasing order?
- Insert sequence of formatting that can overlap into a string at specific locations
- How to sort two arrays with one being sorted based on the sorting of the other?