Разделяйте фигуры по мере того, как линии разделяют холст + выберите точки, чтобы рисовать фигуры из массивов

avatar
user1427468
8 августа 2021 в 17:35
206
3
2

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

  1. Есть ли способ обнаружить близлежащие точки, чтобы закрыть минимально возможную форму, будь то треугольник, прямоугольник или многоугольник (например, с помощью beginShape и endShape)?
  2. Если 1) слишком сложно, есть ли способ выбрать 3 или более случайных точек из массива?

Вот пример изображения с 4 линиями, разделяющими холст, точки пересечения которых отмечены красным. Я также сохранил верхнюю и нижнюю точки (отмеченные черным цветом) каждой случайно сгенерированной линии, а также четыре угла холста в тех же массивах для позиций x и y отдельно (px, py).

.

sample image that has lines dividing the canvas with their intersection points marked Несколько линий разделяют холст.

shapes split by multiple lines Как получить фигуры, разделенные линиями в Обработке?

Мне удалось получить все точки пересечения, но возникла проблема с соединением их в отдельные фигуры. Вот код обработки, над которым я работаю:

//Run in Processing.
//Press r to refresh.
//Top and bottom points are added to px and py when refreshed (filled in black).
//Intersection points are added to px and py when detected (filled in red).
int l = 4; //set number of lines
float[] r1 = new float[l];
float[] r2 = new float[l];
float[] px = {}; //array to save x positions of all possible points
float[] py = {}; //array to save y positions of all possible points
boolean added = false;
void setup(){
  size(800, 800);
  background(255);
  
  refresh();
}
void draw(){ 
  background(255);
  stroke(0, 150, 255, 150);
  strokeWeight(1);
  for(int i=0; i < r1.length; i++){
    for(int j=0; j < r1.length; j++){
      if(i>j){
      boolean hit = lineLine(r1[i], 0, r2[i], height, r1[j], 0, r2[j], height);
      if (hit) stroke(255, 150, 0, 150);
      else stroke(0, 150, 255, 150);
      }
    line(r1[i], 0, r2[i], height);
    }
  }
  added = true;
  print(px.length);
}
//source: http://jeffreythompson.org/collision-detection/line-line.php
boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  // calculate the distance to intersection point
  float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  // if uA and uB are between 0-1, lines are colliding
  if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
    // optionally, draw a circle where the lines meet
    float intersectionX = x1 + (uA * (x2-x1));
    float intersectionY = y1 + (uA * (y2-y1));
    fill(255,0,0);
    noStroke();
    ellipse(intersectionX,intersectionY, 20,20);
    if(added==false){
      px = append(px, intersectionX);
      py = append(py, intersectionY);
    }
    return true;
  }
  return false;
}
void refresh(){
  added = false;
  px = new float[0];
  py = new float[0];
  r1 = new float[l];
  r2 = new float[l];
  
  px = append(px, 0);
  py = append(py, 0);
  px = append(px, 0);
  py = append(py, height);
  px = append(px, width);
  py = append(py, 0);
  px = append(px, width);
  py = append(py, height);
  
  for(int i=0; i< r1.length; i++){
    r1[i] = random(800);
  }
  for(int i=0; i< r2.length; i++){
    r2[i] = random(800);
  }
  for(int i=0; i < r1.length; i++){
      stroke(0);
      line(r1[i], 0, r2[i], height);
      px = append(px, r1[i]);
      py = append(py, 0);
      px = append(px, r2[i]);
      py = append(py, height);
  }
}
void keyReleased() {
  if (key == 'r') refresh();
}
Источник
Andre Goulart
9 августа 2021 в 03:51
0

Я предлагаю вам добавить свой язык программирования в свои теги.

Andre Goulart
9 августа 2021 в 03:53
0

Я не мог понять ваш вопрос. У вас есть какая-то конкретная проблема с программированием? Это общий вопрос по программированию? Или это проблема геометрии/линейной алгебры?

