1

I have a few polygons in 3d space (given as loops of vertices and edges), but they lay on the same plane. I need to find a bridges between "holes" and "polygon":
grey - polygon
red - bridges

enter image description here


Does somebody know the algorithm to find such bridges for the polygon, if they are contained as a tree: polygon as a parent and it contains all holes as children elements?


I have found this material (4. finding mutually visible vertices): https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
but I don't know how to apply this method to the program if the coordinates are given in 3D.

Dark_Phoenix
  • 368
  • 3
  • 14
  • Can please add more information about the bridges. Why did you choose these red bridges as connection between the inner and the outer polygons. What distinguishes them form other possible bridges? – gdir Apr 08 '22 at 06:52
  • @gdir, there are arbitrary bridges, it's just a connection between a hole and the polygon. So, there are a lot of such "bridges", I am just looking for the fastest way to find a bridge for each hole. – Dark_Phoenix Apr 08 '22 at 06:59
  • Join a vertex of the polygon and a vertex of the hole. –  Apr 09 '22 at 15:53

2 Answers2

2

first see:

its similar task so it might get you some inspiration.

After some thinking you could try simple brute force:

  1. definitions

    let polygon points be stored in p[] array and hole points in h[] array.

  2. try every combination if bridge edge between p[] and h[]

    such that it does not intersect any previous edge not any of the polygons. In case of intersection use shorter edge and remove the longer ones.

  3. remove non "parallel" bridges

    above solution should lead to triangulated like polygon with holes so we need to remove all edges but one that share the same point so:

    1. sort edges by used first point (index)
    2. remove all lines that share the same first point leave the smallest one
    3. sort edges by used second point (index)
    4. remove all lines that share the same second point leave the smallest one

In code the first 2 bullets would look like this:

int i,j,k,e;
line l;
List<point> p,h; // input points
List<line>  P,H; // input polygon and holes lines
List<line>  B;   // output bridge lines

for (i=0;i<p.size;i++)
 for (j=0;j<h.size;j++)
   {
   l=line(p[i],h[j]); e=0;
   // first test if new edge l intersects P,H
   if (!e) for (k=0;k<P.size;i++) if (intersekt(l,P[k])){ e=1; break; }
   if (!e) for (k=0;k<H.size;i++) if (intersekt(l,H[k])){ e=1; break; }
   // if not test if intersect already found bridges
   if (!e) for (k=0;k<B.size;i++) if (intersekt(l,B[k]))
     {
     if (l.length()<=B[k]) B.del(k); // remove bigger edge from B
      else { e=1; break; }           // or throw away l for good
     }
   if (!e) B.add(l);
   }

Beware I have not test this just wrote the code directly in Answer editor so it might need some tweaking especially the last loop (maybe you will have to find first if l should be deleted or not and only then remove edges from B ...

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Yes, this should solution might work... but I was looking for a faster way to find just one bridge for each hole. – Dark_Phoenix Apr 08 '22 at 07:03
  • @Dark_Phoenix OK repaired ... for just single bridge you could use closest point however it will be also `O(n^2)` well might be speeded up to `O(n.log(n))` by spatial subdivision but for small number of points like this it will be slower I think ... Also 3D coordinates? are the polygons on the same plane or not ? – Spektre Apr 08 '22 at 07:07
  • points of polygons are given in 3D, but they are on the same plane – Dark_Phoenix Apr 08 '22 at 07:14
  • @Dark_Phoenix if you have good 2D solution then just use basis vectors of that plane and convert your points to 2D ... 1. find plane normal by cross product of any 2 non parallel edges 2. find 2 vectors `u,v` perpendicular to `n` and to each other (again use cross product) and make them unit (one of the vectors might be any edge) 3. find any point `p0` belonging to plane (any point of your polygon or hole) 4. convert `p` to 2D: `x = dot(p-p0,u); y = dot(p-p0,v);` 5. use your 2D algo 6. convert to 3D `p = p0 + x*u + y*v;` – Spektre Apr 08 '22 at 07:20
0

If you need to find just any bridge without any optimization, then the solution for a simple polygon with a single hole would be simple:

  • Step 1. Find a vertex v1of the hole polygon with maximal value of the y-coordinate.
  • Step 2. Find a vertex v2 of the outer polygon with minimal value of the y-coordinate, greater than the y-coordinate of the vertex v1, found previously.
  • Step 3. Connect vertices v1 and v2 by a bridge.

Of course, the maximization/minimization of the y-coordinate is not your only choice - you can choose any direction, along which you'll be able to perform the search, described above.

This solution won't work in case you have many holes, because they can conceal each other. Even more - there might be cases, where you won't be able to find a bridge between a concealed hole and the outer polygon. However, you can apply the algorithm, described above, to finding bridges between holes - in this case you'll need to analyze location of holes relative to each other. For example, you'll need to (algorithmically) find that the smallest hole on your picture is bounded from above by the biggest hole, so this algorithm will easily give you a bridge between them.

HEKTO
  • 3,876
  • 2
  • 24
  • 45