Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. Qt Development
  3. General and Desktop
  4. How-to find surrounding polygon (Convex Hull)?
Forum Updated to NodeBB v4.3 + New Features

How-to find surrounding polygon (Convex Hull)?

Scheduled Pinned Locked Moved Unsolved General and Desktop
8 Posts 5 Posters 1.7k Views 2 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • KroMignonK Offline
    KroMignonK Offline
    KroMignon
    wrote on last edited by KroMignon
    #1

    Hi all,

    I wonder if Qt contains a function to find a surrounding polygon which includes a given list of 2D points?
    Qt is so a big framework, perhaps there is such a function.

    Does anyone know this?
    Or is there another algebra library which include this kind of function?

    It is an old maxim of mine that when you have excluded the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

    1 Reply Last reply
    0
    • BondrusiekB Offline
      BondrusiekB Offline
      Bondrusiek
      wrote on last edited by
      #2

      Hi,
      I found this example: https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/. Maybe this help you solve problem.

      KroMignonK 1 Reply Last reply
      0
      • BondrusiekB Bondrusiek

        Hi,
        I found this example: https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/. Maybe this help you solve problem.

        KroMignonK Offline
        KroMignonK Offline
        KroMignon
        wrote on last edited by
        #3

        @Bondrusiek Thanks for your suggestion, but this is not what I want to do. I want to find the polygon which is surrounding a given list of 2D points.

        Your example is to check if a point is inside a polygon, but I want to find this polygon!

        It is an old maxim of mine that when you have excluded the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

        JonBJ 1 Reply Last reply
        0
        • KroMignonK KroMignon

          @Bondrusiek Thanks for your suggestion, but this is not what I want to do. I want to find the polygon which is surrounding a given list of 2D points.

          Your example is to check if a point is inside a polygon, but I want to find this polygon!

          JonBJ Offline
          JonBJ Offline
          JonB
          wrote on last edited by JonB
          #4

          @KroMignon
          Does this make sense? There are many possible polygons which "surrounding a given list of 2D points". So what do you mean? One example would be a polygon which runs through every one of the points (i.e. has them as its vertices, with some algorithm so arcs do not cross each other), but won't there be many such not just one? I suppose another might "find the smallest area polygon which encloses a bunch of points"? Or smallest perimeter/arc length. Or smallest number of arcs?

          I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

          KroMignonK 1 Reply Last reply
          1
          • JonBJ JonB

            @KroMignon
            Does this make sense? There are many possible polygons which "surrounding a given list of 2D points". So what do you mean? One example would be a polygon which runs through every one of the points (i.e. has them as its vertices, with some algorithm so arcs do not cross each other), but won't there be many such not just one? I suppose another might "find the smallest area polygon which encloses a bunch of points"? Or smallest perimeter/arc length. Or smallest number of arcs?

            I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

            KroMignonK Offline
            KroMignonK Offline
            KroMignon
            wrote on last edited by
            #5

            @JonB said in How-to find surrounding polygon?:

            I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

            Perhaps I am not finding right words, english is not my first language...
            I have a list of points and I want to find the edge of a Polygon which will contains all those points. Like this:
            45826552-64a5-4967-9538-e6539a9de146-image.png

            Is this more clear?

            It is an old maxim of mine that when you have excluded the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

            KroMignonK mrjjM 2 Replies Last reply
            1
            • KroMignonK KroMignon

              @JonB said in How-to find surrounding polygon?:

              I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

              Perhaps I am not finding right words, english is not my first language...
              I have a list of points and I want to find the edge of a Polygon which will contains all those points. Like this:
              45826552-64a5-4967-9538-e6539a9de146-image.png

              Is this more clear?

              KroMignonK Offline
              KroMignonK Offline
              KroMignon
              wrote on last edited by
              #6

              @KroMignon I reply to myself, it seems that the algorithm I am look for is call "Convex Hull".

              I found an implementation here: ==> https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

              But perhaps someone could recommend me a better algorithm?

              It is an old maxim of mine that when you have excluded the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

              1 Reply Last reply
              3
              • KroMignonK KroMignon

                @JonB said in How-to find surrounding polygon?:

                I'm not a mathematician, but that's how it seems to me? It sounds a bit travelling salesman/Hamiltonian to me?!

                Perhaps I am not finding right words, english is not my first language...
                I have a list of points and I want to find the edge of a Polygon which will contains all those points. Like this:
                45826552-64a5-4967-9538-e6539a9de146-image.png

                Is this more clear?

                mrjjM Offline
                mrjjM Offline
                mrjj
                Lifetime Qt Champion
                wrote on last edited by mrjj
                #7

                @KroMignon
                hi
                the picture makes it really clear :)

                https://math.stackexchange.com/questions/1143878/find-polygon-with-smallest-perimeter-that-encompasses-all-points

                Maybe this algro
                https://en.wikipedia.org/wiki/Graham_scan

                c++ version here
                https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
                (oh you already found :)

                regarding the best algorithm.
                They all have tradeoffs and really only matter if you have huge list of points.

                1 Reply Last reply
                2
                • gbettegaG Offline
                  gbettegaG Offline
                  gbettega
                  wrote on last edited by
                  #8

                  Hi
                  http://www.qhull.org/
                  Giovanni

                  1 Reply Last reply
                  0

                  • Login

                  • Login or register to search.
                  • First post
                    Last post
                  0
                  • Categories
                  • Recent
                  • Tags
                  • Popular
                  • Users
                  • Groups
                  • Search
                  • Get Qt Extensions
                  • Unsolved