c++ - Removing sliver regions from a 2d point loop - Stack Overflow

I want to remove sliver regions from a loop of closed points in 2D. After removal of sliver nodes, I should get closed good area region so that my meshing software can mesh it.

For example, here are my points in the loop

Boundary Nodes Data:

Node_ID    U_param    V_param
298        -1.570694  1.933077
859        -1.570804  1.637394
860        -1.570801  1.331141
861        -1.570797  1.047667
862        -1.570806  0.775248
863        -1.570798  0.502410
864        -1.570798  0.217605
865        -1.570806 -0.089721
866        -1.570797 -0.383541
867        -1.570801 -0.659983
868        -1.570804 -0.931217
133        -1.570796 -1.208516
763        -1.355953 -1.208516
134        -1.141109 -1.208516
963        -1.141265 -0.968128
962        -1.141443 -0.732077
961        -1.141122 -0.491922
960        -1.141160 -0.250871
959        -1.140885  0.013409
309        -1.141109  0.276746
1527       -1.345324  0.430356
212        -1.491354  0.602793
211        -1.570592  0.855809
1079       -1.570592  1.109513
1078       -1.570592  1.375016
1077       -1.570592  1.660328
298        -1.570694  1.933077

How do I remove the sliver region efficiently?

EDIT: Sliver regions are narrow near zero area regions.

I want to remove sliver regions from a loop of closed points in 2D. After removal of sliver nodes, I should get closed good area region so that my meshing software can mesh it.

For example, here are my points in the loop

Boundary Nodes Data:

Node_ID    U_param    V_param
298        -1.570694  1.933077
859        -1.570804  1.637394
860        -1.570801  1.331141
861        -1.570797  1.047667
862        -1.570806  0.775248
863        -1.570798  0.502410
864        -1.570798  0.217605
865        -1.570806 -0.089721
866        -1.570797 -0.383541
867        -1.570801 -0.659983
868        -1.570804 -0.931217
133        -1.570796 -1.208516
763        -1.355953 -1.208516
134        -1.141109 -1.208516
963        -1.141265 -0.968128
962        -1.141443 -0.732077
961        -1.141122 -0.491922
960        -1.141160 -0.250871
959        -1.140885  0.013409
309        -1.141109  0.276746
1527       -1.345324  0.430356
212        -1.491354  0.602793
211        -1.570592  0.855809
1079       -1.570592  1.109513
1078       -1.570592  1.375016
1077       -1.570592  1.660328
298        -1.570694  1.933077

How do I remove the sliver region efficiently?

EDIT: Sliver regions are narrow near zero area regions.

• c++
• algorithm
• computational-geometry

Share Improve this question Follow edited Jan 4 at 15:56 user294664 asked Jan 2 at 2:46 user294664user294664 1271212 bronze badges 11

• Tag the programming language/library/technology that you are using – ray Commented Jan 2 at 2:48
• 1 what is the silver region? – Sayalic Commented Jan 2 at 12:02
• @Sayalic It's "sliver" region, not "silver". Basically the edges in the above image that almost overlaps with each other. – Weijun Zhou Commented Jan 2 at 12:35
• "Almost overlaps" does not really make anything clearer. Please define a "sliver"! Does it overlap. Does it not overlap? Do you just mean two lines that are less than some specified distance apart. Or something else. – ravenspoint Commented Jan 2 at 15:34
• Do you mean the points with indices from 211 to 862? – ravenspoint Commented Jan 2 at 15:36

 |  Show 6 more comments

1 Answer 1

Sorted by: Reset to default 0

Your question does not define a "sliver"

My best guess is that you mean the region circled in red:

So we need to define this formally. My suggestion:

Two points in an ordered list of points around a closed loop that are closer together than a small specified distance but are not adjacent to each other in the ordered list define the beginning and end of a "sliver".

Visualizing that:

Now, I hope, you can see the value of formally defining your terms. With this definition the algorithm is obvious.

• Arrange the points in order around the loop.
• Loop P over points
  • Loop Q over points starting from P+2
    • IF dist(P,Q) < Dmin
      • IF area enclosed by P, P+1, ... Q-1, Q, P < Amin
        • remove points from P+1 to Q