Path around a perimeter

Processing Project Guidance
1

Background (skip if you just want to get to the problem):

I’m still trying to implement the voronoi project, having run into some issues with my initial method.

Initially, i was incrementing the radius around a point, and when the the radius intersected with a line I would add a line which would be located at the inital point of intersections and grow with the radius size, using arc length formula, and if it met any other lines it would stop growing. Whilst this seemed like a good approach at first, there are just too many problems that I would later have to correct, to make the project work.

image
image.png1200×647 87.7 KB

as you can see from the picture, there are a few lines which never intersect, and so would have to be rectified later.

End of Background,

So instead i thought of calculating the midpoints from each point to every other point ( I know this means a lot of operations and is not really feasible as the size of the program grows). However if I calculate intersections with points already in my array first, then I wouldn’t have to deal with iterating through all the points as I would break out of the loop if an intersection is found.

So thats the theory anyway, apart from I’m stuck ordering the points by angle, around the central point.

It works fine in most cases,

image
image.png603×541 8.68 KB

however in some cases this happens.

51%20PM%20001
Screen Shot 10-30-19 at 07.51 PM 001.JPG603×541 12.3 KB

image
image.png603×541 9.96 KB

This is due to the fact that angles are calculated clockwise from x = 0 direction.

I however do not understand how to approach correcting this issue.

Parent closest(ArrayList<Parent> a){
    //next = a.get(a.size()-1);
    Parent k = a.get(0);
    Parent c = null;
    if(sorted_mpoints.size()==0){
      c = new Parent(W,H,100000);
    }
    else{
      c = sorted_mpoints.get(sorted_mpoints.size()-1);
    }
      //k = a.get(0);
    for(int i=0;i<a.size();i++){
      
      Parent b = a.get(i);
      
      Float d1 = dist(k.x,k.y,x,y);
      Float d2 = dist(b.x,b.y,x,y);
      
      float t1 = atan2(k.y-y,k.x-x);
      float t2 = atan2(b.y-y,b.x-x);
      
      if(t2<t1){
        k = b;
        }}
    
    return k;
  };
1 Like
2

I might be wrong about how angles are calculated using the atan2 function.

image
image.png1366×768 61 KB

the point in black should deffo be picked after point 2.

3

Partially fixed. Note there are still issues when the last points x coordinate is smaller than the central point x coordinate.

image
image.png603×541 5.37 KB
;

however it works in every other case.

An alternative program I made to debug the code.

Click to add more points, The points will be joined with a line according to their angle around the ellipse;

https://www.openprocessing.org/sketch/781579

final product;

image
image.png603×541 10.1 KB

1 Like
4

hi, i found some old code already posted here at forum
but give it some new show…
i not try to understand the math, just translated it into processing…

it is a math for a OUTER HULL,
not your OUTER LINE concept,
but possibly can be used,
as it fits your question too: “around a perimeter”

// https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

// Java program to find convex hull of a set of points. Refer 
// https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
// for explanation of orientation() 
import java.util.*; 

GFG myset;

class Point 
{ 
  int x, y; 
  Point(int x, int y){ 
    this.x=x; 
    this.y=y; 
  } 
} 

class GFG { 
  
  // To find orientation of ordered triplet (p, q, r). 
  // The function returns following values 
  // 0 --> p, q and r are colinear 
  // 1 --> Clockwise 
  // 2 --> Counterclockwise 
  public int orientation(Point p, Point q, Point r) 
  { 
    int val = (q.y - p.y) * (r.x - q.x) - 
        (q.x - p.x) * (r.y - q.y); 
  
    if (val == 0) return 0; // collinear 
    return (val > 0)? 1: 2; // clock or counterclock wise 
  } 
  
  // Prints convex hull of a set of n points. 
  public void convexHull(Point points[], int n) 
  { 
    // There must be at least 3 points 
    if (n < 3) return; 
  
    // Initialize Result 
    //Vector<Point> hull = new Vector<Point>(); 
  
    // Find the leftmost point 
    int l = 0; 
    for (int i = 1; i < n; i++) 
      if (points[i].x < points[l].x) 
        l = i; 
  
    // Start from leftmost point, keep moving 
    // counterclockwise until reach the start point 
    // again. This loop runs O(h) times where h is 
    // number of points in result or output. 
    int p = l, q; 
    do
    { 
      // Add current point to result 
      hull.add(points[p]); 
  
      // Search for a point 'q' such that 
      // orientation(p, x, q) is counterclockwise 
      // for all points 'x'. The idea is to keep 
      // track of last visited most counterclock- 
      // wise point in q. If any point 'i' is more 
      // counterclock-wise than q, then update q. 
      q = (p + 1) % n; 
      
      for (int i = 0; i < n; i++)  { 
      // If i is more counterclockwise than 
      // current q, then update q 
      if (orientation(points[p], points[i], points[q]) 
                        == 2) 
        q = i; 
      } 
  
      // Now q is the most counterclockwise with 
      // respect to p. Set p as q for next iteration, 
      // so that q is added to result 'hull' 
      p = q; 
  
    } while (p != l); // While we don't come to first  // point 
    
    // Print Result 
    for (Point temp : hull) 
      println("(" + temp.x + ", " + temp.y + ")"); 
  } 
  
/* Driver program to test above function */
public void make() {

    points[0]=new Point(0, 3); 
    points[1]=new Point(2, 2); 
    points[2]=new Point(1, 1); 
    points[3]=new Point(2, 1); 
    points[4]=new Point(3, 0); 
    points[5]=new Point(0, 0); 
    points[6]=new Point(3, 3); 
    points[7]=new Point(4, 4); 
}

public void hull() {
    int n = points.length; 
    convexHull(points, n); 
  } 
  
} 
  