user1427468
9 августа 2021 в 04:57
1

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

Andre Goulart
9 августа 2021 в 05:01
0

О, моя ошибка. Я даже не знал этого языка, поэтому processing показался мне просто случайным широким ключевым словом. :) Так что это конкретный вопрос, на который я не могу ответить. Удачи, однако. :)

Ответы (3)

avatar
George Profenza
9 августа 2021 в 17:48
2

Если вы хотите нарисовать фигуру, состоящую только из точек пересечения, вы на правильном пути с beginShape()/endShape().

В настоящее время похоже, что вы размещаете все точки в px, py: точки пересечения, а также точки, определяющие линии, используемые для вычисления пересечений в первую очередь.

Возможно, вы захотите разделить их, например, пару массивов для точек, определяющих только линии, и другую пару массивов x,y только для точек пересечения. Вам нужно будет только перебрать пересекающиеся координаты, чтобы разместить вызовы vertex(x, y) между beginShape()/endShape(). Вот модифицированная версия вашего кода, чтобы проиллюстрировать идею:

//Run in Processing.
//Press r to refresh.
//Top and bottom points are added to px and py when refreshed (filled in black).
//Intersection points are added to px and py when detected (filled in red).
int l = 4; //set number of lines
float[] r1 = new float[l];
float[] r2 = new float[l];
float[] px = {}; //array to save x positions of all possible points
float[] py = {}; //array to save y positions of all possible points
float[] ipx = {}; // array to save x for intersections only
float[] ipy = {}; // array to save y for intersections only
boolean added = false;

void setup(){
  size(800, 800);
  background(255);
  
  refresh();
}
void draw(){ 
  background(255);
  stroke(0, 150, 255, 150);
  strokeWeight(1);
  for(int i=0; i < r1.length; i++){
    for(int j=0; j < r1.length; j++){
      if(i>j){
      boolean hit = lineLine(r1[i], 0, r2[i], height, r1[j], 0, r2[j], height);
      if (hit) stroke(255, 150, 0, 150);
      else stroke(0, 150, 255, 150);
      }
    line(r1[i], 0, r2[i], height);
    }
  }
  added = true;
  
  // draw intersections
  beginShape();
  for(int i = 0 ; i < ipx.length; i++){
    vertex(ipx[i], ipy[i]);
  }
  endShape();
  
  //print(px.length);
  //println(px.length, py.length);
}
//source: http://jeffreythompson.org/collision-detection/line-line.php
boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  // calculate the distance to intersection point
  float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  // if uA and uB are between 0-1, lines are colliding
  if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
    // optionally, draw a circle where the lines meet
    float intersectionX = x1 + (uA * (x2-x1));
    float intersectionY = y1 + (uA * (y2-y1));
    fill(255,0,0);
    noStroke();
    ellipse(intersectionX,intersectionY, 20,20);
    if(added==false){
      px = append(px, intersectionX);
      py = append(py, intersectionY);
      
      // store intersections
      ipx = append(ipx, intersectionX);
      ipy = append(ipy, intersectionY);
      
    }
    return true;
  }
  return false;
}
void refresh(){
  added = false;
  px = new float[0];
  py = new float[0];
  ipx = new float[0];
  ipy = new float[0];
  r1 = new float[l];
  r2 = new float[l];
  
  px = append(px, 0);
  py = append(py, 0);
  px = append(px, 0);
  py = append(py, height);
  px = append(px, width);
  py = append(py, 0);
  px = append(px, width);
  py = append(py, height);
  
  for(int i=0; i< r1.length; i++){
    r1[i] = random(800);
  }
  for(int i=0; i< r2.length; i++){
    r2[i] = random(800);
  }
  for(int i=0; i < r1.length; i++){
      stroke(0);
      line(r1[i], 0, r2[i], height);
      px = append(px, r1[i]);
      py = append(py, 0);
      px = append(px, r2[i]);
      py = append(py, height);
  }
  
}
void keyReleased() {
  if (key == 'r') refresh();
}

