# Tag Info

64

Assuming that your square might be rotated against whatever coordinates system you have in place, you can't rely on there being any repetition of X and Y values in your four points. What you can do is calculate the distances between each of the four points. If you find the following to be true, you have a square: There are two points, say A and C which ...

23

Pick three of the four points. Figure out if it's a right isosceles triangle by checking if one of the three vectors between points is equal to another one rotated by 90 degrees. If so, compute the fourth point by vector addition and compare it to the given fourth point. Note that this doesn't require expensive square roots, not even multiplication.

20

It's simply a matter of your two axes not visually being the same size. You can see that they go out to a radius of 1 in all 4 directions, which is 5 marks, but the distance between marks is different between the x axis and y axis. Mathematically, your result is in fact a circle, it's how you're rendering it that is the problem.

20

It looks like you can find the arbitrarily aligned minimum bounding box using the linear time Rotating calipers algorithm. Once you have the bounding box, you just need to determine the angle of rotation by calculating the slope of one of the sides.

15

I think the easiest solution is the following: First, calculate the center of the 4 points: center = (A + B + C + D)/4 Then calculate the vector A - center. Let this be v := (x,y) Let v2 be the vector v rotated by 90 degrees: v2 := (-y, x) Now the other points should be center - v, center + v2 and center - v2. The advantage of this solution is that you don'...

12

The first step of your approach is flawed - there are an infinite number of real values between 0 and 45, so it makes no sense to "loop through them". However, your algorithm can be repaired: find the convex hull of the polygon loop through the finite (!) number of angles given by the outer edges of the convex hull now apply the steps 2 to 4 using these ...

11

I think you're on the right track with your parametric equation. What you have there is the vector form of the line equation. L = R + tV Where R is [x0, y0, z0] and V is [a, b, c]. You just need to normalize your equations. You would do that by finding the value of R such that |R| is at a minimum, which occurs when R is perpendicular to V, or R.V = 0. ...

10

I'm going to define "neighboring points" as points that share an edge with area of point in Voronoi diagram. To calculate which points are "neighbors" in voronoi diagram, you use Delaunay triangulation.

9

The equations can be all rewritten into form : a*X + b*Y + c = 0 That means you can store three doubles a, b and c. This doesn't have a problem in representing an arbitrary slope. You can also calculate slope as a/b (or b/a). Two lines are equal if there exists k where a1*k = a2, b1*k=b2, c1*k = c2.

8

This is why geometry class in high school had you spending all that time drawing stuff. Assuming a regular polygon (all sides same length, all "corners" same angle), it is immediately obvious that the centers of the largest inscribed circle and the smallest circumscribed circle are identical, and are given by the vector arithmetic mean of the polygon ...

8

What about of implementing a free function taking the subjects as parameters, instead of binding it to a specific class, if you can't tell which it should belong to specifically? Would a separate "middle-man" Intersections class be better? If you're working with a programming language like c# or java, which doesn't support free functions, you probably ...

6

First, create a list of all triangles (subsets of 3 points). Then you make a pairwise comparison of each of two triangles T_i and T_j: either T_i is inside T_j, T_j is inside T_i or none of the two lies inside of the other. Interpret this as a directed, acyclic graph: the triangles are the vertices of the graph, and each relationship "T_i is inside T_j" ...

6

You're going to have to loop through all the points and calculate the distance. There is a great question on StackOverflow about how to calculate the distance: Shortest distance between a point and a line segment Some of the work can be precalculated, given that you have to do this more than once for a given line segment. You also don't need to figure out ...

6

Not solvable. I tried a number of methods until i realized it couldn't be done. Assume a shape with area 4, which should be divided in 2 parts with area 2 each: The leftmost triangle and square must be part of shape 1, but it needs another triangle. The only place that could be taken from is the square to the right, but then the remainder is split in two ...

6

As I said in my comment to Doc Browns (otherwise excellent) answer, there is a matter of choice of square->triangle division which makes it slightly harder to device an algorithm. Also, you don't have to make it serially, but can do it in parallell, as some of my suggestions show. I made several heuristic approaches at first. Voronoi: Choose N points (non-...

6

