amarao_san

Category:

математико-программистское

Краткая предистория: мой алгоритм ищет корни, раскидывая точки по «фикселу» (области в R², точнее, в f64xf64), соответствующей текущему размеру «пиксела». В моём текущем коде окно float'ов фиксированно (например от (-1.0;-1.0) до (1.0;1.0), а вот сколько туды пикселов влазит определяется разрешением окна. (В будущем я добавлю ресайз окна тоже). После того, как точки раскиданы, смотрится, есть ли у выражения положительные и отрицательные значения. Если есть — где-то между ними корень. Плюс, особое значение для точного нуля — вот он, корень. Плюс поддержка nan'ов.

Каждый фиксел (структура) хранит в себе координаты всех «probes», т.е. точек, для которых уже было посчитано. Например, если работа идёт с матрицей 2х2, то каждый фиксел имеет в себе 4 точки.

Интересное происходит, когда мы ресайзим окно. При ресайзе число фикселов меняется (или, при ресайзе окна в R² меняется содержимое фикселов). Пока не написан, но очевидно понятен алгоритм перекидывания точек между фикселами.

После чего нам надо посмотреть, у каких фикселов не хватает точек. И, допустим, у нас есть фиксел, в котором 3 из 4 точек. Где 4ую ставить? А если не хватает 2 из 4?

А если есть M точек, а надо N? Звучит, как интересный вопрос. Поскольку я сейчас никаким образом не думаю про содержимое точек (всякие градиенты и т.д.), то задача, видимо, сводится к поиску максимально удалённой точки от...

от чего? Пока что в голову приходит включить в список точек углы, и тогда будет «максимально удалённое от углов и существующих точек». Но, во-первых, решение неоднозначное (например, если у нас есть 1 точка в центре фиксела, ответом будет множество точек, хотя бы из соображений симметрии), а во-вторых нам надо учесть M (например, если оптимальным для 0 при 1 (нет точек, добавить одну) будет поставить в середине, то для 0 при 2 будет поставить две точки на 1/3 по горизонтали или вертикали.

Что-то у меня ощущение, что я какую-то банку с пауками открыл, и никакого супербыстрого решения там не бывает. Можно, конечно, монтекарлить...


Error

default userpic

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.