Locate grid cells that intersect a quadrilateral of any shape

I am looking to identify the indexes [x, y] for grid cells that intersect with a quadrilateral shape characterized by its corner coordinates;

  • each grid cell measures 128 x 128 px

  • grid cells are assigned an integer index between [-nx, -ny] and [nx, ny]
    (the maximum area covered is a square measuring (2nx * 128) * (2ny * 128) px)

  • the quadrilateral's shape is delineated by corner points with pixel-space coordinates (qx, qy) supplied in the order of (tl, tr, br, bl)

  • This task is integrated into a three.js scene:
    • The corner points/coordinates are determined via raycasting from the camera on a base THREE.PlaneBufferGeometry

How can I efficiently obtain all intersecting tiles using JavaScript?

Currently, my approach involves calculating perimeter tiles by traversing each edge of the quadrilateral utilizing mx + b with a step equal to the tile dimension (128px); then, I add interior tile indexes row by row. However, this method seems somewhat cumbersome, which could be due to coding skills. I am considering using THREE.Raycaster to acquire the perimeter tile indexes, but I am unsure of the process.

I am in search of a more optimized solution algorithmically; whether it be basic formulas, pseudo code, concepts, or definitive solutions.

javascriptperformancethree.jsgeometrycomputational-geometry

Answer №1

For an efficient way to locate grid cells where quad edges intersect, consider utilizing the Woo and Amanatides grid traversal algorithm as outlined in their article titled "Fast Voxel Traversal Algorithm...".
A practical implementation can be found in the grid traversal section available here
See the example below:

https://i.sstatic.net/BFYPN.png

To handle inner cells of convex quads: while traversing edges, remember the leftmost cell in a row for "right" edges, the rightmost cell for "left" edges, and fill in any horizontal gap between them.

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Error: Cannot execute 'x' as a function

I am currently developing an Express web application that initiates JavaScript scraping code upon the page's initial load. Below is the node web scraping code (scrape.js): const request = require('request-promise'); const cheerio = require( ...

javascriptnode.jsexpressweb-scraping

Asking for something with no discernible purpose

I'm currently working on implementing a button that will trigger a request to display a login page. My goal is to restrict access to the login page only to project admins. To achieve this, I have their IP addresses and cross-reference them with those ...

javascriptnode.jsmongodbejs

The `$(this).data()` function removes any excess data from a database, stopping at the first occurrence of a

One issue I am encountering is when retrieving data with a whitespace. I need the complete string of data, not the trimmed version. When retrieving "data-title" or "data-type", the data gets cut at the whitespace. I tested by setting a static string in ...

javascriptphp

Having trouble accessing Kotlin JS from JavaScript

I'm currently experiencing an issue where I am unable to call any Kotlin JS function and receiving an error stating that 'something' is not defined. Initially, I attempted compiling the project with Gradle but found success after following ...

javascriptgradlekotlinnpmwebpack

developing a dropdown menu in JavaScript using data from a text document

Is it possible to achieve this task? If so, any assistance would be greatly appreciated. I am relatively new to JavaScript and have limited knowledge of syntax rules and best practices. I've created some functions in an external file. var myFunction ...

javascripthtmlcsstext

A function that takes one argument and performs named destructuring operations

Is it possible to classify a function like this as a unary function? function unaryOrNot([foo,bar,baz,...args,]){} When given an input such as: [1,2,3,4,5,6,7,8,9] Even though there is technically only one input, I still have named access to foo, bar, an ...

javascriptarraysdestructuring

Dynamic resizing navigation with JQUERY