Не забывайте, что это просто рисует точки в том порядке, в котором были вычислены пересечения. В хороший день вы получите что-то вроде этого:

triangle defined by intersection of lines

Не исключается возможность полигонов с неправильным порядком вершин (намотка):

ribbon defined by intersection of lines: instead of a quad, the wrong winding order generates the ribbon

и вы также можете получить выпуклые многоугольники.

Если вам нужна только внешняя "оболочка" этих точек пересечения, вам может понадобиться что-то вроде алгоритма выпуклой оболочки

Одним из вариантов, по крайней мере, для визуального разделения фигур может быть использование beginShape(TRIANGLES); с endShape(CLOSE);, которые должны перебирать точки и рисовать треугольник для каждой координатной тройки, однако учитывая случайные точки и количество пересечений, которые вы может закончиться отсутствующим треугольником или двумя (например, 6 точек = 2 треугольника, 7 точек = 2 треугольника и 1 точка без отсутствующих пар)

Единственное замечание, которое у меня есть, касается синтаксиса: с массивами можно начинать, но вы, возможно, захотите изучить ArrayList и PVector<670787>3347742 Это позволит вам использовать один динамический массив экземпляров PVector со свойствами x, y.

Обновление

В целом код можно упростить. Если мы уберем код, связанный с пересечением линий, мы можем получить что-то вроде:

int l = 4; //set number of random lines
float[] r1 = new float[l];  // random x top
float[] r2 = new float[l];  // random x bottom

void setup() {
  size(800, 800);
  strokeWeight(3);
  stroke(0, 150, 255, 150);
  
  refresh();
}

void draw() { 
  background(255);
  
  // random lines
  for (int i=0; i < r1.length; i++) {
    line(r1[i], 0, r2[i], height);
  }
  
  // borders
  line(0, 0, width, 0);
  line(width, 0, width - 1, height - 1);
  line(0, height - 1, width - 1, height - 1);
  line(0, 0, 0, height - 1);
}

void refresh() {
  r1 = new float[l];
  r2 = new float[l];

  for (int i=0; i< r1.length; i++) {
    r1[i] = random(800);
    r2[i] = random(800);
  }
}

void keyReleased() {
  if (key == 'r') refresh();
}

Если бы мы использовали базовый класс Line и использовали PVector и ArrayList, мы могли бы переписать приведенное выше как:

int numRandomLines = 4;
ArrayList<PVector> points = new ArrayList<PVector>();


void setup() {
  size(800, 800);
  stroke(0, 150, 255, 150);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  points.clear();
  //add borders
  points.add(new PVector(0, 0)); points.add(new PVector(width, 0));
  points.add(new PVector(width, 0));points.add(new PVector(width - 1, height - 1));
  points.add(new PVector(0, height - 1));points.add(new PVector(width - 1, height - 1));
  points.add(new PVector(0, 0)); points.add(new PVector(0, height - 1));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    points.add(new PVector(random(800), 0));  points.add(new PVector(random(800), height));
  }
}

void draw(){
  background(255);
  
  beginShape(LINES);
  for(PVector point : points) vertex(point.x, point.y);
  endShape();
}

void keyReleased() {
  if (key == 'r') refresh();
}

и группировка пары точек (PVector) в класс Line:

int numRandomLines = 4;
ArrayList<Line> lines = new ArrayList<Line>();

void setup() {
  size(800, 800);
  stroke(0, 150, 255, 150);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  lines.clear();
  //add borders
  lines.add(new Line(new PVector(0, 0), new PVector(width, 0)));
  lines.add(new Line(new PVector(width, 0), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, height - 1), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, 0), new PVector(0, height - 1)));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    lines.add(new Line(new PVector(random(800), 0), new PVector(random(800), height)));
  }
}

