I have written working code calculating the angle between the adjacent planes. I read subsequently from standart input: n - amount of triangles, m - amount of vertices ind[] - indices of the vertices given coord[] - coordinates of the vertices given The output is supposed to be the maximum angle between the adjacent planes in rad. Function calculate_angle() iterates over the amount of triangles so that I compare only new ones with the old ones (for z in range(k, n)) list_result = [i for i in index1 if i in index2] used for the adjacency detection: it asks, whether the indices of the first triangle coordinates == to the second. If there are at leat 2 of them - we start to calculate the normals to triangles (the angle between surfaces = to the angle between their normals) However, if the number of triangles is more than 104 it starts to work very slowly: ``` import numpy as np import math import sys import cProfile, pstats, io pr = cProfile.Profile() pr.enable() num_triangles, num_vertices = input().split() n = int(num_triangles) # amount of triangles m = int(num_vertices) # amount of vertices ind = [] coord = [] angles_list =[] for i in range(n): ind.append([int(j) for j in input().split()]) # indices of the vertices given for j in range(m): coord.append([float(k) for k in input().split()]) # coordinates of the vertices given def unit_vector(v): # Returns the unit vector of the vector. return v/ np.sqrt(v[0]*v[0]+v[1]*v[1]+v[2]*v[2]) def angle_between(v1, v2): v1_u = unit_vector(v1) v2_u = unit_vector(v2) return math.acos(max(min(np.dot(v1_u, v2_u), 1), -1)) # (np.clip(np.dot(v1_u, v2_u), -1.0, 1.0)) def calculate_angle(): for k in range(0, n): for z in range(k, n): index1 = ind[k] index2 = ind[z] trignum =0 list_result = [i for i in index1 if i in index2] if (ind[k] != ind[z])&(len(list_result) >= 2)&(trignum <= 3): trignum = trignum +

I have a 3D data set made of a certain number of points (x,y,z) that cover a certain region of space. Using the `scatteredInterpolant` object I can interpolate this data set over a grid to produce a rectangular mesh. Note that the mesh may extend to regions that are not defined by the data set; in fact, after the mesh generation I need to remove the part of the mesh that is extrapolated away from the data set (replacing its values with NaN, for example) in order to retain only the mesh generated between the data points. I came up with the following MATLAB script to solve this problem in a very naive way. Considering a single mesh point (xq,yq), I evaluate the minimum distance between this point and the data set; if this distance is greater than a certain threshold, then the corresponding interpolated value (zq) is set to NaN. ``` %% Data set (x,y,z) x = [3 3 3 4 4 4 4 4 5 5 5 5 5]'; y = [1 2 3 0 1 2 3 4 0 1 2 3 4]'; z = [.5 .505 .51 .51 .51 .51 .51 .515 .535 .528 .53 .53 .53]'; %% Interpolant F = scatteredInterpolant(x,y,z,'natural'); %% Mesh generation (xq,yq,zq) delta = 0.5; ti = 0:delta:5; si = 0:delta:4; [xq,yq] = meshgrid(ti,si); zq = F(xq,yq); %% Replacing undesired values with NaN thresh = 1; n = length(ti) * length(si); m = length(x); xqcol = reshape(xq,[n,1]); yqcol = reshape(yq,[n,1]); zqcol = reshape(zq,[n,1]); tab = [xqcol yqcol zqcol]; for i = 1:n dmin = 10^32; for k = 1:m diffx = tab(i,1) - x(k); diffy = tab(i,2) - y(k); d = sqrt(diffx^2 + diffy^2); if d = thresh tab(i,3) = NaN; end end zqwork = tab(:,3); zq2 = reshape(zqwork,[size(zq,1),size(zq,2)]); %% Plotting figure plot3(x,y,z,'.r','MarkerSize',10); % data set grid on; axis([0 5 0 4 0.46 0.54]); hold on; % mesh(xq,yq,zq); view(3); % full mesh mesh(xq,yq,zq2); view(3); % mesh with undesired points removed ``` This code gets the job done (to my utter surprise, since I am not really proficient with Matlab!). Here you can find a fu

