Random non-intersecting walk through triangulation #57

micycle1 · 2021-02-05T21:24:52Z

micycle1
Feb 5, 2021

I'm trying to compute a random non-intersecting walk through a triangulation.

My algorithm (which I believe works logically) is:

Start with a random edge.
Get edges connected to its A vertex via pinwheel() [1]
Randomly choose an edge connected to A: if its B vertex hasn't been seen, choose this edge for next iteration
Reverse the edge, so that the its pinwheel will operate on the an unseen vertex (instead of the one we just came from)
Loop back to [1] unless we've reached the maximum path length

So I'm expecting something like this:

However, I'm getting something like this:

It's not clear to me whether it's a problem with my logic/code or an incorrect assumption about how pinwheel or vertex or edges work in Tinfour -- hoping you could clarify where I might be going wrong. Thanks.

The Code:

IncrementalTin tin = new IncrementalTin(10);

tin.add(vertexList, null);
HashSet<Vertex> seen = new HashSet<>();

ArrayList<Vertex> pathVertices = new ArrayList<>();
int pathLength = 100; // path vertex count

IQuadEdge lastEdge = tin.getStartingEdge();

int n = 1;
while (n < pathLength) {

	List<IQuadEdge> list = new ArrayList<>();
	lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array

	// edges returned by pinwheel have A at the pinwheel and point to new vertices
	// B?

	IQuadEdge nextEdge;
	int attempts = 0;
	do {
		nextEdge = list.get((int) random(list.size())).getForward();
		attempts++;
	} while (!seen.contains(nextEdge.getB()) && attempts < 50);

	if (attempts > 50) {
		return; // path ended prematurely (no possible edges to take)
	}
	lastEdge = nextEdge.getReverse(); // A and B flip around, so A is at a unique point, ready for pinwheel next
										// iter
	pathVertices.add(lastEdge.getB()); // add the point we just came from
	seen.add(lastEdge.getB());
	n++;
}

Answered by gwlucastrig

Feb 6, 2021

Okay, I made some progress. The main problem was in the way your code used getForward() in the do-while loop. A lesser problem was in your post loop test where you checked for attempts>50 it should have been attempts == 50. I also had to add some checks for "ghost" vertices (the null vertex) for cases where the pinwheel would rotate to an edge outside the tin... When I designed the pinwheel, I debated about whether it should do that, but decided that I needed to capability for other purposes.

Here's my code:

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.AffineTransform;
import java.awt.geom.Line2D;
imp…

View full answer

gwlucastrig · 2021-02-06T00:48:07Z

gwlucastrig
Feb 6, 2021
Maintainer

I'll look at this tomorrow. In the mean time, perhaps it would be useful to keep track of where your path has been using a Java Bitset and and the edge indices.

…

On Fri, Feb 5, 2021, 4:25 PM Michael Carleton ***@***.***> wrote: I'm trying to compute a random non-intersecting walk through a triangulation. My algorithm (which I believe works logically) is: - Start with a random edge. - Get edges connected to its A vertex via pinwheel() [1] - Randomly choose an edge connected to A: if its B vertex hasn't been seen, choose this edge for next iteration - Reverse the edge, so that the its pinwheel will operate on the an unseen vertex (instead of the one we just came from) - Loop back to [1] unless we've reached the maximum path length So I'm expecting something like this: [image: image] <https://user-images.githubusercontent.com/9304234/107088322-b4ec5380-67f4-11eb-95d5-f254c99acb7c.png> However, I'm getting something like this: [image: image] <https://user-images.githubusercontent.com/9304234/107089769-17465380-67f7-11eb-8bf2-ccc680369c3a.png> It's not clear to me whether it's a problem with my logic/code or an incorrect assumption about how pinwheel or vertex or edges work in Tinfour -- hoping you could clarify where I might be going wrong. Thanks. The Code: IncrementalTin tin = new IncrementalTin(10); tin.add(vertexList, null); HashSet<Vertex> seen = new HashSet<>(); ArrayList<Vertex> pathVertices = new ArrayList<>(); int pathLength = 100; // path vertex count IQuadEdge lastEdge = tin.getStartingEdge(); int n = 1; while (n < pathLength) { List<IQuadEdge> list = new ArrayList<>(); lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array // edges returned by pinwheel have A at the pinwheel and point to new vertices // B? IQuadEdge nextEdge; int attempts = 0; do { nextEdge = list.get((int) random(list.size())).getForward(); attempts++; } while (!seen.contains(nextEdge.getB()) && attempts < 50); if (attempts > 50) { return; // path ended prematurely (no possible edges to take) } lastEdge = nextEdge.getReverse(); // A and B flip around, so A is at a unique point, ready for pinwheel next // iter pathVertices.add(lastEdge.getB()); // add the point we just came from seen.add(lastEdge.getB()); n++; } — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#57>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEWJDYMM7VGXYIRGL6GRQALS5RO3HANCNFSM4XFOSNVQ> .

