CODEWITHSUNDEEP
algorithmgeometry
dragon_carr
dragon_carr

Reputation: 1

Algorithm to generate rectangle coordinates given a set of points

I have a set of points on 2D plane, each has its screen coordinates X and Y. They are placed this way:

enter image description here

You see they are placed in horizontal lines, but X coordinate is quite random. A number of points in each line is not necessarily the same.

Given these coordinates, I need to generate triangles so that each edge of the triangle connects a pair of points which are close to each other, if possible:

enter image description here

Is there any known algorithm or library for this?

Upvotes: 0

Views: 371

Answers (1)

MBo
MBo

Reputation: 80297

You need point set triangulation.

In described case Delaunay triangulation should give desired result.

Library by J.R.Shewchuk (and it's not hard to find triangulation implementation for any popular language)

Upvotes: 2

Related Questions