// This code is contributed by Arnav Kr. Mandal. 
// mod processing KLL

Point[] points = new Point[8]; 
Vector<Point> hull = new Vector<Point>(); 

float zoom=100;

void setup(){
 size(500,500);
 myset = new GFG();
 myset.make();
 myset.hull();
}

void draw() {
  background(200,200,0);
//  translate(width/2,height/2);
  translate(20,20);
  // points
  noStroke();
  fill(200,0,0);
  for ( int i = 0; i<points.length; i++) circle(points[i].x*zoom,points[i].y*zoom,5);
  // result
  stroke(0,200,0);
  noFill();
  int segs = hull.size(); 
  for ( int i = 0; i<segs; i++)   circle(hull.get(i).x*zoom,hull.get(i).y*zoom,7);
  for ( int i = 0; i<segs; i++) {
    float x1 = hull.get(i).x*zoom;
    float y1 = hull.get(i).y*zoom;
    int j = i+1;
    if ( j == segs ) j = 0;
    float x2 = hull.get(j).x*zoom;
    float y2 = hull.get(j).y*zoom;    
    line(x1,y1,x2,y2);
  }

}

andrews_monoton_chain_algorithm
andrews_monoton_chain_algorithm.png1288×827 29.9 KB

1 Like
5

Great. A key concept here is that, in order for radial sorting of a point set to work, you must

  1. compute the midpoint
  2. the midpoint must be in the shape, with points that make sense to represent as a hull around the midpoint – never concave around the midpoint.

So, for example, a crescent moon of points will be represented as a jagged circle – both sides of the shape cannot be on one side of the midpoint. If that is okay, then radial sorting is appropriate and works well.

1 Like
6

Hi Kll, how does the code work, I dont understand all of this.

mainly

public int orientation(Point p, Point q, Point r) 
  { 
    int val = (q.y - p.y) * (r.x - q.x) - 
        (q.x - p.x) * (r.y - q.y); 
  
    if (val == 0) return 0; // collinear 
    return (val > 0)? 1: 2; // clock or counterclock wise 
  }

I managed to create a alternative test for concavity

image
this needs further calculations as I then need another test to identify which point to keep.

Your solution seems a lot more elegant but again I’m struggling to understand it all.

7

Also the issue with this is that I don’t know if a convex hull will accomplish what I’m trying to achieve, so far the increasing circle intersection test seems to be more accessible, but again I’m working with a limited understanding of coding.

Using a series of line intersection tests I can get pretty far, I now just have to close of the shape, this should be fairly simple compare to everything else however it does require checking each point against every other point in the array, and then checking points against all intersections and it very quickly becomes expensive. Not to mention that the radius has to be incremented very slowly for best result otherwise intersection are often out of place as can be seen on this picture.

image
image1200×659 76.9 KB

8

how i know, i just copy it and used it in processing.

tells you the principles used, i not read the details.

it just sounded fitting to your topic title / problem description,
but i might misunderstood it.

good

9

how fast is this method on say 1000 point array?

10

sorry, about 8.28 msec

11

Wow that is fast. I shall deffo look into this.

1 Like
13

well i used a array version, you a arrayList
but should not be a problem
keep digging

hull_from_array
hull_from_array1365×742 65.2 KB

14

solved, had to remove zoom.

This is seriously fast.

// https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

// Java program to find convex hull of a set of points. Refer 
// https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
// for explanation of orientation() 
int W = 1200,H = 660,total = 100000;
ArrayList<Point> points = new ArrayList<Point>(); 
Vector<Point> hull = new Vector<Point>(); 
import java.util.*; 

GFG myset;

class Point 
{ 
  int x, y; 
  Point(int x, int y){ 
    this.x=x; 
    this.y=y; 
  } 
} 

class GFG { 
  
