wonder if seemingly unused tutorial function dos have other use

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

36 Replies - 947 Views - Last Post: 07 November 2018 - 09:10 PM Rate Topic: -----

#1 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 05:22 PM

I was reading this: https://www.geeksfor...hm-convex-hull/


But...

// Returns the square of distance between 
// p1 and p2. 
int dist(iPair p, iPair q) 
{ 
    return (p.second - q.second) * (p.second - q.second) + 
           (p.first - q.first) * (p.first - q.first); 
} 



...in the code dos not seem to be used. Is there some use with it could have that they just did not implement here? Better point ordering perhap? Is function only junk they forgot and left?

This post has been edited by sonar87: 04 November 2018 - 11:53 AM


Is This A Good Question/Topic? 0
  • +

Replies To: wonder if seemingly unused tutorial function dos have other use

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 14494
  • View blog
  • Posts: 58,107
  • Joined: 12-June 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 05:42 PM

I do not see that function in that link's code.
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 06:19 PM

I'm not seeing it either. Perhaps the OP has multiple tabs open and just got confused.
Was This Post Helpful? 0
  • +
  • -

#4 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1549
  • View blog
  • Posts: 4,929
  • Joined: 20-March 10

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 07:14 PM

The snippet of code shown comes from the Graham Scan Algorithm, the program shown implements the Quick Hull Algorithm and that is why it is never used it comes from a different algorithm set.

Perhaps the OP's task is to implement the Graham scan algorithm but can't find the code needed to do this online?

Dunno. :/
Was This Post Helpful? 1
  • +
  • -

#5 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 07:41 PM

Just looked again also, at original tab with it and opened link in same tab. check had some url and they did. I had also sent and email to the people owning the site to ask them but never heard back. Maybe it was junk and was now removed since for same url in old tab and new, the function only shows in old opened page. Sorry for confusing everyone.

View Postsonar87, on 03 November 2018 - 06:22 PM, said:

...in the code dos not seem to be used. Is there some use with convex hull it could have that they just did not implement here? Better point ordering perhap? Is function only junk they forgot and left?



Also asking this made me wonder... how would you make link's code order points better? Other hull algorithms order in clock or counter clockwise order but this for me had them not in the order you would visit them to make a hull?
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 08:21 PM

View Postsnoopy11, on 03 November 2018 - 10:14 PM, said:

The snippet of code shown comes from the Graham Scan Algorithm, the program shown implements the Quick Hull Algorithm and that is why it is never used it comes from a different algorithm set.

I was going to comment similarly, except that I saw the code for that site's Graham Scan used the class Point rather than the class iPair as posted by the OP, so I refrained.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 08:45 PM

View Postsonar87, on 03 November 2018 - 10:41 PM, said:

Also asking this made me wonder... how would you make link's code order points better? Other hull algorithms order in clock or counter clockwise order but this for me had them not in the order you would visit them to make a hull?

As the description for the implementation, it said it would return the points of the hull in ascending X coordinate order. That is simply a side effect of using the C++ std::set<> with the default comparer. If you don't like that behavior, you are free to change the comparer to change the order, or simply use a different C++ container.
Was This Post Helpful? 1
  • +
  • -

#8 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 09:04 PM

Also pay attention to the comments made on that page:

1. The implementation is actually O(n2) because it's not reducing the search set. The Wikipedia article says that QuickHull has a much better than than complexity, but you obviously have to implement it correctly.

2. Simply going with a std::vector<> will result in duplicate points on the hull. It looks like the person who wrote that code was also depending on the side effect of std::set<> merging duplicates.
Was This Post Helpful? 1
  • +
  • -

#9 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 09:11 PM

I'll also add that it looks like this vector is computed twice:
(p.second - p1.second) * (p2.first - p1.first) - 
(p2.second - p1.second) * (p.first - p1.first)



First, just the direction of the vector is checked by findSide() and if it is on the side of the line wanted, then the magnitude of the vector is computed by lineDist().
Was This Post Helpful? 1
  • +
  • -

#10 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 03 November 2018 - 09:31 PM

Thank you for all the info, likely would not of noticed that duplicate points. Looks like I have work to do to swap to vector.

Hmm yes. I guess that could be computed and then just abs() it in place of lineDist and pass it to the other for use.

Would ordered set keep them in correct order, not force them into the unwanted order that set puts them in, as a better choice than a vector?
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 04 November 2018 - 09:43 AM

The ordered set is still dependent on the comparer that is used.

Personally, if I were in your shoes, I would simply get the resulting std::set<> and then run the Jarvis march or Graham scan against it. Since all the points in the set are already known to be on the convex hull, it's just a matter of getting the points in the order that you prefer.
Was This Post Helpful? 1
  • +
  • -

#12 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 04 November 2018 - 11:18 AM

Crud, meant 'unordered'. But did look at it and seems that would not keep them in order put in either, unless I misunderstood it. I guess that should work to run the others on the result, except in bad case with lots of hull points, shouldn't take long after narrowing to just hull points.
Was This Post Helpful? 0
  • +
  • -

#13 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 04 November 2018 - 11:51 AM

I decided to see if could add custom comparer to help with point ordering because I was curious about it...

But with my point class it give a seg fault on lines in side of if block. I How would that happen? I thought seg fault was only accessing non existent elements. If it was inside if to check if it was empty first, then if it passed the condition and got in, should it not be fine? Why would it seg fault if pass not empty?

struct point
{
    int xval, yval;
    point(int xval, int yval) : x(xval), y(yval){ }
};

struct compar
{
    bool operator() (const point& a, const point& B)/>/> const
    {return true;}
};


std::set<point, compar> points;

point x(5,5);
points.insert(x);
if(!points.empty())
{
        int m = *points.begin(); // seg fault
        cout << m.x;
}






But here when I do with just int it is fine:

struct compar2 
{
    bool operator() (const int& a, const int& B)/>/> const
    {return true;}
};

std::set<int, compar2> points;

points.insert(5);
if(!points.empty())
{
        int m = *points.begin();
        cout << m;
}



Attached Image

This post has been edited by sonar87: 04 November 2018 - 12:35 PM

Was This Post Helpful? 0
  • +
  • -

#14 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6501
  • View blog
  • Posts: 22,256
  • Joined: 05-May 12

Re: wonder if seemingly unused tutorial function dos have other use

Posted 04 November 2018 - 12:54 PM

Does this even compile?
struct point
{
    int xval, yval;
    point(int xval, int yval) : x(xval), y(yval){ }
};



And how are you getting this to compile?
int m = *points.begin();


points is a set of points. How are you managing to assign that to an int?

And how did you get this to compile?
cout << m.x;


point has xval, not x.
Was This Post Helpful? 0
  • +
  • -

#15 sonar87   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 61
  • Joined: 04-February 08

Re: wonder if seemingly unused tutorial function dos have other use

Posted 04 November 2018 - 01:03 PM

Because I copied wrong thing and stupidly though could just fix it manually without messing it up....

Going to stop and take break and go over code again after.

This post has been edited by sonar87: 04 November 2018 - 01:17 PM

Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3