For a school project, I will design and prototype a bicycle brake that uses a four-bar linkage to accomplish its goal. My Python 3 code does this mechanism generation, and implements methods to remove mechanisms I don't think will work well to hopefully give me a good final mechanism to construct. Overall I wrote this up quite quickly, hence its messiness. I'm hoping to dramatically clean up the code and improve efficiency. Any suggestions on where to begin? Background (This section isn't critical to review the code, but I thought would be nice to include) To create the mechanism, I need to define a set of three "precision positions" on the coupler curve, which are points the coupler point of the four-bar will pass through. Since the points I define are just approximate guesses what I think the path should be (approximate linear motion), I loop over a small range for each coordinate I define. I then also choose the driver rotation between PP1 and PP2 (\$ \beta_2 \$) and PP1 and PP3 (\$ \beta_3 \$). The \$ \alpha \$'s are solved from the given precision positions (the couplers rotation), as well as the \$ \delta \$'s (the translational movement of the coupler point). The following picture illustrates this: The following system of equations is solved to obtain a 2 dyads (shown above, cut the mechanism in half between the coupler point, the two links on each side is a dyad). The two dyads together form the 4-bar. $$\vec{W_A}(e^{i\beta_{2A}} - 1) + \vec{Z_A}(e^{i\alpha_{2A}} - 1) = \delta_2$$ $$\vec{W_A}(e^{i\beta_{3A}} - 1) + \vec{Z_A}(e^{i\alpha_{3A}} - 1) = \delta_3$$ $$\vec{W_B}(e^{i\beta_{2B}} - 1) + \vec{Z_B}(e^{i\beta_{2A}} - 1) = \delta_2$$ $$\vec{W_B}(e^{i\beta_{3B}} - 1) + \vec{Z_B}(e^{i\beta_{3A}} - 1) = \delta_3$$ gen.py: ``` import numpy as np import matplotlib.pyplot as plt import math from filter import links_to_joints, filter_length, filter_orientation, filter_configuration, filter_mechanical_advantage from plot import plot_four_bar_

I'm totally new in Python and I wrote some code. It is a simple algorithm to smooth objects. I need to find adjacent vertices in mesh and sum their coordinates and after that divide by a number of adjacent vertices. This algorithm is called Laplacian Smoothing. Could anybody point out how to make it better? ``` n = mesh.VPos.shape[0] final = [] for i in range(n): neighbors = mesh.vertices[i].getVertexNeighbors() indices = map(lambda x: x.ID, neighbors) z = len(indices) help = [] for j in indices: help.append([mesh.VPos[j]]) final += [sum(x)/z for x in zip(*help)] final = np.array(final) mesh.VPos = final ```

In a course I'm doing, I was given the task of finding the closest pair of points among the given points. The program that passed all test cases was the following: ``` import math if __name__ == '__main__': n = int(input()) P = [] for i in range(n): line = input().split() x = int(line[0]) y = int(line[1]) p = (x, y) P.append(p) print(closest(P, n)) def square(x): return x * x def square_distance(p0, p1): return square(p0[0] - p1[0]) + square(p0[1] - p1[1]) def closest(P, n): P.sort() # sort by x coordinates return math.sqrt(_closest_square_distance(P, n)) def _closest_square_distance(P, n): if n == 2: return square_distance(P[0], P[1]) if n == 3: return min(square_distance(P[0], P[1]), square_distance(P[0], P[2]), square_distance(P[1], P[2])) mid = n // 2 dl = _closest_square_distance(P[:mid], mid) dr = _closest_square_distance(P[mid:], n - mid) closest_square_distance = min(dl, dr) closest_distance_so_far = math.sqrt(closest_square_distance) mid_x = P[mid][0] strip = [] strip_length = 0 for i in range(n): p = P[i] if abs(p[0] - mid_x) < closest_distance_so_far: strip.append(p) strip_length += 1 strip.sort(key=lambda x: x[1]) # sort strip by y coordinates for i in range(strip_length): js = min(strip_length, i + 7) # sufficient to compute next 6 neighbors for j in range(i + 1, js): ds = square_distance(strip[i], strip[j]) if ds < closest_square_distance: closest_square_distance = ds return closest_square_distance ``` This code was based on the algorithm found at https://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_case . What do you think I can do better? Is there a more efficient way to implement this algorithm? (In this one, I just tried to delay the `sqrt` computation as long as possible, and avoided

I was inspired by another question to post another method of finding the two points in a plane that are closest to each other1. This one is a line-sweep algorithm. It works roughly like this: - Sort the points based on their X coordinates. - Take two left-most points. They give us our first guess at the shortest distance (call it D). - Insert those two points into a set that's sorted based on Y coordinates. This collection forms a vertical "band" of points whose X coordinates are within D units of the X coordinate of the current point. - Consider the next point to the right of those currently in the "band" as the current point. - Trim the band to remove points more than D units away in the X dimension from the current point. - Find the points in the band that are vertically within D units of the Y coordinate of the current point. - Look through the points in that rectangle (maximum of 6) to see if any is closer than D units from the current point. - If so, record the points and distance. - Repeat from step 4 for remaining points. Here's the code: ``` #include #include #include #include #include #include struct point { double x, y; // Used by the `set` to keep the points in the band // sorted by Y coordinates. bool operator min_dist(std::vector points) { std::sort(points.begin(), points.end(), [](point const &a, point const &b) { return a.x band{ *first, *last }; double d = dist(*first, *last); while (++last != points.end()) { while (last->x - first->x > d) { band.erase(*first); ++first; } auto begin = band.lower_bound({ 0, last->y - d }); auto end = band.upper_bound({ 0, last->y + d }); assert(std::distance(begin, end) points{ {1, 1}, {17, 9}, {23, 23}, {3, 3}, {100, 100}, {200, 200}, {24, 24}, {300, 300} }; auto r = min_dist(points); std::cout << "Closest

Full disclosure: I'm working on this for an online course. However, my goal is really just to get a pointer to where the issue is. The goal is to implement the closest points problem, that is, given a set of points on a 2D plane, find the shortest distance between two points. After lots of stress-testing and debugging, I am confident the algorithm is correct. However, it is not fast enough, which is the problem I want to solve. My algorithm is the implementation of what is described in that page, and includes the following optimisations: - Sort the arrays before passing them to the function; - Keep track of minimum distance so far and stop if it equals 0; - When considering the strip in the middle, only calculate the distance between a point and the next one if the distance between their x-coordinates and the distance between their y-coordinates is smaller than the minimum distance found so far; The main parts of the code are ``` double min_distance(const vector points_x, const vector points_y, double current_delta) { // Base case - sets of 3 points or fewer if (points_x.size() x_left; vector x_right; vector y_left; vector y_right; // Creates the x_left and x_right arrays for (int i = 0; i y_strip; // Creates the y_strip sorted by its y coordinate for (int i = 0; i = min_x && points_y[i].x <= max_x) { y_strip.push_back(points_y[i]); } } // Find the minimum distance in the strip double min_strip = mid_min_distance(y_strip, delta); return min(delta, min_strip); } ``` for recursively calculating the smallest distance on the left and right sides, and ``` double mid_min_distance(const vector y_strip, double delta) { // If mid_region is empty or contains just 1 point if (y_strip.size() < 2) return delta; double mid_min = minimal_distance(y_strip[0], y_strip[1]); double mid_min_distance = mid_min; // Brute force to inner points for (int i = 0; i < y_strip.size(); i++) { for (int j = i + 1; j < y_strip.size();

I am making a game for Android using Java and libGdx. I have an `ArrayList` of enemies that are updated each frame. The update method for the enemy looks like this: ``` public void update(float delta){ if (waypointIndex < waypointCount){ waypoint = path.getPoints().get(waypointIndex); distanceToWaypointX = waypoint.getX() - getCenterX(); distanceToWaypointY = waypoint.getY() - getCenterY(); directionToWaypoint = (float) Math.atan2(distanceToWaypointY, distanceToWaypointX); setRotation((float) Math.toDegrees(directionToWaypoint) - 180); translationX = (float) (Math.cos(directionToWaypoint) * getMovementSpeed() * delta); translationY = (float) (Math.sin(directionToWaypoint) * getMovementSpeed() * delta); distanceToWaypoint = (float) Math.hypot(distanceToWaypointX, distanceToWaypointY); if (distanceToWaypoint <= 5){ waypointIndex++; } distanceTraveled += Math.sqrt(Math.pow(translationX, 2) + Math.pow(translationY, 2)); translate(translationX, translationY); } } ``` This works OK, but with 100 enemies the FPS starts to dip into the low 50's. I would like to keep a consistent 60 FPS and I plan to have more than 100 enemies on the screen at a time. How can i improve this code to make it more efficient?

I have written a short Python program which does the following: loads a large data file (\$10^9+\$ rows) where each row is a point on a sphere. The code then loads a pre-determined triangular grid on the sphere, and counts the number of points in each triangle. I have optimised it as best as I could, however, I'd like to see if it can be optimised even further (at the moment it takes more than 1 hour to go through the entire file). ``` import numpy as np import math import csv import time import pandas PI = 3.141592653589793115997963468544 error = 0.000001 def GalacticToCartesian (starPolar, starCartesian): starCartesian[:, 0] = np.sin(starPolar[:, 1] + PI/2.0) * np.cos(starPolar[:, 0]) starCartesian[:, 1] = np.sin(starPolar[:, 1] + PI/2.0) * np.sin(starPolar[:, 0]) starCartesian[:, 2] = np.cos(starPolar[:, 1] + PI/2.0) for coord in np.nditer(starCartesian): if (np.abs(coord) > error): coord = 0 def RayTriangleIntersection (star, triangle): a = np.empty((len(star), 3, 3)) a[..., 0] = star a[..., 1] = (triangle[1] - triangle[0]) [None, :] a[..., 2] = (triangle[2] - triangle[0]) [None, :] b = np.tile(-triangle[0], (len(star), 1)) solution = np.linalg.solve (a, b) return np.where(np.logical_or.reduce((solution[:, 0] 1.0)), False, True) grid = 1 gridFacesFile = "triangles.dat" csv_file = csv.reader(open(gridFacesFile, 'rb'), delimiter='\t') triangles = [] for row in csv_file: triangles.append(np.array([float(elem) for elem in row]).reshape((3,3))) starCountPerTriangle = np.zeros ((len(triangles))) dataFile = "data.csv" chunkSize = 10 data = pandas.read_csv (dataFile, chunksize = chunkSize) count = 0 t0 = time.clock() for chunk in data: currentChunkSize = len(chunk) print ("Processing stars " + str(count*chunkSize + 1) + " to " + str(count*chunkSize + currentChunkSize) + "...") count += 1 starsPolar = np.asarray (chunk) [:, 1:3] starsCartesian = np.zeros ((curre

A python program made with a friend to draw n dimensional hyper-cubes in python using turtle. Any suggestions for improvement. ``` import turtle from turtle import * import time import math n = int(input("How many dimensions?: ")) length = int(input("How long is each side?: ")) angle = (math.pi/180)*float(input("Angle: ")) offsetx = int(input("offset of the x:")) offsety = int(input("offset of the y:")) vertices = [] numlist = [] t = turtle.Turtle() t.penup() t.shape('circle') t.shapesize(0.01) t.speed(0) tot = 0 r = 0 for i in range(0,2**n): temp = list(bin(i)) temp.remove("b") temp.remove("0") while len(temp) 0: x = vertices[0] for y in vertices: for i in range(0,n): if x[i] == y[i]: tot = tot+1 if tot == n-1: Vertex(x) t.pendown() Vertex(y) t.penup() tot = 0 r = r+1 print("DRAWING SIDES",int((r/(2**n))*100), "% COMPLETE") vertices.remove(x) print("HYPERCUBE DRAWN") nope = input("") ```