1

I am developing a web app and I need to find a way to draw an outline rectangular polygon connecting the given points to form a perimeter on a coordinate system.

I found this ordering shuffled points that can be joined to form a polygon (in python) to be quite relevant to my problem, but it has the problem that, if any points surpasses the center of the polygon the algorithm does not work...

To make it more clear what I want I am attaching two pictures to show what I want to achieve with given points:

Correct way to join points

Correct way to connect points

Wrong way to connect points

Wrong way to connect points

Is there an algorithm that given point coordinates creates the rectangular perimeter as I want it? Thanks

Community
  • 1
  • 1
mitsos1os
  • 2,170
  • 1
  • 20
  • 34
  • 2
    Well.. This problem doesn't vanish even if you will consider only vertical and horizontal lines. Look at the letter "H" and place a dot at every corner of this letter (black pixels of "H" are inside the figure). You will get 12 dots that can't be connected in an unique way. How exactly you want to connect the dots? – JustAnotherCurious Mar 24 '15 at 13:56
  • Due to the nature of the web app, such designs won't be available, but if i should say, then for the 12 dots you mention, I would want for them to connect and form the H ! – mitsos1os Mar 24 '15 at 14:33
  • As JustAnotherCurious points out, this problem is quite underdetermined. Do you also know the order in which the points were drawn? If this is known, *and* the nature of your program means that every point is displaced from the previous point by either a vertical or horizontal line (i.e. never a diagonal line), then the problem becomes easy. – j_random_hacker Mar 24 '15 at 15:21
  • is the input of your app has some specific limitation? like are you sure the set of points must have a way to connected as a rectangular polygon? How about the input is like 3 points of a triangle? – shole Mar 25 '15 at 01:17
  • The order of points is unknown and they are always a rectangular polygon. Right now I have implemented an algorithm of my own but I was asking if someone new a more standard way for the specific problem because I couldn't find anything. I will provide my algorithm as an answer if no one else posts something. – mitsos1os Mar 25 '15 at 18:39
  • Did you find a solution to this? – Marin Oct 24 '18 at 17:40
  • @Marin I would be more than glad to share my solution, but unfortunately the project was abandoned couple years ago and I don't have kept the code... – mitsos1os Oct 25 '18 at 16:52
  • @mitsos1os appreciate it mitsos , your question is exactly like mine. Do you remember did you use Monotone or Graham's solution ? – Marin Oct 25 '18 at 17:07
  • @Marin, from what I remember I based my solution on moving only on vertical - horizontal lines from the beginning point.... But this might cause a problem if your dots, are not exactly on the same y coordinate, so moving directly vertical and horizontal would not meet the actual point. Maybe you could use some distance metrics – mitsos1os Oct 31 '18 at 10:33
  • @mitsos1os i tried counterclockwise sorting but didn't quite work, will have to try a few things. Thank you for taking the time to respond :) – Marin Oct 31 '18 at 20:30
  • 1
    @Marin I am sure you will find something that suits you! Good luck – mitsos1os Nov 01 '18 at 11:36

0 Answers0