Skip to main content

Questions tagged [geometry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
17 views

Feedback on API design of a HalfEdge Data structure

Background Sometimes also referred to as doubly connected edge list, the HalfEdge data structure allows programmers to efficiently and easily modify topological and geometric properties of a mesh. ...
Makogan's user avatar
  • 261
-3 votes
1 answer
239 views

Why sort the points acc to y coordinates in closest point divide and conquer method?

The divide and conquer strategy for closest point problem sorts the points according to x coordinates so that the median could be found. But what does sorting the strip (strip array contains all the ...
user12208242's user avatar
-5 votes
3 answers
193 views

Algorithm to find if a square is removable from a group of squares without disconnection

I have a group of squares on a 2d grid, here's an example I need an algorithm to find out whether we are able to remove a square while keeping the entire group connected. Below is an image where I ...
mazore's user avatar
  • 115
-2 votes
1 answer
2k views

Algorithm to split a grid of squares into equally sized sections

I have a grid of squares, let's say 12x12. I want to split this grid into equal sections of 8 squares, which is 18 total sections. There is no requirement for sections being convex or compact, and ...
mazore's user avatar
  • 115
1 vote
0 answers
188 views

Rectangle packing / Bin packing with multiple frames

I have multiple rectangular frames, with different fixed heights. The width should be minimized and there is a maximum width. Then there are many different smaller rectangles. These should be packed ...
Wombosvideo's user avatar
-3 votes
2 answers
1k views

How can I calculate the radius of an arc given by a series of points

Given a series of points, I need to assert that the plotted points form an arc (with a certain level of confidence), and I need to approximate the radius of the arc. For example, the following points ...
Yanick Rochon's user avatar
0 votes
1 answer
457 views

What is a good Object-Oriented design for geometry objects when building libraries dealing with geometry operations?

I am trying to design an object-oriented library to handle geometric calculations. However, I am trying to exaggerate on being "tightly" object-oriented and applying relevant "best practices". I know ...
Vector Zita's user avatar
  • 2,472
1 vote
4 answers
901 views

Algorithm to simplify 2D convex hull at the cost of extra area

Are there any algorithms related to the following problem that could be usefull for solving it? I have a convex hull built on some point set. I would like to simplify it (reduce number of points) by ...
Anton Petrov's user avatar
5 votes
4 answers
277 views

Which class should have the `intersects` method?

I have a Circle class and a LineSegment class, and I want to implement a method that returns two points (or one, or none) for the intersections. How do I know which class to put this method in? Would ...
MCMastery's user avatar
  • 163
2 votes
1 answer
76 views

Should a LineSegment class disallow approximately equal endpoints in its constructor?

Imagine a LineSegment class that represents a line segment using two arbitrary endpoints. Should the constructor throw if it is passed two approximately equal endpoints? Obviously this would require ...
davidvandebunte's user avatar
1 vote
3 answers
318 views

How do you usually implement right triangles in programming

When I want to implement axis aligned 2d rectangles I always go with {x, y, w, h}, because that is the natural approach to it. With 3d axis aligned rectangles you need {x, y, z, w, h, d(depth)}. For a ...
hgiesel's user avatar
  • 811
12 votes
5 answers
820 views

Find nearest best fit for circle

Below is an example image, if I have a point of the white dot in the middle and I want to find the nearest possible location for the blue circle (which is obviously at the location where I placed it) ...
Botanic's user avatar
  • 129
1 vote
2 answers
314 views

How to detect thin extrusions from a polygon?

I want to create a minimal polygon which approximates the boundary of an arbitrary (semi-random) shape. By "minimal" I mean, "as few points as possible". The original shape (to be bounded) is in ...
ChrisW's user avatar
  • 3,417
1 vote
0 answers
55 views

Check if a point is deviating from a path made by a set of line segments

I'd like to know or have other ideas --other than my solution-- about how to check if a car on a given position (lat, lng) is getting away (let's say a distance D away) from the path where the car ...
Sergio Guillen Mantilla's user avatar
0 votes
1 answer
2k views

Calculate largest square in rectangle with a given vertex

There are two points (x1, y1) and (x2, y2), each of which can be any real integer pair. These define a rectangle R with vertices {(x1, y1), (x2, y2), (x1, y2), (x2, y1)}. The rectangle exists in a ...
AaronF's user avatar
  • 101
-1 votes
1 answer
215 views

Effecient ways to find the squares enclosed by a path on their edges

If we have a 2d grid (e.g. points at every (x,y) such that x and y are integers) and a closed path on this grid, such that a point on the path (x,y) could only be followed by a point in [(x+1,y), (x-1,...
Rrab's user avatar
  • 11
3 votes
1 answer
268 views

Building 3D from 2D

If you have an image sheet of facets and data to indicate which point on each facet should connect with other points on the other facets, is it possible to position those facets in 3D space based on ...
Matt W's user avatar
  • 447
2 votes
2 answers
595 views

Algorithm for lines comparison

I'm working on the import of land-use data into Openstreetmap. Unfortunately I've encountered a problem that has delayed my time table. Take a look at the picture below: the red line is the main road ...
Davide_sd's user avatar
  • 147
2 votes
1 answer
163 views

Place circle such that it overlaps the most possible other circles

Given a list of circles (each with parameters (x,y,radius) ) I want to place another circle with a fixed radius such that it overlaps the maximum possible circles from the list of circles. As long ...
heishe's user avatar
  • 233
2 votes
4 answers
2k views

Storing a straight line equation

How to store a straight line (infinite length, not a line segment) efficiently? This is not a duplication of How to represent a geometric line programmatically?, because the linked question is about ...
SOFe's user avatar
  • 708
0 votes
1 answer
38 views

Find whether or not current location is near other locations with given radii

tl;dr: "Am I, with any given location, inside of any number of circles with varying radii" Assume you have a database full of locations (coordinates) with arbitrary radii. Now the user enters and ...
pmilla1606's user avatar
1 vote
1 answer
805 views

tiling algorithm for maximum size of equal-sized tiles

I'm trying to fit an arbitrary number of HD videos on screen so that they all have equal size, maximizing the size of the videos, with no scrollbars appearing. Given N number of tiles of equal aspect ...
RedFilter's user avatar
  • 119
3 votes
1 answer
346 views

Neighbourhood points (2d)

I have a 2d coordinates system with some points on it, like this one: Now I am looking for an algorithm (or just some approach) to find neighboured points. So, if you have the coordinates of one ...
palsch's user avatar
  • 171
8 votes
3 answers
363 views

Generate equally sized areas in polygon

I am looking for a pseudo code logic that would find n equally sized areas in a given polygon. No space should be between or outside the matched areas. First valid match of areas should be returned. ...
Sergey Lukin's user avatar
3 votes
0 answers
143 views

Polygon simplification that encloses original set of points

I have been trying to implement an optimization for 2D sprite rendering to fight the problem of limited fillrate on mobile devices. The idea is to render textured polygons instead of quads that will ...
Adrian Lis's user avatar
4 votes
1 answer
1k views

How to generalize the planar case of the closest pair problem to d dimensions?

I'm trying to create a solution for the Closest pair problem using d-dimensional points. I've done a thorough search on google but it seems that there is no explanation for the d-dimensional case ...
Adam Arold's user avatar
  • 1,180
3 votes
2 answers
228 views

How to synchronize segments in polylines?

My input are two polylines -- I had one polyline and I computed offset of it, similarly to polygons. Here is the useful post: https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-...
greenoldman's user avatar
  • 1,526
2 votes
1 answer
1k views

Number of parallel lines in a given set of lines [closed]

I am given N lines, i.e, I am given a,b,c for N lines. And each line is of the form ax + by + c = 0. I need to find out the maximum number of lines that are parallel to each other. For this, first I ...
user avatar
1 vote
0 answers
1k views

distribute rectangles in order to do not overlap

I've a series of labels and icons inside the screen. A label is on the right of corresponding icon. I must perform a sort of declutter: when two or more labels overlap each other (or a label with an ...
Jepessen's user avatar
  • 123
2 votes
1 answer
124 views

Which algorithm to find the shortest (nodes count) path that encompasses all polygons inside a larger polygon?

Inside a large polygon (say the USA boundaries) I need to find the shortest path that will encompass smaller polygons (say the following cities: Kansas city, St Louis, Memphis, Oklahoma City) By ...
frenchone's user avatar
  • 129
3 votes
3 answers
2k views

Find a line that is closest to scattered points

I came across the below interview question on Glassdoor: A scatter graph of points on a page, draw a horizontal line across the page such the the perpendicular y distance to the line from all ...
Chander Shivdasani's user avatar
3 votes
0 answers
66 views

Project a piece of image cut by N-vertex shape to a different N-vertex shape

I have an N-vertex shape that I cut out from an image, and I want to project it onto another shape with the same amount of vertices, but different. So, the image will get changed inside the projection....
noncom's user avatar
  • 293
0 votes
1 answer
221 views

How can I map a number of points of a polygon to matching points of a larger rectangle?

Suppose I have 2D polygon image and a larger 2D rectangle image and that I have a collection of points for each that I want to align. For Example the polygon has point collection: [PA(a, b), PB(c, d)...
SMTF's user avatar
  • 101
6 votes
3 answers
3k views

How to determine if set of ordered coordinates form a simple curve?

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science. Eventually this seemed more suitable. Anyway, some background first: A closed curve, is ...
so.very.tired's user avatar
6 votes
3 answers
17k views

Efficient method for finding closest point to a line segment from a set of points including line segment's vertices

Let's say I have a list of points (in my case, point objects in a Python implementation). I then have a line segment connecting two of these points. I want to know if there's a way to efficiently ...
acm_myk's user avatar
  • 123
6 votes
3 answers
2k views

Method for determining if a line segment is an external edge of a Delauney triangulation?

I've created a Delauney triangulation of a set of points. Now I want to iterate over the triangulation and remove any line segments/edges on the exterior for which the following are true: The outside ...
acm_myk's user avatar
  • 123
1 vote
0 answers
1k views

Algorithm for sweeping a 2d shape along a curve?

I am trying to create a graphics application where the user can use an arbitrary shape as a "brush", which will be swept along the drawing path. The shape may be transformed along the path (rotated, ...
Neil Mussett's user avatar
13 votes
2 answers
3k 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 is ...
Dusan's user avatar
  • 585
1 vote
1 answer
494 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 ...
TND's user avatar
  • 263
0 votes
0 answers
1k 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, ...
Dennis's user avatar
  • 8,247
1 vote
2 answers
225 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 + r1....
Jason Madux's user avatar
4 votes
2 answers
4k 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 ...
Stephan Kolassa's user avatar
2 votes
1 answer
720 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 ...
Ted's user avatar
  • 121
2 votes
5 answers
2k 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 ...
Rob Perkins's user avatar
6 votes
3 answers
390 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: Now ...
wRAR's user avatar
  • 163
5 votes
2 answers
4k 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 ...
shoham's user avatar
  • 225
4 votes
1 answer
233 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 ...
Mr. Smith's user avatar
  • 291
5 votes
2 answers
4k 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 ...
Morwenn's user avatar
  • 1,766
11 votes
5 answers
10k 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 ...
laalee's user avatar
  • 111
5 votes
3 answers
2k 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 ...
Morwenn's user avatar
  • 1,766