All geek questions in one place

How can I simplify a complex polygon?

Recently, I was thinking about how to convert a complex polygon to a non-complex polygon. How it's done?

This is what I want to do:

Example

I ended up with JavaScript when done, but any form of solution is perfect (language, algorithm, or just English).

+6
source share
6 answers

I would use the same heuristic that I would use when drawing a polygon manually (which is probably not the most mathematically efficient way to caluclaute this polygon, but probably the easiest to understand / implement).

  • Start at point
  • Find all the intersections between my current point and the point I'm trying to get to
  • If none of them are drawn at the next point
  • If so, then draw there, and then set the next point to the next point from there
  • If you do not return to the beginning, go to 2.

Here is an example jsfiddle implementation. Note: it is not optimized.

+5
source

I believe the easiest route is to flatten the plane to detect all border crossings. It’s easy to increase the base implementation of the sweep algorithm to support the outermost border you want. Almost every textbook on computational geometry explains this well.

+3
source

You must keep a list of incident edges for each intersection.

Then, for any point, select the edge (outgoing) that has the smallest angle (counterclockwise) with the previous (incoming) edge.

+1
source

This is a late answer, but it can be done using the Javascript Clipper Library . The desired operation is Simplification (which internally uses the Union operation), and it removes the self-intersections where the edge intersects the other edges (s).

Attention! Javascript Clipper 5 cannot guarantee that in all cases the solution consists only of really simple polygons. This, as a special case, is the vertices touching the edges. Clipper 6 (the Javascript version is not ready yet) can handle them as special cases.

Simplify polygons using the Javascript Clipper main editor

You can play with Clipper using the Javascript Clipper Main Demo . Click "Polygons-Custom", and you can enter your own polygon and perform the necessary operations.

Take your example:
[[7.86, 196.24, 199.177, 47.169, 51.21, 224.102, 223.146, 7.40, 7.86]]

If you enter these points in a demo (like a theme or a clip), you get the following polygon: enter image description here

Then do the Simplify operation, which produces the following solution:

enter image description here

If you click Solution in Polygon Explorer, you will see the coordinates of the simplified polygon: [[199,177, 47,169, 47,75,141,13, 7,144, 7,86, 49,62,72,02, 51,21, 114,51,50, 73, 196.24, 197.28.89.49, 224.102, 223.146, 198.38,145.32]]

Simplifying Polygon Code Example

And finally, I put the full functional code in JSBIN , which includes the SVG drawing functions and is therefore quite long:

<html> <head> <title>Javascript Clipper Library / Simplifying Polygons</title> <script src="clipper.js"></script> <script> function draw() { var subj_polygons = [[{"X":7,"Y":86},{"X":196,"Y":24},{"X":199,"Y":177},{"X":47,"Y":169},{"X":51,"Y":21},{"X":224,"Y":102},{"X":223,"Y":146},{"X":7,"Y":140},{"X":7,"Y":86}]]; var scale = 100; subj_polygons = scaleup(subj_polygons, scale); var cpr = new ClipperLib.Clipper(); cpr.AddPolygons(subj_polygons, ClipperLib.PolyType.ptSubject); var solution_polygons = new ClipperLib.Polygons(); solution_polygons = cpr.SimplifyPolygons(subj_polygons, ClipperLib.PolyFillType.pftNonZero); //console.log(JSON.stringify(solution_polygons)); var svg = '<svg style="margin-top:10px; margin-right:10px;margin-bottom:10px;background-color:#dddddd" width="240" height="200">'; svg += '<path stroke="black" fill="yellow" stroke-width="2" d="' + polys2path(solution_polygons, scale) + '"/>'; svg += '</svg>'; document.getElementById('svgcontainer').innerHTML = svg; } // helper function to scale up polygon coordinates function scaleup(poly, scale) { var i, j; if (!scale) scale = 1; for(i = 0; i < poly.length; i++) { for(j = 0; j < poly[i].length; j++) { poly[i][j].X *= scale; poly[i][j].Y *= scale; } } return poly; } // converts polygons to SVG path string function polys2path (poly, scale) { var path = "", i, j; if (!scale) scale = 1; for(i = 0; i < poly.length; i++) { for(j = 0; j < poly[i].length; j++) { if (!j) path += "M"; else path += "L"; path += (poly[i][j].X / scale) + ", " + (poly[i][j].Y / scale); } path += "Z"; } return path; } </script> </head> <body onload="draw()"> <h2>Javascript Clipper Library / Simplifying Polygons</h2> This page shows an example of simplifying polygon and drawing it using SVG. <div id="svgcontainer"></div> </body> </html>
+1
source

It looks like you will want to look into the algorithms of a convex hull . Here is an applet of several Convex Hull algorithms. Perhaps you can change one of the algorithms to get your extreme points and go from there.

0
source

Well, it looks like I made a working solution:

http://mrpyo.github.com/Polygon/

This is ActionScript, so you don’t have to translate it into JavaScript. I can explain the algorithm used if someone is interested ...

0
source

Source: https://habr.com/ru/post/916183/

More articles:


All Articles