CSC220 Path Intersections and Synthetic Traces

From CSclasswiki
Jump to: navigation, search

Synthetic Traces

Goal

Given two paths, our goal is to:

  • determine if the two paths will intersect
  • calculate the coordinates of these intersections
  • add the intersections into the two paths
  • generate random paths along the two original paths and the new intersections

There two ways to go about finding intersections.

  • One way, the "easy way", is simpler to code and slightly easier to understand but does not take into account certain variables and is not as accurate as the "math way".
  • The "math way" is much more complicated, and requires figuring out the determinant of two matrices to figure out an intersection between two paths. However, it is much more accurate than the "easy way". The two different ways have been outlined below.

How to Determine Intersections Exist (the Easy Way)

Parse through 2 KML files, and go through every single point in each KML file. Go through all the points in file A, and for each point in file A, go through all the points in file B. This means we will be comparing every single point to every single point and seeing if they are less than 4 meters from each other. If they are, then we will take the average of those two points and call it the intersection.


EasyWayDiagram.jpg

Algorithm

  • read in two separate KML files, A and B
  • store x and y values from file A and B in four separate arrays
  • loop through all four arrays and check that each consecutive value of each array does not have a difference of more than 4 meters.
    • if consecutive values of an array does have a difference of more than 4 meters:
      • then create a value in between the two points that have a difference of more than 4 meters and insert into the array (for example, create a x value that is the average of x1 and x2, given that x2-x1 > 4m)
        • to insert into the array, split the array, append the value to the end of the first array, then merge them back together (see below)
      • also go into the corresponding array (the "other" x or y array) and insert the corresponding average value (for example, create a y value that is the average of y1 and y2, given that you know you need a midpoint between x1 and x2)
  • loop through appropriate array(s) to get x and y coordinates that represent path A
    • loop through appropriate array(s) to get x and y coordinates and represent path B
      • calculate distance between points
        • if within a certain value, calculate point in between two points, and store
        • else, continue

   <?php
   function array_insert($array,$pos,$val)
   {
   $array2 = array_splice($array,$pos);
   $array[] = $val;
   $array = array_merge($array,$array2);
 
   return $array;
   }
   ?>

How to Determine Intersections Exist (the Math Way)

Just like in the "simple" solution, no 2 points should be more than 4 meters apart. If they are, then we must calculate a midpoint between the far-away points and insert it into the KML file using the algorithm from above. This way, there is no way of "missing" any intersections because points are very far apart.

Then, given points A and B, we need to find all points lying within 4 meters of the line AB. This means we need to figure out whether any points are lying within a 4 meter radius of points A and B, and whether any points are lying within a 4 meter distance of any point on line AB.


PathDiagram.jpg

The figure on the left shows our line segment in black and the red shaded area around it is where we must search for points.

However, looking within two circles and a square for every point is too complicated. So we chose to look for potential intersection points within the circle of radius 3x/2 centered around the midpoint between points A and B, pictured in purple on the left

The only payoff is that we will be looking at more space than necessary.


Whichpoint.jpg

Finally, we need to determine if an intersection exists between two line segments.

Pretend that we are walking along the line segment AB:

  • If the line CD crosses AB, then at the end of AB, we will have to turn left to get to C and right to get to B.
    • If this condition is satisfied, we can continue with the test.
    • Otherwise CD cannot cross AB
  • To prove that an intersection exists, repeat the same process except this time walking along CD.
    • If you have to turn left to get to A and right to get to B, then we know that the two line segments cross.



Walkleftright.jpg

How to Calculate an Intersection Once We Know it Exists

Code adapted from here.

 <php
 function intersect($ax, $ay, $bx, $by, $cx, $cy, $dx, $dy) {
  // Translate the system so that point A is on the origin.
  $bx-=$ax;   $by-=$ay;
  $cx-=$ax;   $cy-=$ay;
  $dx-=$ax;   $dy-=$ay;

  $distAB = sqrt($bx * $bx + $by * $by);
            
  // Rotate the system so that point B is on the positive X axis.          
  $theCos = $bx / $distAB;            
  $theSin = $by / $distAB;            
  $newX = $cx * $theCos + $cy * $theSin;            
  $cy  = $cy * $theCos - $cx * $theSin; 
  $cx = $newX;
            
  $newX = $dx * $theCos + $dy * $theSin;
  $dy  = $dy * $theCos - $dx * $theSin; 
  $dx = $newX;
            
  // Discover the position of the intersection point along line A-B.           
  $posAB = $dx+($cx-$dx)*$dy/($dy-$cy);

  // Apply the discovered position to line A-B in the original coordinate system.
  $intersection = array();   
  $intersection[] = $ax + $posAB * $theCos;
  $intersection[] = $ay + $posAB * $theSin;
  
  return $intersection;
 }

 ?>
 



Intersection.jpg

How to Create New Paths

Several Possibilities

