Как я мог упростить сложный многоугольник?

Недавно я думал о том, как преобразовать сложный многоугольник в не сложный многоугольник. Как это сделать?

Это то, что я хочу сделать:

Пример

Я собираюсь закончить с JavaScript, когда я закончу, но любая форма решения подойдет (язык, алгоритм или просто английский).

6 голосов | спросил user263078 20 Mayam12 2012, 10:17:41

6 ответов


0

Я бы использовал ту же эвристику, что и при рисовании многоугольника вручную (что, вероятно, не самый математически эффективный способ вычисления этого многоугольника, но, вероятно, самый простой для понимания /реализации).

  1. Начните с точки
  2. Найдите все пересечения между моей текущей точкой и точкой, к которой я пытаюсь добраться
  3. Если ничего не существует, переходите к следующей точке
  4. Если это так, то нарисуйте туда, а затем установите следующую точку на следующую точку оттуда
  5. Если вы не вернулись к началу, перейдите к пункту 2.

Вот пример реализации на jsfiddle. Примечание: он не оптимизирован.

ответил James Holmes 20 Maypm12 2012, 16:45:18
0

Я считаю, что самый простой способ - выполнить развертку плоскости , чтобы обнаружить все ребро пересечения. Нетрудно дополнить базовую реализацию алгоритма плоской развертки, чтобы сохранить самая внешняя граница, это то, что вы хотите. Почти каждый учебник по вычислительной геометрии объясняет это хорошо.

ответил Joseph O'Rourke 20 Maypm12 2012, 20:52:46
0

Вы должны вести список инцидентных ребер для каждой точки пересечения.

Затем для каждой точки выберите ребро (исходящее), которое имеет наименьший угол (против часовой стрелки) с предыдущим (входящим) ребром.

ответил MBo 20 Maypm12 2012, 15:58:04
0

Это поздний ответ, но это можно сделать с помощью библиотеки Javascript Clipper . Желаемой операцией является Упрощение (которое внутренне использует операцию Объединения), и оно удаляет самопересечения, когда ребро (я) пересекают другое ребро (я).

Внимание! Javascript Clipper 5 не может гарантировать, что во всех случаях решение состоит только из действительно простых полигонов. Это как частный случай, когда вершины соприкасаются с ребрами. Clipper 6 (версия Javascript еще не готова) также может обрабатывать такие же особые случаи.


Упрощение полигонов с помощью основной демонстрации Javascript Clipper

Вы можете играть с Clipper, используя Основную демонстрацию Javascript Clipper . Нажмите Polygons-Custom, и вы можете ввести свой собственный полигон и затем выполнить необходимые операции.

Давайте возьмем ваш пример:
[[7,86, 196,24, 199,177, 47,169, 51,21, 224,102, 223,146, 7,140, ​​7,86]]

Если вы введете эти точки в демо-версии (в качестве темы или клипа), вы получите следующий многоугольник: введите описание изображения здесь

Затем выполните операцию Simplify, которая приводит к следующему решению:

введите описание изображения здесь

Если вы щелкнете Решение в Polygon Explorer, вы увидите координаты упрощенного многоугольника: [[199,177, 47,169, 47,75,141.13, 7,140, ​​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]]


Пример кода упрощающих многоугольников

И, наконец, я поместил полный функциональный код в JSBIN , который включает в себя функции рисования SVG и поэтому довольно долго:

<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>

ответил Timo Kähkönen 8 +04002013-10-08T13:37:09+04:00312013bEurope/MoscowTue, 08 Oct 2013 13:37:09 +0400 2013, 13:37:09
0

Похоже, вам захочется изучить алгоритмы выпуклых оболочек . Вот апплет нескольких алгоритмов выпуклой оболочки. Возможно, вы сможете изменить один из алгоритмов, чтобы получить свои крайние точки и перейти оттуда.

ответил iCanHasFay 20 Mayam12 2012, 10:45:13
0

Хорошо, похоже, я сделал рабочее решение:

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

Это ActionScript, поэтому у вас не должно возникнуть проблем с переводом его на JavaScript. Я могу объяснить используемый алгоритм, если кому-то интересно ...

ответил mrpyo 22 Maypm12 2012, 17:16:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132