I have successfully created a navigation menu that dynamically resizes each list item to fit the entire width of the menu using JavaScript. $(function() { changeWidth(500); function changeWidth(menuWidth){ var menuItems = $('#menu l ...

javascriptjquerycssnavigation

What is the best way to pass a value from an AJAX function back to its parent in JavaScript?

I am attempting to determine the appropriate response (true or false) for a function based on the outcome of an AJAX call within it. However, I am unsure of the correct approach to achieve this. (function($) { $('#example').ajaxForm({ ...

javascriptjqueryajax

Displaying images retrieved from firebase on a React.js application

Currently, I am attempting to retrieve images from Firebase storage and then exhibit them in a React component. As a newcomer to React/Javascript, I find it challenging to grasp the asynchronous nature of React/JS. The issue I'm facing is that althoug ...

javascriptreactjsfirebase

Turn off transition animations

How do I turn off animation in certain cases? https://jsfiddle.net/4b3nxv7n/ <div id="flip-list-demo" class="demo" :class="{'animate': animate}"> <button v-on:click="shuffle">Shuffle</button> <input type="checkbox" v-mo ...

javascriptanimationvue.jscss-transitionsvuejs2

Strange rendering issues when using the react material-ui dialog

Exploring the Project Recently, I developed a front-end project focusing on a delivery service using React and Material UI. One interesting feature I added was a Dialog window that pops up when users click on an item, allowing them to customize it. Here i ...

javascriptreactjsmaterial-uireact-hooksrendering

Issues encountered when trying to access a POST endpoint with .NET Framework 4.6.2

I have developed a WEB API using .NET Framework 4.6.2, specifically in my AuthController where I have implemented a test endpoint that requires a parameter. Unfortunately, I am encountering issues in hitting this endpoint and receiving the following error ...

javascriptjquery.netasp.net-mvcasp.net-web-api

Problems arise when JQuery fails to function properly alongside ajax page loading

While utilizing ajax to load the page, I encountered an issue where the jQuery on the loaded page template was not functioning until the page was manually refreshed. The ready function being used is: jQuery(document).ready(function() { jQuery(' ...

javascriptjqueryajaxdocument-ready

Combining numerous (nearly identical) duplicate each statements

I am faced with a series of each statements that are very similar and need to add around 20 more like them. My challenge is figuring out how to streamline the variables used in these statements into a single statement for efficiency, instead of repeating a ...

javascriptjquery

Is there a way to prevent javascript from automatically inserting tags when selecting text?

If you want to view the Fiddle Here Essentially, it's a text-highlighting tool that works almost flawlessly. The problem arises when it encounters tags like <p> or <br> within the selection. The JavaScript code seems to automatically in ...

javascriptjqueryhtml

Creating an automatic response button on Whatsapp with VB 2019 and Selenium Chrome

Hello friends and developers, I am interested in creating a WhatsApp automation bot using Selenium Chrome in VB 2019. However, I have been facing issues with creating a button on WhatsApp messages for auto-reply. I have come across some code in Node.js bu ...

javascriptc#vb.netselenium-webdriverwhatsapp

When examining the buffer property of each uploaded file, particularly when dealing with multiple files

I'm encountering an issue while trying to upload multiple files to my server using multer. Although I can access the req.files array, I am unable to retrieve the buffer property of the files. Upon attempting to log them with console.log, all I get is ...

javascriptexpressmulter

Understanding the concept of inertia within the OrbitControls feature of ThreeJS

I have implemented THREE.OrbitControls to rotate my objects in a project. Yet, I am interested in incorporating some inertia for the camera rotation so that it gradually comes to a stop after the user stops moving the mouse. What would be the best approa ...

javascriptthree.js

Extract the values from multiple checkboxes and display them using a foreach loop

Hello there! I have a form on a page with multiple dynamically added checkboxes. The number of checkboxes is unknown, here is the code snippet: <form action="" method="" style="margin:0px;" onsubmit="return sharedocxss();" id="share90_FORMh8"> < ...

javascriptphpjqueryhtmlcss

The Challenge of Testing React Components with Jest

Currently, I am delving into the realm of testing with React and Jest. I have encountered some challenges and could use some assistance navigating through them. In one of my react components, I have a logout method that is structured as follows: doLogou ...

javascriptreactjstesting