Как сказать, если точка находится в пределах полигона для текстуры

Question

Это кажется довольно задаваемый вопрос - (выслушай меня первый :)

Я создал полигон Перлин шума, и это выглядит :

Мне нужно создать текстуру из этого массива точек. (Я использую Monogame/XNA, но я предполагаю, что этот вопрос несколько агностик).

В любом случае, исследование этой проблемы говорит мне, что многие люди используют raycasting to determine how many times a line crosses over the polygon shape (Если один раз, это внутри, дважды или нулевое время, оно снаружи). Это имеет смысл, но мне интересно, есть ли лучший способ, учитывая, что у меня есть все пункты. Выполнение небольшого raycast для каждого пикселя, который я хочу заполнить, кажется чрезмерным - это единственный/лучший способ?

Если у меня есть маленькое квадратное изображение размером 500 пикселей, которое мне нужно заполнить, мне нужно сделать raycast для 250 000 отдельных пикселей, что кажется ужасным.

Answer 1

Если вы хотите сделать это для каждого пикселя, вы можете использовать подметания линию:

Начните с самой верхней координате и исследовать горизонтальный луч слева направо. Вычислите все пересечения с многоугольником и отсортируйте их по их координате x. Затем повторите все пиксели в строке и запомните, находитесь ли вы или нет. Всякий раз, когда вы сталкиваетесь с перекрестком, переключитесь на другую сторону. Если какой-то пиксель включен, установите текстуру. Если нет, игнорируйте его. Сделайте это сверху вниз для каждой горизонтальной линии.

Расчет пересечения может быть увеличен несколькими способами. Например. используя структуру данных ускорения, такую ​​как сетка, квадранты и т. д. или путем изучения пересекающихся или трогательных краев многоугольника раньше. Затем, когда вы развернете линию, вы уже знаете, какие края вызовут пересечение.