CODEWITHSUNDEEP
c#algorithmmergepolygons
Vahid
Vahid

Reputation: 5444

A simple algorithm to merge non-overlapping polygons in C#

I'm trying to implement a simple algorithm to merge some polygons. The polygons are not overlapping, and the algorithm I need doesn't have to be efficient at all. I'm looking for the simplest algorithm.

My problem is with polygons 10,9 and 6. As you can see, polygons 10 and 9 are NOT adjacent with 6 before they are merged. So if 9 and 5 are merged before 9 and 10, 6 won't have any chances to be merged with 10 and 9. But if I merge 10,9 first I'll be able to merge the final polygon with 10. How can I solve this?

enter image description here

Upvotes: 1

Views: 1264

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55619

How about merging shapes with edges that overlap?

  • Extract all the edges of all the shapes

  • Sort the edges

    • First by gradient,

    • Then by the y value where that edge would cross the x-axis if extended that far
      (or by x value if it's parallel to the y-axis),

    • Then by smallest y end-point of the edge (or smallest x point if it's parallel to the x-axis).

  • Iterate through the edges

    • The first two sorting criteria are just to eliminate non-overlapping edges (we can essentially consider those not matching the first two sorting criteria to be stored in a different data structure).

    • For the third criteria, do the following:

      If this edge starts before the end of the previous edge (with the same first two criteria), merge the shapes (if they haven't already been merged).

Example:

We split the horizontal and vertical edges.

Then we order the horizontal edges such that all the edges on 3-10 (3-1, 1-2, 2-11, etc.) are following each other, then those on 7-9, then those on 2-6 (keep in mind that we first sort by their y value, since, if they are extended to the x-axis, they'd have the same y value there, then we sort by the smallest x end-point).

Then we order the vertical edges such that the edges on 2-3 (2-7 and 7-3) are following each other, then 14-1, then the 5-2 edges, etc. (keep in mind that they're parallel to the y-axis, so we just take their x value first, then we sort by the smallest y end-point).

Keep in mind that edges such as 14-1 will appear twice since it's an edge of both 10 and 9, and we'll have edges 7-8, 7-14 and 14-8.

Now we iterate through the edges:

We start with 3-1. It doesn't have a previous edge, so we do nothing. 1-2 start after its previous edge (3-1), so we do nothing. Similarly for 2-11, 11-41, 41-19 and 19-10.

Then 7-8. No previous edge, so do nothing. Then we do 7-14. Since 7 < 8, we merge the corresponding shapes 10 and 6.

And so on.

Upvotes: 1

Related Questions