0 replies

gwlucastrig · 2021-02-06T00:51:30Z

gwlucastrig
Feb 6, 2021
Maintainer

I take it that the restriction is never pass through a vertex more than once?

…

On Fri, Feb 5, 2021, 7:47 PM Gary Lucas ***@***.***> wrote: I'll look at this tomorrow. In the mean time, perhaps it would be useful to keep track of where your path has been using a Java Bitset and and the edge indices. On Fri, Feb 5, 2021, 4:25 PM Michael Carleton ***@***.***> wrote: > I'm trying to compute a random non-intersecting walk through a > triangulation. > > My algorithm (which I believe works logically) is: > > - Start with a random edge. > - Get edges connected to its A vertex via pinwheel() [1] > - Randomly choose an edge connected to A: if its B vertex hasn't been > seen, choose this edge for next iteration > - Reverse the edge, so that the its pinwheel will operate on the an > unseen vertex (instead of the one we just came from) > - Loop back to [1] unless we've reached the maximum path length > > So I'm expecting something like this: > > [image: image] > <https://user-images.githubusercontent.com/9304234/107088322-b4ec5380-67f4-11eb-95d5-f254c99acb7c.png> > > However, I'm getting something like this: > > [image: image] > <https://user-images.githubusercontent.com/9304234/107089769-17465380-67f7-11eb-8bf2-ccc680369c3a.png> > > It's not clear to me whether it's a problem with my logic/code or an > incorrect assumption about how pinwheel or vertex or edges work in Tinfour > -- hoping you could clarify where I might be going wrong. Thanks. > > The Code: > > IncrementalTin tin = new IncrementalTin(10); > > tin.add(vertexList, null); > HashSet<Vertex> seen = new HashSet<>(); > > ArrayList<Vertex> pathVertices = new ArrayList<>(); > int pathLength = 100; // path vertex count > > IQuadEdge lastEdge = tin.getStartingEdge(); > > int n = 1; > while (n < pathLength) { > > List<IQuadEdge> list = new ArrayList<>(); > lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array > > // edges returned by pinwheel have A at the pinwheel and point to new vertices > // B? > > IQuadEdge nextEdge; > int attempts = 0; > do { > nextEdge = list.get((int) random(list.size())).getForward(); > attempts++; > } while (!seen.contains(nextEdge.getB()) && attempts < 50); > > if (attempts > 50) { > return; // path ended prematurely (no possible edges to take) > } > lastEdge = nextEdge.getReverse(); // A and B flip around, so A is at a unique point, ready for pinwheel next > // iter > pathVertices.add(lastEdge.getB()); // add the point we just came from > seen.add(lastEdge.getB()); > n++; > } > > — > You are receiving this because you are subscribed to this thread. > Reply to this email directly, view it on GitHub > <#57>, or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AEWJDYMM7VGXYIRGL6GRQALS5RO3HANCNFSM4XFOSNVQ> > . >

0 replies

gwlucastrig · 2021-02-06T10:09:22Z

gwlucastrig
Feb 6, 2021
Maintainer

