Блог пользователя Benq

Автор Benq, история, 5 лет назад, По-английски

Does anyone have a simple 3D Hull implementation? KACTL has this but it assumes that no four points are coplanar. (or in general, is it okay to shift each coordinate by a small value and work in doubles?)

On a related note, does anyone have a list of 3D hull problems? I know of these:

  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

This implementation seems to only assume that the first four points are not coplanar. I have not used it myself, so I do not know how it works.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Thanks! Considering that it calculates the volume of a cube correctly it might be okay (code). I'll do some more testing later.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    OK, but it is O(n^2 log n), still not enough for this monster: https://contest.yandex.com/newyear2020/contest/16507/problems/59/

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      What $$$O(n\log n)$$$ implementation would you recommend? (well, not like I would be able to do it if I had one)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      3D Hull in $$$O(n\log n)$$$ is surely a monster, because $$$O(n \log n)$$$ Voronoi Diagram can be reduced to it. Would be surprised if anyone has a robust $$$O(n \log n)$$$ 3D hull implementation :O

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

        We can ask guys that have it solved during New Year. aid ecnerwala do you have some robust $$$O(n \log n)$$$ 3D convex hull or did you somehow exploit additional structure and the fact that we needed to get only faces adjacent to origin?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +36 Проголосовать: не нравится

          No, this problem is much easier than 3D convex hull. After finding halfspace containing all the points it's essentially the same as 2D convex hull.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            After finding halfspace containing all the points

            How do you this without a 3D convex hull? Maybe it's really simple and I don't see something obvious, or maybe I'm somehow misled by this task:

            The editorial mentions some solutions, but it seems only 3D convex hull based ones can be made as fast as $$$O(n \log n)$$$?

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +13 Проголосовать: не нравится

              You need to find a point in the intersection of semispheres. It looks very similar to halfplanes intersection in 2D. There is a well known randomised $$$O(n)$$$ algorithm for finding a point inside halfplanes intersection: shuffle all the halfplanes, go through them and maintain one segment of border of intersection. When you add a new halfplane, you intersect it with the segment. If the intersection is empty, then either the whole halfplanes intersection is empty or new halfplane lies on border of intersection, so you intersect it with all the previous halfplanes to get a new segment. You can do the same with semispheres.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +35 Проголосовать: не нравится

          My solution also exploited the structure of the problem; I picked one of the points arbitrarily to be "up" and another to be "north", and then sorted by azimuth and ran something similar to 2D hull.

          I'm not sure where to find robust 3D hull code either.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        The randomized incremental 3D hull probably can be made to handle coplanar points well (page 26 of https://dccg.upc.edu/people/vera/wp-content/uploads/2014/11/GA2014-ConvexHulls3D-Roger-Hernando.pdf ). I don't have an implementation on hand, though.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Benq (previous revision, new revision, compare).