void draw(){
  background(255);
  
  for(Line line : lines) line.draw();
}

void keyReleased() {
  if (key == 'r') refresh();
}

class Line{
  
  PVector start;
  PVector end;
  
  Line(PVector start, PVector end){
    this.start = start;
    this.end = end;
  }
  
  void draw(){
    line(start.x, start.y, end.x, end.y);
  }
}

На этом этапе, чтобы получить отдельные формы, как показано на вашей диаграмме, мы могли бы схитрить и использовать библиотеку компьютерного зрения, например OpenCV. Это, конечно, излишество (поскольку мы get() PImage копию чертежа, конвертируем ее в изображение OpenCV), тогда просто используйте findContours(), чтобы получить каждую форму/контур.

Возвращаясь к исходному подходу, функция пересечения строк может быть интегрирована в класс Line:

int numRandomLines = 4;
ArrayList<Line> lines = new ArrayList<Line>();
ArrayList<PVector> intersections = new ArrayList<PVector>();

void setup() {
  size(800, 800);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  lines.clear();
  intersections.clear();
  //add borders
  lines.add(new Line(new PVector(0, 0), new PVector(width, 0)));
  lines.add(new Line(new PVector(width, 0), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, height - 1), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, 0), new PVector(0, height - 1)));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    lines.add(new Line(new PVector(random(800), 0), new PVector(random(800), height)));
  }
  // compute intersections
  int numLines = lines.size();
  // when looping only check if lineA intersects lineB but not also if lineB intersects lineA (redundant)
  for (int i = 0; i < numLines - 1; i++){
    Line lineA = lines.get(i);
    for (int j = i + 1; j < numLines; j++){
      Line lineB = lines.get(j);
      // check intersection
      PVector intersection = lineA.intersect(lineB);
      // if there is one, append the intersection point to the list
      if(intersection != null){
        intersections.add(intersection);
      }
    }
  }
}

void draw(){
  background(255);
  stroke(0, 150, 255, 150);
  // draw lines
  for(Line line : lines) line.draw();
  stroke(255, 0, 0, 150);
  // draw intersections
  for(PVector intersection : intersections) ellipse(intersection.x, intersection.y, 9, 9);
}

void keyReleased() {
  if (key == 'r') refresh();
}

class Line{
  
  PVector start;
  PVector end;
  
  Line(PVector start, PVector end){
    this.start = start;
    this.end = end;
  }
  
  void draw(){
    line(start.x, start.y, end.x, end.y);
  }
  
  //source: http://jeffreythompson.org/collision-detection/line-line.php
  //boolean lineLine(float this.start.x, float this.start.y, float this.end.x, float this.end.y, 
                   //float other.start.x, float other.start.y, float other.end.x, float other.end.y) {
  PVector intersect(Line other) {
    // calculate the distance to intersection point
    float uA = ((other.end.x-other.start.x)*(this.start.y-other.start.y) - (other.end.y-other.start.y)*(this.start.x-other.start.x)) / ((other.end.y-other.start.y)*(this.end.x-this.start.x) - (other.end.x-other.start.x)*(this.end.y-this.start.y));
    float uB = ((this.end.x-this.start.x)*(this.start.y-other.start.y) - (this.end.y-this.start.y)*(this.start.x-other.start.x)) / ((other.end.y-other.start.y)*(this.end.x-this.start.x) - (other.end.x-other.start.x)*(this.end.y-this.start.y));
    // if uA and uB are between 0-1, lines are colliding
    if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
      // optionally, draw a circle where the lines meet
      float intersectionX = this.start.x + (uA * (this.end.x-this.start.x));
      float intersectionY = this.start.y + (uA * (this.end.y-this.start.y));
      
      return new PVector(intersectionX, intersectionY);
    }
    return null;
  }
}

