The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
32 views

Algorithm for 2D general sweep - Implementation? [on hold]

Please help! I have been reading and re-reading two papers: Approximate General Sweep Boundary of a 2D Curved Object and Polygonal boundary approximation for a 2D general sweep based on envelope ...
12
votes
2answers
911 views

How to calculate figure rotation efficiently?

I have a Figure represented through a matrix of bytes (bitmap-like matrix). Example Figure is shown on the Picture 1. The goal is to find the best rotation angle of some given Figure. When Figure ...
1
vote
1answer
60 views

Algorithm to “de-rasterize” a voxel image of a polyhedron

Rasterizing a polygon in this question consists of creating an array of binary pixels that "represent" the polygon. The reverse of this process is easy to approximate in linear time to the perimeter ...
0
votes
0answers
86 views

Approach for packing 2D shapes while minimizing total enclosing area

Not sure on my tags for this question, but in short .... I need to solve a problem of packing industrial parts into crates while minimizing total containing area. These parts are motors, or pumps, ...
1
vote
2answers
64 views

Adding a minimum rectangle overlap threshold

I have a function that works perfectly for detecting whether or not r1 overlaps with r2: boolean overlaps( Rectangle r1, Rectangle r2 ) { return r1.x < r2.x + r2.width && r1.x + ...
3
votes
2answers
188 views

Find points whose pairwise distances approximate a given distance matrix

Problem. I have a symmetric distance matrix with entries between zero and one, like this one: D = ( 0.0 0.4 0.0 0.5 ) ( 0.4 0.0 0.2 1.0 ) ( 0.0 0.2 0.0 0.7 ) ( 0.5 1.0 0.7 0.0 ) I would ...
2
votes
1answer
123 views

How to find out if a tile is being covered by a polygon?

Given a (intersecting) polygon, I'd like find out which tiles are being covered by the polygon. Example: Details: Tiles are square, 1 unit wide/high The grid begins in (0,0) The corners of the ...
2
votes
5answers
101 views

Selecting a point inside a non-convex polygon

There are a lot of algorithms which will tell you whether or not a given point is found inside a polygon. I'm looking to write an algorithm which, given a non-convex polygon, will return a point ...
6
votes
3answers
206 views

Maximizing number of nested triangles

There is a finite set of points on a plane (about 1500 points in the current task). I need to construct triangles on those points such as each triangle lies completely inside one larger triangle: ...
1
vote
2answers
357 views

2 closest points between 2 rectangles

On a 2D plane, I have 2 rectangles. I want to find the closest pair of points (one on each rectangle), which are closest to each other. By points I mean the corners of the rectangles. And no, they do ...
4
votes
1answer
130 views

How do I find which line connected two squares?

In the Permissive Field of View algorithm, a destination square is visible from a source square if any unobstructed line can be drawn from the source square to the destination square. The algorithm ...
4
votes
2answers
730 views

How to represent a geometric line programmatically?

I have been trying to design a library to do some simple geometric computations in an Euclidean space regardless of its dimension. While it is easy to represent points, vectors, hyperspheres and ...
10
votes
5answers
828 views

How to compare features of two curves?

I need to compare two curves f(x) and g(x). They are in the same x range (say -30 to 30). f(x) may have some sharp peaks or smooth peaks and valleys. g(x) may have the same peaks and valleys. If so I ...
3
votes
2answers
349 views

Intersection of geometric entities

I was trying to design a small C++ geometric API for learning purposes, but came across a problem when dealing with intersections of geometric entities. For example, the intersection of a line and a ...
1
vote
2answers
298 views

Drawing a biggest possible circle inside a polygon - JSXGRAPH

I manage to create a circle inside triangle with this code, but circle inside other polygons are not maximum size: var p1 = board.create("point", [0.0, 2.0]); var p2 = board.create("point", [2.0, ...
2
votes
0answers
202 views

Generate complex (non-convex) polyhedron UV mapping

I need to find an approach to the problem of generating texture maps for non-convex polyhedrons without using a design tool like Maya. Specifically, I am mapping simulation results data onto a 3D ...
1
vote
1answer
215 views

How to compute barycentric coordinates in a systematic and efficient way?

As part of a ray tracer implementation, I need to compute the barycentric coordinates in a triangle in 3D in order to decide if a ray hits the triangle or not. In theory this could be done by simply ...
2
votes
3answers
298 views

Trying to code the points on a circle [closed]

I am trying to understand this: I wrote a code for points on a circle of radius 1. Note that the first and last point intentionally coincide. do i=1,imax X(i,1) = ...
3
votes
1answer
3k views

Find the new coordinates using a starting point, a distance, and an angle

Okay, say I have a point coordinate. var coordinate = { x: 10, y: 20 }; Now I also have a distance and an angle. var distance = 20; var angle = 72; The problem I am trying to solve is, if I want ...
26
votes
9answers
7k views

How to check if 4 points form a square?

Assume I have 4 points (they are 2-dimension), which are different from each other, and I want to know whether they form a square. How to do it? (let the process be as simple as possible.)
0
votes
2answers
427 views

projective geometry: how do I turn a projection of a rectangle in 3D into a 2D view

So the problem is that I have a 3D projection of a rectangle that I want to turn into 2D. That is I have a photo of a sheet of paper laying on a table which I want to transform into a 2D view of that ...
2
votes
2answers
281 views

How to detect two moving shapes overlapped?

Given a list of circles with its coordinates (x and y) that are moving every second in different direction (South-East, South-West, North-East and North-West), and the circle will change direction if ...
-2
votes
1answer
397 views

What do ptLineDist and relativeCCW do? [closed]

I saw these methods in the Line2D Java Docs but did not understand what they do? Javadoc for ptLineDist says: Returns the distance from a point to this line. The distance measured is the ...
3
votes
3answers
1k views

Algorithm to calculate trajectories from vector field

I have a two-dimensional vector field, i.e., for each point (x, y) I have a vector (u, v), whereas u and v are functions of x and y. This vector field canonically defines a set of trajectories, i.e. ...
10
votes
1answer
207 views

How do graphics programmers deal with rendering vertices that don't change the image?

So, the title is a little awkward. I'll give some background, and then ask my question. Background: I work as a web GIS application developer, but in my spare time I've been playing with map ...
1
vote
3answers
517 views

Calculate Ellipse based on 4 points

I need to move an object based on 100 images rotating. The object needs to move in a path that is forming an ellipse when I'm rotating the image based on my gestures. I have 4 points, 2 pairs of ...
3
votes
4answers
1k views

Area calculation of irregular shapes

Is there any algo that can help splitting irregular shape into regular shapes, and eventually calculate the area of the main object by summing the areas of those regular objects?