Results 1 to 14 of 14

Thread: Idea how to solve one problem

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Idea how to solve one problem

    Hello all today I found one problem which I think is very interesting.
    On the picture below you can see blue points which are X & Y coordinates.
    After entering all X & Y points they need to be connected like the second picture.
    My idea first was to solve it this way:
    1.Read data from TextFile.
    2.Then find the lowest point which in my case is [X:1,Y:1] and set it like a start point.
    3.Then increase the Y coordinate and find the second point , when it's found the program set it as start and so on,but after applying these ideas on paper all fail.


    Second link for picture:


    Can you give me some idea how to solve it ?
    Last edited by mitko29; Mar 27th, 2012 at 02:04 PM.

  2. #2
    Frenzied Member Lightning's Avatar
    Join Date
    Oct 2002
    Location
    Eygelshoven
    Posts
    1,611

    Re: Idea how to solve one problem

    The picture doesn't show
    VB6 & C# (WCF LINQ) mostly


    If you need help with a WPF/WCF question post in the NEW WPF & WCF forum and we will try help the best we can

    My site

    My blog, couding troubles and solutions

    Free online tools

  3. #3

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    Try now......

  4. #4

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    Anyone ?

  5. #5
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,299

    Re: Idea how to solve one problem

    First up, please don't bump your threads. If you have nothing to add then don't add anything. As for the question, one example isn't really enough to explain the problem. That would require an actual explanation. What are the actual rules, e.g. will there always be a single central point, will the number of points in the rings always be the same, etc? You can't hope to write code if you have no algorithm and you can't design an algorithm if you don't have rules.

  6. #6

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    Quote Originally Posted by jmcilhinney View Post
    First up, please don't bump your threads. If you have nothing to add then don't add anything. As for the question, one example isn't really enough to explain the problem. That would require an actual explanation. What are the actual rules, e.g. will there always be a single central point, will the number of points in the rings always be the same, etc? You can't hope to write code if you have no algorithm and you can't design an algorithm if you don't have rules.
    There are rules :
    1: Each horizontals are convex polygons
    2: Every two adjacent sides of a polygon are at an angle less than 180 degrees
    3:Polygons can invest each other, without touching or crossing.
    4:The tip is the only point which is located in the inner part of the polygon and lie on it.

  7. #7
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,299

    Re: Idea how to solve one problem

    This really isn't a VB.NET question. This is an algorithm question, because what you need to do is work out the steps you need to perform to get the job done. Those steps would be the same whether you were writing a program in VB, C#, Java, C++ or any other language or even not writing a program at all but solving the problem with pen and paper. Like I said, you can't even think about code unless you know what steps that code has to implement. So, here's my algorithm, give or take:

    1. Select the point with the greatest Y value as P1.
    2. For each remaining point P2, calculate the angle made by the line between P2 and P1 with the horizontal.
    3. Choose the point that creates the smallest angle as P2.
    4. For each remaining point P3, calculate the angle made by the line between P3 and P2 with the line between P2 and P1.
    5. Choose the point that creates the smallest angle as P3.
    6. P3 becomes P2 and P2 becomes P1.
    7. Go back to step 2 and continue until you arrive back at the original point.
    8. Go back to step 1 and continue until there are no points remaining.

    So, it's really just recursion with some trigonometry. If you don't know how to implement recursion, it's time to learn. For the trig, look to the Math class.

  8. #8

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    Quote Originally Posted by jmcilhinney View Post
    This really isn't a VB.NET question. This is an algorithm question, because what you need to do is work out the steps you need to perform to get the job done. Those steps would be the same whether you were writing a program in VB, C#, Java, C++ or any other language or even not writing a program at all but solving the problem with pen and paper. Like I said, you can't even think about code unless you know what steps that code has to implement. So, here's my algorithm, give or take:

    1. Select the point with the greatest Y value as P1.
    2. For each remaining point P2, calculate the angle made by the line between P2 and P1 with the horizontal.
    3. Choose the point that creates the smallest angle as P2.
    4. For each remaining point P3, calculate the angle made by the line between P3 and P2 with the line between P2 and P1.
    5. Choose the point that creates the smallest angle as P3.
    6. P3 becomes P2 and P2 becomes P1.
    7. Go back to step 2 and continue until you arrive back at the original point.
    8. Go back to step 1 and continue until there are no points remaining.

    So, it's really just recursion with some trigonometry. If you don't know how to implement recursion, it's time to learn. For the trig, look to the Math class.
    Well I through to do it this way:
    1.Find the point with smallest X & Y coordinates.
    2.Start increasing Y axes(X is still the same) until you reach the second point when you reach it draw line,between P1 and P2 and make P2 to be the next start point.
    3.If there aren't any point left in Y axis start changing X axis and when you reach some point ,draw a line and make it as start point.
    But this way I found that I will have problem when I need to find the center point !
    I was sure that this can be done with recursion , but I also wanted to try another approach.
    Thx for you help

  9. #9
    Smooth Moperator techgnome's Avatar
    Join Date
    May 2002
    Posts
    34,531

    Re: Idea how to solve one problem

    "Start increasing Y axes(X is still the same)" -- that doesn't work... the assumption is that P1.X and P2.X are the same... which they may not be. In fact, none of your dots are on the same axis (X or Y) as any other dot... they're all shifted one way or another.

    -tg
    * I don't respond to private (PM) requests for help. It's not conducive to the general learning of others.*
    * I also don't respond to friend requests. Save a few bits and don't bother. I'll just end up rejecting anyways.*
    * How to get EFFECTIVE help: The Hitchhiker's Guide to Getting Help at VBF - Removing eels from your hovercraft *
    * How to Use Parameters * Create Disconnected ADO Recordset Clones * Set your VB6 ActiveX Compatibility * Get rid of those pesky VB Line Numbers * I swear I saved my data, where'd it run off to??? *

  10. #10

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    How am I suppose to calculate a angle between two points , did you mean distance ?

    Because the only way I can figure out for calculation is about distance:

    Z^2 = x^2+y^2;
    where z - is the beginning of the coordinate system t.O[0,0]

  11. #11
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,299

    Re: Idea how to solve one problem

    I didn't say the angle between two points. I do wish people would actually read the words of my post. I said the angle between two lines. When you are using the first two points. For the first and second points of a polygon, one line is between the two points and the other is the implicit horizontal. It's a simple tangent calculation to get that angle. For subsequent caculations you will have three points, so you have two explicit lines so you can calculate the angle betwen them. That would be two tangent calculations and a subtraction.

  12. #12

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    Well , what can I say sorry for misunderstanding

    I already started writing the code , but I have one little glitch and I post it here if someone is able to help me.
    So I am trying to sort with my custom function List<Point>:
    Code:
      public class PointSort : IComparer
            {
                public enum Mode
                {
                    sinus,
                    cos
                }
    
                Mode currentMode = Mode.sinus;
    
                public PointSort(Mode mode)
                {
                    currentMode = mode;
                }
    
            
                int IComparer.Compare(object a, object b)
                {
                    Point one = (Point)a;
                    Point two = (Point)b;
                    if ((one.x - sx) / (Math.Sqrt(Math.Pow(one.x - sx, 2) + Math.Pow(one.y - sy, 2))) > (two.x - sx) / (Math.Sqrt(Math.Pow(two.x - sx, 2) + Math.Pow(two.y - sy, 2))))
                    {
                        return 1;
                    }
                    else
                    {
                        return 0;
                    }
    
                }
            }
    and then I just use this in order to sort:
    Code:
     Array.Sort(masiv, new PointSort(PointSort.Mode.sinus));
    and the error is:

    Where masiv is List<Point> and here my struct for Point:
    Code:
     public struct Point
            {
                public int x, y;
    
                public Point(int p1, int p2)
                {
                    x = p1;
                    y = p2;
                }
            }
    Last edited by mitko29; Mar 30th, 2012 at 04:06 PM.

  13. #13
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,299

    Re: Idea how to solve one problem

    You shouldn't be defining your own Point type because the .NET Framework already includes a Point type. That's the type of, for instance, the Location property of a control.

    Here's an example of where you should be providing comments in your code. Look at this line:
    Code:
    if ((one.x - sx) / (Math.Sqrt(Math.Pow(one.x - sx, 2) + Math.Pow(one.y - sy, 2))) > (two.x - sx) / (Math.Sqrt(Math.Pow(two.x - sx, 2) + Math.Pow(two.y - sy, 2))))
    If someone showed you that for the first time would you be able to tell them what it was doing? That is a place that you absolutely MUST provide a comment to explain what the code is doing and why. Do you really think that it's a good idea that we have to work out what it does when you already know and could simply tell us?

  14. #14

    Thread Starter
    Addicted Member
    Join Date
    Mar 2010
    Posts
    231

    Re: Idea how to solve one problem

    In the code you commented :
    sx,sy - are positive integers where I store the smallest point.
    one,two - as far as you can see are points and they represent each other point left in the list.

    So I am using these code in order to calculate which point have greater sinus than the other and then sort the list...

    So I changed the code a littleremoved my point struct and now I am using system.drawing.point)
    Code:
     class Program : IComparer<Point>
        {
     public int Compare(Point one, Point two)
            {
                if ((one.X - sX) / (Math.Sqrt(Math.Pow(one.X - sX, 2) + Math.Pow(one.Y - sY, 2))) > (two.X - sX) / (Math.Sqrt(Math.Pow(two.X - sX, 2) + Math.Pow(two.Y - sY, 2))))            
                {
                    return one.X.CompareTo(two.X) & one.Y.CompareTo(two.Y);             
                }
                else
                {
                    return 0;
                }
            }
    //then I just call the sorter like this
    masiv.sort(new Program());
    
    }
    but I am not sure that the above code is returning exactly what I need,because I wan't when the statement is true to return me the first point and when the statement is false to return the second point.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width