Следующим шагом будет более сложный алгоритм для сортировки точек на основе положения x, y (например, сверху вниз, слева направо), итерации по точкам, сравнения первой точки с остальными по расстоянию и углу и попытки работать out, если последовательные точки с минимальными изменениями расстояния и угла соединяются.

Глянув в интернете, я вижу такие алгоритмы, например:

CGAL c++ computational geometry library example of the sweep line algorithm displaying two orthogonal intersecting line cut by a third diagonal lower left to upper right line which connects it's tip to the horizontal: red and blue colour coded circles illustrate the intersection of these lines highlighting the interior points

user1427468
10 августа 2021 в 10:42
0

Благодарю вас! Это действительно полезно. Имеет смысл отделять только точки пересечения. Я попробую с разными вариантами методов begin/endShape().

George Profenza
11 августа 2021 в 01:53
0

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

avatar
Justin
9 августа 2021 в 16:21
2

Я вижу, что ваш код не является javascript, но поскольку вы не указали язык, я предполагаю, что вам просто нужен метод и вы можете преобразовать его в свой язык.

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

Пример: Там 3 строки (строка 1, 2, 3)

У меня есть точка пересечения между линиями 3 и 1, теперь я иду по линии 3 к соседней точке. Я нахожу один, и его пересечение 3 и 2. Ну, единственный способ, которым я мог бы получить треугольник, - это пересечение линий 1 и 2 где-то. Так что мы можем проверить это программно.

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

Это только контрольные треугольники