There are several possibilities for creating new paths. Once we determine the intersection points of two paths, we can store them somewhere. Using these intersection points, we can create new paths.

  • Create a new path by taking the start point of one path, have that lead to the intersection point, and have the intersection point lead to the end of point of another path (or the same path).
    • Pros: Easy to do - taking the first and last point of any path should not be hard, and we could write the first point, then the intersection point, and then the last point to a KML file. To trace the new path, we could read from the new KML file and trace.
    • Cons: Each path would only have 3 points, so it would either look like the person is going really fast or the path is super disjointed.
  • Create a new path by following one path until you hit the intersection point, then follow another path until you hit the end point of the second path.
    • Pros: Creates more accurate paths with more points along the path (end result is a smoother path).
    • Cons: It will be hard to determine where in the KML file to start the second path (i.e. we follow one path from the beginning and stop when we get to where the intersection should be, but how do we know where in the second KML file to start?). Not entirely sure how feasible this is. --> See diagram below.
  • Create new path by arbitrarily taking points from both paths and include the intersection.
    • Pros: Fairly easy.
    • Cons: Inaccurate...
  • Use spline or polynomial interpolation to create new paths.
    • Pros: makes aesthetically pleasing paths that don't follow the original data points exactly.
    • Cons: mathematical, complicated to do in php (we would have to download separate packages.)

Final Method

  1. There are two arrays, one with the points from path A, and one with the points from path B. There is also a variable (or something) that has the intersection point stored.
  2. Go through the array with the points from path A. Add points to new array (= new path) until we find the intersection point. Add intersection point to new array.
  3. Stop adding points from array with points from path A. Go into array with points from path B and go through it until we find the intersection point. Add all points from the array with points from path B to new array.

FakePaths.jpg

Algorithm

  • We have to generate the new path in the PHP file, and then save the coordinates to some file. We would have 2 files with the 2 new generated paths (since the PHP program can only give us 2 new paths at once). Maybe save intersection point to file?
  • Start going through array X1 and loop through until you find the intersection. While looping through X1, add the points you loop over into a new array, newPathX1, and also add corresponding points to newPathY1. When the value in X1 = x value of intersection, add the intersection point and stop looping through X1.
  • Start looping through X2 and loop through until you find the intersection (don't add any of these points to newPathX1!). Once you find the intersection, add the following points to newPathX1, and also add corresponding points to newPathY1. Stop at the end of X2.

Inserting Paths Into the Database

This form will allow you to choose two paths, calculate the intersection(s) and synthetic paths from the two paths chosen and then insert them into the intersectPoints table and the kmldata table.

pickPaths.php
processPaths.php

Visuals

The main goal of our project was not to create a visualization (it was more to create synthetic traces), but we have created a visualization here that helps to visualize how we created the new paths.
Processing Source Code
Processing Files (used with the source code)

Although visualization was not part of our project, there is some code here that will help someone who is trying to get our project to integrate with a Processing demo like the one we did above.

In the html file containing the applet:

 <param name="newPath1" value="http://maven.smith.edu/~220a-ag/kmlFile1new.csv">
 <param name="newPath2" value="http://maven.smith.edu/~220a-ag/kmlFile2new.csv">
 <param name="intersections" value="http://maven.smith.edu/~220a-ag/kmlFileInt.csv">
 <param name="fakePath1" value="http://maven.smith.edu/~220a-ag/Path1.csv">
 <param name="fakePath2" value="http://maven.smith.edu/~220a-ag/Path2.csv">

In the Processing file:

  String newPath1 = this.getParameter("newPath1");
  String newPath2 = this.getParameter("newPath2");
  String intersections = this.getParameter("intersections");
  String fakePath1 = this.getParameter("fakePath1");
  String fakePath2 = this.getParameter("fakePath2");

Then, whenever you'd like to call the "kmlFile1new.csv" file, you simply call newPath1 in the Processing file. The kmlFile1new.csv, kmlFile2.csv, kmlFileInt.csv, Path1.csv and Path2.csv files are created when the user goes to processPaths.php. processPaths.php writes data to external files, which the Processing then tries to access.

Project Timeline

By Wednesday 12/08

  • Generate/draw new paths, however way we can.
  • Come up with nice way to display them.
  • Read PHP program from Processing.
    • Writing to/reading from files: X1/X2/Y1/Y2original (original paths), X1/X2/Y1/Y2 (original paths with intersection), newPathX1/X2/Y1/Y2 (newly generated paths), intX/intY (just the intersection points)
      • kmlFile1.csv -- original path1
      • kmlFile2.csv -- original path2
      • kmlFile1new.csv -- original path1 with midpoints and intersections added in
      • kmlFile2new.csv -- original path2 with midpoints and intersections added in
      • kmlFileInt.csv -- all the intersection points
      • Path1.csv -- new path generated from original two paths
      • Path2.csv -- new path generated from original two paths

By End of Finals

  • Be able to get traces from database so we can generate lots of paths to put in another table.
  • Check that paths are unique. As long as the path pairs you choose is unique, the generated paths will be unique.

Future Tasks/Questions

  • Visualizations
    • Adding a processing applet to the form
  • How to generate paths with more than one intersection
    • One intersection --> 2 possible new paths
    • Two intersections --> 6 possible new paths
    • Three intersections --> 24 possible new paths
    • It gets complicated fast!
  • How to generate paths that do not follow the original path's directions
  • Create a "random walker" who walks do different points with varying probabilities
    • On a path can move forward, backward or stay still with probability 1/3
    • At an intersection can move forward, back, left, right or stay still with probability 1/5