Suppose you have a set of segments in R^2 (call it S). Every segment is contained in a box of dimension WxH (so, the set S has four additional segments, one for each side of the box) and a segment s to be addedd to S. The segment s starts from point A (that will belong to one of the segment in S) and ends at point B. What i want to compute is the point B' such that B'belongs to one of the segment in S and A-B' does not intersect any other segment in S. Is there a wat to compute B' without using a brute-force algorithm (that is, intersecting AB with every other segment in S)?
Speeding up segment/set of segment intersection
148 views Asked by Marco Masci At
1
There are 1 answers
Related Questions in COMPUTATIONAL-GEOMETRY
- Sweep shape along 3D path in Python
- 'plotAtlas' function in Morpho package
- Encounter problem at different speed/start point algorithm design
- Selecting suitable triangles to intersect with a line
- Merging Geodataframe Polygons to Meet Population Threshold in Python
- Rotating a 3D body in python results in holes in the body
- SageMath: Create a triangle with specific angles in Hyperbolic space, eg., Upper Halfspace Plane
- reducing a massive tetrahedron mesh using gmsh or other way
- Implementing Jarvis Binary Search in Chan's algorithm
- How to find centroid snapped to grid via Shapely?
- Find the largest rectangle that doesn't intersect any given polygon
- Generate P random N-dimensional points from list of ALL possible pairwise distances
- Fast way to find closest line segment for a large set of planar points [Python]
- how to check if all the faces face outward
- Counting the number of polygons containing origin in 2D
Related Questions in INTERSECTION
- How do I find the line segments formed by the meeting of two sides of two polygons?
- How much exact are the operations in CGAL function "halfspace intersection with constructions"
- Custom equality comparator for set operation in Kotlin
- confuse about union and intersection type on typescript
- NetTopologySuite - how to detect when rectangle intersects circle?
- Find the Largest Area of Square Inside Two Rectangles(Intersection)
- Finding Intersections of Cones on a Sphere
- Intersecting two panda dataframe
- Shapely can't find intersection points that definitely exist
- create intersection points between lists of functions
- Lookahead assertion can work like a type of intersection of regular expressions, but why? (JavaScript)
- Union of intersected rotated boxes
- Ray-Triangle Intersection Issue in java
- How to merge two columns by the intersection of the elements in each col?
- Check intersection and draggable svg path (svgdotjs and kld-intersections)
Related Questions in LINE-SEGMENT
- Determining Number of Line Segment Intersections
- Line segmentation detection line draw by hand
- Ramer Douglas Peucker Algorithmn (Python)
- Generating a lattice graph from line segments
- How to swap nodes in a Balanced Binary Search Tree for a line segment intersection detection
- Identifying Rectangles from a Large Set of Line Segments in Python
- BinaryDescriptor in Python/OpenCV
- Finding pixel closest (grid points) to rectilinear polygons
- Is there a way in R to find the perpendicular distance between a point and a line segment?
- How to realize the conversion animation of two LineSegments in Three.js
- How do I find the intersection point of two line SEGMENTS, if one exists?
- Find most optimal algorithm for given problem
- THREE.LineSegments - geometry.needsUpdate is not updating
- How to move the end points of a line to keep its length but make it parallel to another line (C# preferably!)
- Find closest point to each line segment and expand/shrink the network graph - Python
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
"Real-time Collision Detection" by Ericson (table of contents) is a great resource for solving problems like this. Chapter 7 spatial partitioning lists a number of methods suitable for solving such problems.
Consider starting with Octrees, KD-Trees or spatial hashing. They are all reasonably easy to implement, and will make the problem go from O(n^2) to (from memory) O(n log n)