There is no "common approach", because this is not a requirement occuring so frequently that it needs a special standard. So pick a solution which suits your needs like the one you suggested: {x, y, w, h}, where w and h is allowed to be negative That is actually the first idea which came into my mind when I saw your question, so why don't you give it a ...

5

I'm sorry but some answers don't apply. For the case you measure 3 edges (let's say AB, AC and AD) to find that two have the same size (let's say AC and AD) and one is bigger (let's say AB). Then you would measure CD to see if it's the same size of AB, and you find that it is. Instead of a square, you could have the picture below, and that makes it a wrong ...

5

Quadtree is a brother of Binary tree, for 2D. Here is a good explanation with live example in Javascript: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/

5

SOHCAHTOA Sine = Opposite/Hypotenuse Cosine = Adjacent/Hypotenuse Tangent = Opposite/Adjacent In your example: Sine(72) = Y/20 -> Y = Sine(72) * 20 Cosine(72) = X/20 -> X = Cosine(72) *20 The problem is you have to be careful with what quadrant you are in. This works perfectly in the upper right quadrant, but not so nice in the other three ...

5

When you do ListPlot[] in Mathematica, it uses an "Auto" aspect ratio, which is something like the Golden Mean. You can see that in your plot (the ticks are closer together on the Y axis than on the X axis). To get what you are looking for, use the option AspectRatio->1, e.g.: ListPlot[Points, AspectRatio -> 1] I'd post a picture for you, but stack ...

5

At a minimum, all you need to compare lines for equality is the parametric equation you already have. Given lines L,M expressed as Dancrumb suggests: L = X + tV M = Y + tW then L == M if V and W are parallel (or equal if they're normalized to unit length and some "positive" direction), and Y=X+tV for some t. To get memberwise equality, normalizing the ...

5

This is the standard problem known as "Multidimensional Scaling". There are lots of varieties, so I recommend reading the wikipedia page on the subject (it's not so long), but in your case, it looks like plain PCA (Principal component analysis) is the way to go. In particular, a (squared) distance matrix D is closely related to B, the product of the ...

5

A triangulation of your point set gives you for each point a list of "adjacent" points, the neighbours to which a point is connected. Once you have calculated the triangulation, you can determine the outer edges by applying an algorithm similar to the classic gift-wrapping algorithm for convex hulls. You start with, for example, the "rightmost" point (which ...

4

Since you are working on a geometric API, I guess you are not only interested in intersection of lines and spheres, but have also more exciting projects. A natural approach to solve your problem of representing values for intersection would be to define a type for geometric figures so that you can represent: Points Lines Spheres Intersections that you ...

4

Obviously, you are dealing with a set of differential equations: dx/dt = u(x, y) dy/dt = v(x, y) There a lot of algorithms, which can actually integrate such equations, but it will depend on the u and v (are they linear or not etc.). Can you provide some more info on this? In relation to your requirement, is it correctly understood that you want to ...

4

If you have a modest number of them, and since they are circles, you can compare the distance between the mid-points of each circle to all the others. If the distance is less than the sum of the two radii, they overlap. This approach isnt terribly efficient, but should suffice for numbers in the dozens without any noticable performance impact. And there's ...

4

This is a common and often difficult problem in analytical chemistry, physics, spectroscopy, etc. The approaches used can range from simple RMSD comparison to very sophisticated methods. If the task isn't easy to do by visual inspection (humans are exquisitely developed for feature recognition), then it will likely be hard to do computationally. One ...

4

If you are okay with an approximated solution (not necessarily the best one possible), you could try genetic approach. Find a so-so solution as a starting point - using some simple algorithm such as the one suggested by @Carra - then make, say, a 1000 copies of this initial solution and keep on mutating them randomly. Switching points, trying to add more ...

4

You could argue that a curve is simple if there are no two line segments between points such that the lines intersect, meaning you could check if a curve is simple by verifying the absence of this condition. The algorithm would look something like: for each p1, p2 in pointlist for each p3, p4 in pointlist if line_segment(p1, p2) intersects ...

4

This is not a general solution, since there are several situations were it will not provide the position of the blue circle with shortest distance to the white dot. For example, if you have 100 red balls grouped together and the white dot is far away from this group of red balls then none of the red balls will have any influence in the position of the blue ...

Only top voted, non community-wiki answers of a minimum length are eligible