Tagged Questions
0
votes
1answer
22 views
Collinearity in n dimensions
What is the best way to check if $m$ points are collinear in $n$ dimensions?
I mean I have
$p_1=(3, 4, 5, 2),\quad p_2=(6, 3, 4, 2),\quad p_3=(5, 3, 5, 6),\quad p_4=(4, 2, 7, 4)$
or
...
0
votes
0answers
32 views
Variation of the trilateration algorithm
When trying to develop an algorithm for a program, I got with the following problem:
Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...
1
vote
0answers
78 views
Divide irregular polygon into hexagons
I'm working on an engineering project, i was asked to divide an irregular polygon into (n) hexagonals like in this image:
would like to know if there is an algorithm for distribution ?
4
votes
2answers
65 views
Accounting for changing radius of a paper roll to always unroll the same amount of paper
So I'm building a Post-Turing Machine that's running a 5-state busy beaver. It has a 300ft roll of receipt paper at each end simulating an infinite tape.
Hypothetically the tape is divided into ...
0
votes
1answer
63 views
Find coordinates of n points uniformly distributed in a rectangle
I have a rectangle R of width W and height H.
I have N points inside this rectangle.
I need to find an algorithm to position my points in the rectangle in the most uniform way possible (no overlaps, ...
5
votes
1answer
76 views
Place 12 equidistant dots on a $\pi$ / 3 curve
For a computer game (which means the origin is on the top left) I need to place 12 dots equidistantly on a circle.
The curve should also go through the 3 red dots shown below:
Here is how I am ...
0
votes
0answers
25 views
Wrap Using Delaunay triangulation in 2D
I want to create a Wrap using the mesh created by Delaunay triangulation [Ruperts Algorithms] ? Example By Pinning few Points and by moving others.Can you suggest Algorithms/Papers/Books Related to ...
0
votes
0answers
5 views
Move a source polyline to a reference polyline (completely or partially)
We have some source lines (with low precision) need to be moved reference lines (with high precision). Following pictures gives the example for normal use cases. The red one is a source line and the ...
1
vote
3answers
50 views
Are there any Heron-like formulas for convex polygons?
Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
3
votes
1answer
73 views
Placing cards in an arc (by using $x ^ 2$)
In a card game I have currently the hand at the bottom placed in an ugly linear corner, but actually would like to change that to an arc:
Unfortunately my math skills are very rusty now (at the age ...
2
votes
2answers
67 views
How to effectively distribute points on plane
I have a plane (screen) with its width and height (monitor resolution, not square). And I'd like to distribute points on that plane with the (approximately) same distance from each other.
For ...
0
votes
1answer
29 views
Identify gaps in N dimensional data set
We have an interesting problem we need to resolve here, we're using C# .NET 4.0 but the language should be irrelevant as it's a mathematical problem.
Problem: we need to identify gaps in N ...
1
vote
1answer
57 views
Can someone identify this algorithm for great-circle distance?
The below is an algorithm used by the jscoord library to calculate the distance between 2 coordinates:
...
0
votes
1answer
90 views
2D Eculidian matrix to 2D cartesian graph/plan
Can anyone help ?
I am trying to convert a 2D matrix of distances to a 2D graph.
For instance, I would like to go from this :
...
0
votes
2answers
72 views
How to recognize ellipse/ellipsoid from random points? UN-weighted average?
Suppose we are getting random points in 2D (or 3D) which tend to be on ellipse (or ellipsoid). We can't guarantee points are uniformly distributed over ellipse (ellipsoid surface).
The task is to ...
8
votes
2answers
106 views
Why does the term ${\frac{1}{n-1}} {2n-4\choose n-2}$ counts the number of possible triangulations in a polygon?
In the given picture bellow, it counts the number of different triangloations in a polygon, how do the get to this expression, why is it:
$$
{2n-4\choose n-2}
$$
and why do we multiply it by ...
3
votes
2answers
280 views
Graham scan convex hull algorithm - include all points on boundary
I have am implementing the Graham scan algorithm to find the convex hull of a set of (two-dimensional) points. (My implementation is in Haskell in case anyone wants to know.) The problem is that not ...
1
vote
2answers
113 views
point on a line segment furthest from its nearest line segment
I have two sets of line segments that should basically overlap, but not exactly, and I want to see where they don't match up well.
I've come up with this idea to flag the locations where there is a ...
3
votes
1answer
119 views
Concave polygons overlapping test
I have set of $N$ concave polygons, given as list of 2D Euclidean coordinates. How to compute:
a. if any of them are overlapping?
b. if one arbitrarily selected polygon overlaps with any of the ...
0
votes
1answer
63 views
Marching cubes - where does the isosurface cut the edge?
I am currently trying to figure out the insane marching cube algorithm (a.k.a. "3D contouring" or "Surface reconstruction"). According to Paul Bourke,
The position that it [the isosurface] cuts ...
0
votes
2answers
166 views
Is this a wrong solution to the smallest enclosing circle problem?
I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set.
I have the ...
1
vote
1answer
55 views
Is the following algorithm to check if a point is on a line correct?
I need to check if a point is inside a rectangle (which can be not parallel to the axes) but not on its perimeter. In 2 dimensions.
I'm checking if the point is inside by finding the intersection ...
1
vote
2answers
245 views
Rectangular spacing algorithm?
thank god there is a math section to this site, I'm going insane
I have a problem I know how to solve by trial and error but I'm trying to figure out the 'smart' way to do it so I can make it into a ...
3
votes
3answers
159 views
Working out an algorithm for finding out whether a point is in or outside of a 2D closed polygon
I'm having a bit of an issue with the following problem:
Write a brief (1/2 page) design specification document (including pseudo code for the algorithm itself) that describes your approach to ...
0
votes
2answers
77 views
Fastest way to compare angles
I' m looking for an efficient (in terms of lowest number of additions/multiplications) way to compare two (directed) angles $\measuredangle p_1 p_0 q$, $\measuredangle p_1 p_0 r$ in a plane.
For ...
1
vote
1answer
70 views
Geometry of N-dimensional hypercubes and their N-M surfaces.
I'm working on a computer code to mesh a N-dimensional space with N-dimensional hypercubes and do some physics in it. I am wondering if I can produce a generic code (with C++ templates, but that is ...
5
votes
3answers
277 views
Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D
I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
1
vote
1answer
86 views
Deterministic algorithm to fit rhombus to set of points
I'm looking for a deterministic algorithm to obtain the best fitting rhombus out of a set of user-drawn points. It need not necessarily be optimal (simple would be better).
Thanks.
0
votes
1answer
171 views
Algorithm for trimming b-spline
I'm stuck with developing algorithm to trim b-spline so it begins at certain point without changing it's shape. I'm using these formulas: link. I have already implemented inserting knot at given t. ...
2
votes
1answer
309 views
Shortest distance between two shapes
This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart).
And I am supposed to find the ...
0
votes
4answers
135 views
Figure out if a fourth point resides within an angle created by three other points
If I have a point that is considered the origin and two lines that extend outwards infinitely to two other points, what is the best way to determine whether or not a fourth point resides on or within ...
2
votes
1answer
70 views
Maximizing the number of points covered by a circular disk of fixed radius.
Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?
0
votes
1answer
93 views
The Nearest Points
Given a set R of N points R={(x1,y1,z1),(x2,y2,z2),.....,(xn,yn,zn)} and set S of M points S={ ((a1,b1,c1),(a2,b2,c2),...(am,bm,cm))}.
for each point pi(i=1 to N) in Set R ,find the point qj(j=1 to ...
2
votes
1answer
154 views
Covering area algorithm?
I'm looking for a 'covering rectangle with smaller rectangles' algorithm with the unique feature of being able to exclude some possible center points of rectangles. Basically, limiting the possible ...
1
vote
1answer
137 views
n lines in the plane
Given a diagram of n infinitely long straight lines in the plane, let them intersect in the points p_i, let the angles at $p_i$ be $v_i^j$, such that $360=\sum_j v_i^j$.
Given the suggestive diagram, ...
4
votes
0answers
116 views
Convex hull of balls
The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
1
vote
3answers
134 views
Finding a point above the line in $O(\log n)$
I am trying to solve the following problem. So far with no success.
Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
2
votes
2answers
932 views
Convex Quadrilateral Test
I have a four points in plane and need to test (based on point coordinates) whether they are able to form a convex quadrilateral:
Of course, the test should avoid configurations like these:
...
2
votes
1answer
123 views
Finding the intersections of straight lines
Given a set of lines intersecting the quadrant with $x, y>0$, what are the available algorithms for finding the area below all straight lines (including $y$ and $x$ axis)? In other words, methods ...
0
votes
1answer
60 views
Find a rotation where the shape has the least width possible on the x-axis
I am toying around with a shape problem and I am looking for a more clever solution than what I have been able to come up with.
Here is the problem:
I have a set of points that form an enclosed ...
0
votes
3answers
87 views
Altering the center of mass with an iterative process
We have a system of $n$ particles, and the particle $i$ has a point mass $m_i$. The center of mass is then given by:
$$X = \frac{\sum_i^nm_ix_i}{\sum_i^nm_i}$$
$$Y = ...
3
votes
2answers
251 views
Heronian triangle Generator
I'm trouble shooting my code I wrote to generate all Heronian Triangles (triangle with integer sides and integer area). I'm using the following algorithm
$$a=n(m^{2}+k^{2})$$
$$b=m(n^{2}+k^{2})$$
...
0
votes
1answer
56 views
How to find co-ordinates of a point from four points that can translate or rotate? All these points form a rigid body.
I have a rigid body that translates and/or rotates about an axis perpendicular to the screen. I have co-ordinates of four points on the rigid body. How can I get the co-ordinates of a unknown point on ...
0
votes
1answer
61 views
Positioning a widget involving intersection of line and a circle?
Here is the problem I'm trying to solve for my game.
I have this scenario:
I'm trying to solve for the position and size of the green rectangle. The circle is at 50%, 40% of the screen and its ...
2
votes
1answer
149 views
Is there a generic function to find the area of any shape?
Given the coordinates of all points making up a two-dimensional shape and the order in which they are connected, is there any generic formula that will give the area of that shape?
EDIT: The list of ...
1
vote
1answer
38 views
transposed matrix - how does this algorithm work?
I have an algorithm to fill a triangle
set Pixel if ("for".."with")
for a triangle like this
now, Im having trouble with the n = .. what does the ^T mean? It ...
3
votes
1answer
106 views
What would you call Apollonian circles that are located within polygon
Sorry, if this question is dumb, but:
When you try to fill the circle with other circles - its called Apollonian circles, and there are resources about it, and some example algorithms.
But i want to ...
3
votes
0answers
107 views
MDS and low distortion embeddings
While googling about low distortion embeddings, I feel that there are two separate communities working on the subject of low distortion embedding, without much communication with each other.
In ...
1
vote
1answer
116 views
Find the position of a beacon using lat/lng/signal strength data
Let's assume, hidden in a forest, there's a beacon. I walk in the forest and, at random intervals, ping the beacon. For each ping I get a lat/lng pair and the signal strength of the ping at that point ...
2
votes
1answer
88 views
Computing the point which is closest to many Planar surfaces
Suppose, i have been given different planes which orients to different direction (i.e. i know only the plane parameter of those planes). If i am able to find out planes (probably more than 3 planes) ...