  // To find orientation of ordered triplet (p, q, r). 
  // The function returns following values 
  // 0 --> p, q and r are colinear 
  // 1 --> Clockwise 
  // 2 --> Counterclockwise 
  public int orientation(Point p, Point q, Point r) 
  { 
    int val = (q.y - p.y) * (r.x - q.x) - 
        (q.x - p.x) * (r.y - q.y); 
  
    if (val == 0) return 0; // collinear 
    return (val > 0)? 1: 2; // clock or counterclock wise 
  }; 
  
  // Prints convex hull of a set of n points. 
  public void convexHull(ArrayList<Point> points, int n) 
  { 
    // There must be at least 3 points 
    if (n < 3) return; 
  
    // Initialize Result 
    //Vector<Point> hull = new Vector<Point>(); 
  
    // Find the leftmost point 
    int l = 0; 
    for (int i = 1; i < n; i++) 
      if (points.get(i).x < points.get(l).x) 
        l = i; 
  
    // Start from leftmost point, keep moving 
    // counterclockwise until reach the start point 
    // again. This loop runs O(h) times where h is 
    // number of points in result or output. 
    int p = l, q; 
    do
    { 
      // Add current point to result 
      hull.add(points.get(p)); 
  
      // Search for a point 'q' such that 
      // orientation(p, x, q) is counterclockwise 
      // for all points 'x'. The idea is to keep 
      // track of last visited most counterclock- 
      // wise point in q. If any point 'i' is more 
      // counterclock-wise than q, then update q. 
      q = (p + 1) % n; 
      
      for (int i = 0; i < n; i++)  { 
      // If i is more counterclockwise than 
      // current q, then update q 
      if (orientation(points.get(p), points.get(i), points.get(q)) 
                        == 2) 
        q = i; 
      } 
  
      // Now q is the most counterclockwise with 
      // respect to p. Set p as q for next iteration, 
      // so that q is added to result 'hull' 
      p = q; 
  
    } while (p != l); // While we don't come to first  // point 
    
    // Print Result 
    for (Point temp : hull) 
      println("(" + temp.x + ", " + temp.y + ")"); 
  }; 
  
/* Driver program to test above function */
public void make() {
  
  for (int i=0;i<total;i++){
    points.add(new Point(floor(random(W-50)), floor(random(H-50))));
  }
    //points[0]=new Point(0, 3); 
    //points[1]=new Point(2, 2); 
    //points[2]=new Point(1, 1); 
    //points[3]=new Point(2, 1); 
    //points[4]=new Point(3, 0); 
    //points[5]=new Point(0, 0); 
    //points[6]=new Point(3, 3); 
    //points[7]=new Point(4, 4); 
    //points[8]=new Point(0, 3); 
    //points[9]=new Point(2, 2); 
    //points[10]=new Point(1, 1); 
    //points[11]=new Point(2, 1); 
    //points[12]=new Point(3, 0); 
    //points[13]=new Point(0, 0); 
    //points[14]=new Point(3, 3); 
    //points[15]=new Point(4, 4); 
};

public void hull() {
    int n = points.size(); 
    convexHull(points, n); 
  } 
  
}; 
  
// This code is contributed by Arnav Kr. Mandal. 
// mod processing KLL



float zoom=1;

void setup(){
 size(1200,660);
 myset = new GFG();
 myset.make();
 myset.hull();
};

void draw() {
  background(255);
//  translate(width/2,height/2);
  translate(20,20);
  // points
  noStroke();
  fill(200,0,0);
  for ( int i = 0; i<points.size(); i++) circle(points.get(i).x*zoom,points.get(i).y*zoom,5);
  // result
  stroke(0,200,0);
  noFill();
  int segs = hull.size(); 
  for ( int i = 0; i<segs; i++)   circle(hull.get(i).x*zoom,hull.get(i).y*zoom,7);
  for ( int i = 0; i<segs; i++) {
    float x1 = hull.get(i).x*zoom;
    float y1 = hull.get(i).y*zoom;
    int j = i+1;
    if ( j == segs ) j = 0;
    float x2 = hull.get(j).x*zoom;
    float y2 = hull.get(j).y*zoom;    
    line(x1,y1,x2,y2);
  }

};
1 Like
15

for better visibility i used random with limited low and high range

  public void make() {
    for ( int i = 0; i < many; i++ ) points[i]=new Point((int)random(50, width-50),(int)random(50, height-50)); 
  }
16

same it seems the points seem to extend outside of the canvas edge.

17

not here, also the hull would also be outside canvas?

18

In general then I take it doing things in setup is much faster

19

could you explain that comment?

the last code i see was

setup: make array
setup: calc hull

draw: draw points and hull lines ( so it does not matter if use loop / noLoop )
20

Do you mean, it is faster doing some things only once in setup() as opposed to doing them repeatedly many times a second in draw()?

21

I was just astonished by the speed of this program to be honest, it is able to deal with a staggering amount of points in no time at all and i thought it was because the calculations were made in setup.

1 Like