I'm working on this now and having pretty much the same problem that you did.

One thing to note. Where you want to flip the edge around to get its mirror image, and your code calls getReverse()

  lastEdge = nextEdge.getReverse(); // A and B flip around, so A is at a unique point, ready for pinwheel next

It should be calling getDual().

The getReverse() call gets the reverse link of the edge. And getForward() gets the forward link. Tinfour uses the term "dual" of an edge to indicate its opposite side (so the dual of A-to-B is B-to-A).

You would use getForward() or getReverse() if you were building a triangle.

On a side topic, something that might help your drawing code... I notice some spikey line joins. These are probably due to you using the default Java basic stroke, which specifies mitered joins. When a rendering has sharp turns, I find it cleaner to use bevel joins:

       new BasicStroke(4.0f, BasicStroke.CAP_ROUND, BasicStroke.JOIN_BEVEL)

Here's my work so far. And although I haven't solved the real problem, at least it shows the join effect I'm talking about.

0 replies

gwlucastrig · 2021-02-06T10:46:13Z

gwlucastrig
Feb 6, 2021
Maintainer

Okay, I made some progress. The main problem was in the way your code used getForward() in the do-while loop. A lesser problem was in your post loop test where you checked for attempts>50 it should have been attempts == 50. I also had to add some checks for "ghost" vertices (the null vertex) for cases where the pinwheel would rotate to an edge outside the tin... When I designed the pinwheel, I debated about whether it should do that, but decided that I needed to capability for other purposes.

Here's my code:

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.AffineTransform;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import javax.imageio.ImageIO;
import org.tinfour.common.IQuadEdge;
import org.tinfour.common.Vertex;
import org.tinfour.demo.utils.TinRenderingUtility;
import org.tinfour.standard.IncrementalTin;

public class Walkabout {

  final int nVerticesInTin;
  final int pathLength;
  final Random random;
  IncrementalTin tin;

  Walkabout(int nVerticesInTin, int pathLength, int seed) {
    this.nVerticesInTin = nVerticesInTin;
    this.pathLength = pathLength;
    random = new Random(seed);
    List<Vertex> vertexList = new ArrayList<>(nVerticesInTin);
    for (int i = 0; i < nVerticesInTin; i++) {
      double x = random.nextDouble();
      double y = random.nextDouble();
      double z = x * x + y * y - (x + y) + 0.5; // arbitrary surface
      vertexList.add(new Vertex(x, y, z, i));
    }
    tin = new IncrementalTin(1.0);
    tin.add(vertexList, null);
  }

  ArrayList<Vertex> constructPath() {
    ArrayList<Vertex> pathVertices = new ArrayList<>();
    HashSet<Vertex> seen = new HashSet<>();
    IQuadEdge lastEdge = tin.getStartingEdge();

    int n = 1;
    while (n < pathLength) {

      List<IQuadEdge> list = new ArrayList<>();
      lastEdge.pinwheel().forEach(list::add); // get edges connected to A; add to array

      // edges returned by pinwheel have A at the pinwheel and point to new vertices
      // B?
      IQuadEdge nextEdge;
      int attempts = 0;
      Vertex B = null;
      do {
        int iList = random.nextInt(list.size());
        nextEdge = list.get(iList);
        B = nextEdge.getB();
        attempts++;
        // If the lastEdge was on the perimeter of the TIN,
        // then the pinwheel operation can result in some edges
        // that have null terminating vertices (essentially these
        // edges lie outside the Delaunay triangulation).
        // So we need to test for the B==null condition.
      } while ((B == null || seen.contains(B)) && attempts < 50);

      if (attempts >= 50) {
        return pathVertices; // path ended prematurely (no possible edges to take)
      }
      pathVertices.add(B); // the vertex we will traverse to
      seen.add(B);

      lastEdge = nextEdge.getDual(); // A and B flip around, so A is at a unique point, ready for pinwheel next

      n++;
    }
    return pathVertices;
  }