let canvas = document.getElementById("canvas");
        let ctx = canvas.getContext("2d");
        canvas.width = 400;
        canvas.height = 400;

        let lines = []; //holds each line
        let points = []; //all intersection point are pushed here [{x: num, y: num}, {x: num, y: num},...]
        let sortedPts = []; //all points sorted bu first number are pushed here in 2d array.
        let lineNum = 15;

        class Lines {
            constructor(num) {
                this.x = Math.round(Math.random() * canvas.width);
                this.x2 = Math.round(Math.random() * canvas.width);
                this.pt1 = {
                    x: this.x,
                    y: 0
                };
                this.pt2 = {
                    x: this.x2,
                    y: canvas.height
                };
                this.num = num;
                this.rads = Math.atan2(this.pt2.y - this.pt1.y, this.pt2.x - this.pt1.x);
                this.angle = this.rads * (180 / Math.PI);
            }
            draw() {
                ctx.beginPath();
                ctx.moveTo(this.pt1.x, this.pt1.y);
                ctx.lineTo(this.pt2.x, this.pt2.y);
                ctx.stroke();
            }
        }

        //creates the lines. I also use this function to prepare the 2d array by pushing an empty array for each line into sortedPts.
        function createLines() {
            for (let i = 0; i < lineNum; i++) {
                lines.push(new Lines(i + 1));
                sortedPts.push([])
            }
        }
        createLines();

        //Visually draws lines on screen
        function drawLines() {
            for (let i = 0; i < lines.length; i++) {
                lines[i].draw();
            }
        }
        drawLines();

        //intersecting formula
        function lineSegmentsIntersect(line1, line2) {
            let a_dx = line1.pt2.x - line1.pt1.x;
            let a_dy = line1.pt2.y - line1.pt1.y;
            let b_dx = line2.pt2.x - line2.pt1.x;
            let b_dy = line2.pt2.y - line2.pt1.y;
            let s =
                (-a_dy * (line1.pt1.x - line2.pt1.x) + a_dx * (line1.pt1.y - line2.pt1.y)) /
                (-b_dx * a_dy + a_dx * b_dy);
            let t =
                (+b_dx * (line1.pt1.y - line2.pt1.y) - b_dy * (line1.pt1.x - line2.pt1.x)) /
                (-b_dx * a_dy + a_dx * b_dy);
            if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
                //this is where we create our array but we also add the line number of where each point intersects. I also add the angle but have not used it throughout the rest of this...yet.
                points.push({
                    x: Math.round(line1.pt1.x + t * (line1.pt2.x - line1.pt1.x)),
                    y: Math.round(line1.pt1.y + t * (line1.pt2.y - line1.pt1.y)),
                    num: {
                        first: line1.num,
                        second: line2.num
                    },
                    angle: {
                        a1: line1.angle,
                        a2: line2.angle
                    }
                });
            }
        }

        //just checks each line against the others by passing to lineSegmentsIntersect() function
        function callIntersect() {
            for (let i = 0; i < lines.length; i++) {
                for (let j = i + 1; j < lines.length; j++) {
                    lineSegmentsIntersect(lines[i], lines[j]);
                }
            }
        }
        callIntersect();

        function drawPoints() {
            //just draws the black points for reference
            for (let i = 0; i < points.length; i++) {
                ctx.beginPath();
                ctx.arc(points[i].x, points[i].y, 2, 0, Math.PI * 2);
                ctx.fill();
            }
        }
        drawPoints();

        function createSortedArray() {
            //Now we take the points array and sort the points by the first number to make using i and j below possible
            points.sort((a, b) => a.num.first - b.num.first)
            //We push each group of points into an array inside sortedPts creating the 2d array 
            for (let i = 0; i < lineNum; i++) {
                for (let j = 0; j < points.length; j++) {
                    if (points[j].num.first == (i + 1)) {
                        sortedPts[i].push(points[j]);
                    }
                }
            }
            //now sort the 2d arrays by y value. This allows or next check to go in order from point to point per line.
            sortedPts.forEach(arr => arr.sort((a, b) => a.y - b.y));

            fillTriangles();
        }
        createSortedArray();

        /*
        The last step iterates through each point in the original points array
        and check to see if either the first or second number matches the second
        number of a point in our sortedPts array AND do the first or second number
        match the next points in the sortedPtsd array. If so then we must have a
        triangle.

        Quick breakdown. If we have 3 lines (line 1, 2, 3) and I have a points on lines
        2 & 3. I also have another point on lines 2 & 1. Then in order to have a triangle
        the last point must be on lines 1 & 3. 

        That's all this is doing.
        */
        function fillTriangles() {
            //iterate through each array inside sortedPts array
            for (let i = 0; i < sortedPts.length; i++) {
                //iterate through all points inside each array of points inside the sortedPts array
                for (let j = 0; j < sortedPts[i].length - 1; j++) {
                    //iterate over the original points and compare
                    for (let k = 0; k < points.length; k++) {
                        if (
                            (points[k].num.first == sortedPts[i][j].num.second ||
                                points[k].num.second == sortedPts[i][j].num.second) &&
                            (points[k].num.first == sortedPts[i][j + 1].num.second ||
                                points[k].num.second == sortedPts[i][j + 1].num.second)
                        ) {
                            ctx.fillStyle = "rgba(200, 100, 0, 0.1)";
                            ctx.beginPath();
                            ctx.moveTo(sortedPts[i][j].x, sortedPts[i][j].y);
                            ctx.lineTo(sortedPts[i][j + 1].x, sortedPts[i][j + 1].y);
                            ctx.lineTo(points[k].x, points[k].y);
                            ctx.closePath();
                            ctx.fill();
                        }
                    }
                }
            }
        }
<canvas id="canvas"></canvas>

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

user1427468
10 августа 2021 в 10:44
0

Благодарю вас! Это отличная идея — назначать идентификаторы линиям. Я не знаком с javascript, но могу выполнить ваши шаги. Я применю их к коду обработки!

avatar
Andre Goulart
9 августа 2021 в 04:03
1

Ваша цель мне не ясна. Вы можете соединить любой произвольный набор точек в любом произвольном порядке и назвать его фигурой. Каковы ваши критерии?

Если вы хотите найти кратчайший путь, соединяющий все точки заданного подмножества, я предлагаю найти задачу коммивояжера.