CODEWITHSUNDEEP
algorithmspatialpoints
Bel
Bel

Reputation: 55

Algorithm to connect multiple points without inclusion

I am searching for an algorithm to connect multiple points without including one of the points. The requirement is that all points are connected but no points are in the interior of the resulting polygon. I was not sure what the technical term for this could be and did not find anything to solve my problem. The setting might look similar to this: Setting

I am not looking for a convex hull algorithm since it might include some points (In the image 2,6,8). The result should be close to the convex hull (as far as possible) but satisfy the requirement of not including any points. Any suggestions?

Upvotes: 1

Views: 118

Answers (2)

bigballer
bigballer

Reputation: 146

you can start with 0->1, 1->2, .. n-1 -> n, n->0 Now look at these lines and see if any of them cross over. If line a-b crosses line c-d, delete these two lines and create two new lines, line a-c and line a-d. Since we are removing crossings, the total length of all the lines is always decreasing, so it should converge to something with zero crossings and everything connected..

Upvotes: 1

Armen Avetisyan
Armen Avetisyan

Reputation: 1258

Start with a point then go to another one in a clockwise (or counter-clockwise fashion). According to Green's Formula you should be integrating the area (in the discrete case it amounts to counting your vertices).

clockwise procedure: Say you start with the top-most point xi

  • from all points right side of xi, pick the nearest below xi
  • if not existing: from all points left side of xi, pick the nearest below xi
  • if your reached the bottom-most point, you go now up but with the opposite recipe (i.e. check the left side first, then the right side)

Upvotes: 2

Related Questions