  private void drawTinAndPath(ArrayList<Vertex> path, File file) {
    int width = 500;
    int height = 500;
    BufferedImage bImage
      = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
    Graphics2D g2d = bImage.createGraphics();
    g2d.setRenderingHint(
      RenderingHints.KEY_ANTIALIASING,
      RenderingHints.VALUE_ANTIALIAS_ON);
    g2d.setRenderingHint(
      RenderingHints.KEY_TEXT_ANTIALIASING,
      RenderingHints.VALUE_TEXT_ANTIALIAS_ON);
    g2d.setColor(Color.white);
    g2d.fillRect(0, 0, width, height);

    Rectangle2D bounds = tin.getBounds();
    TinRenderingUtility tru = new TinRenderingUtility();
    AffineTransform tin2pix = tru.initTransform(
      500, 500,
      bounds.getMinX(), bounds.getMaxX(),
      bounds.getMinY(), bounds.getMaxY());

    // Draw the TIN
    double[] xy = new double[8];
    g2d.setColor(Color.lightGray);
    g2d.setStroke(new BasicStroke(1.0f));
    for (IQuadEdge e : tin.edges()) {
      Vertex a = e.getA();
      Vertex b = e.getB();
      xy[0] = a.getX();
      xy[1] = a.getY();
      xy[2] = b.getX();
      xy[3] = b.getY();
      tin2pix.transform(xy, 0, xy, 4, 2);
      Line2D l2d = new Line2D.Double(xy[4], xy[5], xy[6], xy[7]);
      g2d.draw(l2d);
    }

    // Draw the Path ------------------------------
    g2d.setColor(Color.red);
    g2d.setStroke(new BasicStroke(4.0f, BasicStroke.CAP_ROUND, BasicStroke.JOIN_BEVEL));
    Path2D path2d = new Path2D.Double();
    boolean moveFlag = true;
    for (Vertex v : path) {
      xy[0] = v.getX();
      xy[1] = v.getY();
      tin2pix.transform(xy, 0, xy, 2, 1);
      if (moveFlag) {
        moveFlag = false;
        path2d.moveTo(xy[2], xy[3]);
      } else {
        path2d.lineTo(xy[2], xy[3]);
      }
    }
    g2d.draw(path2d);

    try {
      ImageIO.write(bImage, "PNG", file);
    } catch (IOException ioex) {
      ioex.printStackTrace(System.out);
    }

  }

  public static void main(String[] args) {
    // TODO code application logic here
    Walkabout walkabout = new Walkabout(50, 50, 0);
    ArrayList<Vertex> path = walkabout.constructPath();
    walkabout.drawTinAndPath(path, new File("walkabout.png"));
  }

}

Incidentally, I was unfamiliar with that Java forEach syntax that you used:

lastEdge.pinwheel().forEach(list::add);

So thanks for showing me a new trick... I'm sure t will come in handy in the future.

1 reply

micycle1 Feb 6, 2021
Author

Thank you. So in the end it was a mix of misunderstanding the API (reverse()) and problems with the code (this morning I noticed I had the while condition the wrong way around!). All of this was to answer this question on SO lol, but I'll be able to use for creative coding too.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Random non-intersecting walk through triangulation #57

{{title}}

Replies: 4 comments 1 reply

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Select a reply

Random non-intersecting walk through triangulation #57

micycle1 Feb 5, 2021

Replies: 4 comments · 1 reply

gwlucastrig Feb 6, 2021 Maintainer

gwlucastrig Feb 6, 2021 Maintainer

gwlucastrig Feb 6, 2021 Maintainer

gwlucastrig Feb 6, 2021 Maintainer

micycle1 Feb 6, 2021 Author

micycle1
Feb 5, 2021

Replies: 4 comments 1 reply

gwlucastrig
Feb 6, 2021
Maintainer

gwlucastrig
Feb 6, 2021
Maintainer

gwlucastrig
Feb 6, 2021
Maintainer

gwlucastrig
Feb 6, 2021
Maintainer

micycle1 Feb 6, 2021
Author