midpoint.rs.html -- source

Files

ab_glyph_rasterizer

geometry.rs lib.rs raster.rs

addr2line

adler

andrew

shapes

mod.rs rectangle.rs

text

fontconfig.rs mod.rs

approx

abs_diff_eq.rs lib.rs macros.rs relative_eq.rs ulps_eq.rs

arrayvec

array.rs array_string.rs char.rs errors.rs lib.rs maybe_uninit.rs

ash

atom

backtrace

backtrace

libunwind.rs mod.rs

symbolize

gimli

elf.rs mmap_unix.rs stash.rs

gimli.rs mod.rs

capture.rs lib.rs print.rs types.rs

bitflags

byteorder

calloop

sources

channel.rs generic.rs mod.rs ping.rs signals.rs timer.rs

sys

epoll.rs mod.rs

lib.rs list.rs loop_logic.rs

cfg_if

colorful

core

color_string.rs colors.rs hsl.rs mod.rs rgb.rs style.rs symbols.rs

conrod_core

conrod_derive

common.rs lib.rs style.rs utils.rs

conrod_example_shared

conrod_gfx

conrod_glium

conrod_piston

draw.rs event.rs lib.rs

conrod_rendy

lib.rs vertex.rs

conrod_vulkano

conrod_wgpu

conrod_winit

lib.rs macros.rs v020.rs v021.rs v022.rs v023.rs

copyless

boxed.rs lib.rs vec.rs

copypasta

common.rs lib.rs nop_clipboard.rs wayland_clipboard.rs x11_clipboard.rs

crossbeam

crossbeam_channel

flavors

after.rs array.rs list.rs mod.rs never.rs tick.rs zero.rs

channel.rs context.rs counter.rs err.rs lib.rs select.rs select_macro.rs utils.rs waker.rs

crossbeam_deque

crossbeam_epoch

sync

list.rs mod.rs queue.rs

atomic.rs collector.rs default.rs deferred.rs epoch.rs guard.rs internal.rs lib.rs

crossbeam_queue

array_queue.rs err.rs lib.rs seg_queue.rs

crossbeam_utils

atomic

atomic_cell.rs consume.rs mod.rs seq_lock.rs

sync

mod.rs parker.rs sharded_lock.rs wait_group.rs

backoff.rs cache_padded.rs lib.rs thread.rs

daggy

lib.rs walker.rs

dlib

downcast_rs

draw_state

lib.rs preset.rs state.rs target.rs

either

fixedbitset

lib.rs range.rs

float

fnv

futures

futures_channel

mpsc

mod.rs queue.rs sink_impl.rs

lib.rs lock.rs oneshot.rs

futures_core

task

__internal

atomic_waker.rs mod.rs

future.rs lib.rs stream.rs

futures_executor

enter.rs lib.rs local_pool.rs

futures_io

futures_macro

join.rs lib.rs select.rs

futures_sink

futures_task

arc_wake.rs future_obj.rs lib.rs noop_waker.rs spawn.rs waker.rs waker_ref.rs

futures_util

async_await

join_mod.rs mod.rs pending.rs poll.rs random.rs select_mod.rs

future

io

lock

bilock.rs mod.rs mutex.rs

sink

buffer.rs close.rs drain.rs err_into.rs fanout.rs flush.rs map_err.rs mod.rs send.rs send_all.rs with.rs with_flat_map.rs

stream

task

mod.rs spawn.rs

fns.rs lib.rs never.rs

fxhash

getrandom

error.rs error_impls.rs lib.rs linux_android.rs use_file.rs util.rs util_libc.rs

gfx

macros

mod.rs pso.rs structure.rs

pso

buffer.rs bundle.rs mod.rs resource.rs target.rs

encoder.rs factory.rs lib.rs shade.rs slice.rs

gfx_backend_empty

buffer.rs descriptor.rs image.rs lib.rs memory.rs

gfx_backend_vulkan

command.rs conv.rs device.rs info.rs lib.rs native.rs pool.rs window.rs

gfx_core

buffer.rs command.rs dummy.rs factory.rs format.rs handle.rs lib.rs mapping.rs memory.rs pso.rs shade.rs texture.rs

gfx_descriptor

allocator.rs counts.rs lib.rs

gfx_hal

gfx_memory

allocator

dedicated.rs general.rs linear.rs mod.rs

heaps

heap.rs memory_type.rs mod.rs

block.rs lib.rs mapping.rs memory.rs stats.rs usage.rs

gimli

glium

backend

glutin

headless.rs mod.rs

buffer

alloc.rs fences.rs mod.rs view.rs

context

capabilities.rs extensions.rs mod.rs state.rs

draw_parameters

blend.rs depth.rs mod.rs query.rs stencil.rs

framebuffer

default_fb.rs mod.rs render_buffer.rs

index

buffer.rs mod.rs multidraw.rs

ops

blit.rs clear.rs draw.rs mod.rs read.rs

program

binary_header.rs compute.rs mod.rs program.rs raw.rs reflection.rs shader.rs uniforms_storage.rs

texture

any.rs bindless.rs buffer_texture.rs get_format.rs mod.rs pixel.rs pixel_buffer.rs ty_support.rs

uniforms

bind.rs buffer.rs mod.rs sampler.rs uniforms.rs value.rs

utils

bitsfield.rs mod.rs range.rs

vertex

buffer.rs format.rs mod.rs transform_feedback.rs

debug.rs fbo.rs field.rs image_format.rs lib.rs macros.rs pixel_buffer.rs sampler_object.rs sync.rs version.rs vertex_array_object.rs

glutin

api

egl

make_current_guard.rs mod.rs

glx

make_current_guard.rs mod.rs

osmesa

dlloader.rs mod.rs

platform

platform_impl

unix

x11

mod.rs wayland.rs x11.rs

context.rs lib.rs windowed.rs

glutin_egl_sys

glutin_glx_sys

graphics

half

bfloat

binary16

bfloat.rs binary16.rs lib.rs slice.rs

hibitset

iter

drain.rs mod.rs

atomic.rs lib.rs ops.rs util.rs

inplace_it

guards

mod.rs slice_memory_guard.rs uninitialized_slice_memory_guard.rs

alloc_array.rs fixed_array.rs lib.rs

input

after_render.rs button.rs close.rs controller.rs cursor.rs event_id.rs focus.rs generic_event.rs idle.rs keyboard.rs lib.rs mouse.rs render.rs resize.rs text.rs touch.rs update.rs

instant

lib.rs native.rs

interpolation

ease.rs lerp.rs lib.rs

iovec

sys

itoa

lazy_static

inline_lazy.rs lib.rs

lazycell

libc

unix

linux_like

linux

gnu

b64

x86_64

align.rs mod.rs not_x32.rs

align.rs mod.rs

align.rs mod.rs

align.rs mod.rs

fixed_width_ints.rs lib.rs macros.rs

libloading

os

unix

consts.rs mod.rs

changelog.rs error.rs lib.rs util.rs

line_drawing

bresenham.rs bresenham_3d.rs bresenham_circle.rs grid_walking.rs lib.rs midpoint.rs octant.rs steps.rs walk_voxels.rs xiaolin_wu.rs

linked_hash_map

lock_api

lib.rs mutex.rs remutex.rs rwlock.rs

log

lib.rs macros.rs

maybe_uninit

memchr

x86

avx.rs mod.rs sse2.rs

fallback.rs iter.rs lib.rs naive.rs

memmap

memoffset

lib.rs offset_of.rs raw_field.rs span_of.rs

miniz_oxide

deflate

buffer.rs core.rs mod.rs stream.rs

inflate

core.rs mod.rs output_buffer.rs stream.rs

lib.rs shared.rs

mio

mio_extras

channel.rs lib.rs timer.rs

naga

back

spv

helpers.rs layout.rs mod.rs writer.rs

front

mod.rs spv.rs wgsl.rs

proc

interface.rs mod.rs typifier.rs validator.rs

arena.rs lib.rs

net2

sys

unix

impls.rs mod.rs

ext.rs lib.rs socket.rs tcp.rs udp.rs unix.rs utils.rs

nix

nom

bits

complete.rs macros.rs mod.rs streaming.rs

branch

macros.rs mod.rs

bytes

complete.rs macros.rs mod.rs streaming.rs

character

complete.rs macros.rs mod.rs streaming.rs

combinator

macros.rs mod.rs

multi

macros.rs mod.rs

number

complete.rs macros.rs mod.rs streaming.rs

sequence

macros.rs mod.rs

error.rs internal.rs lib.rs methods.rs str.rs traits.rs util.rs whitespace.rs

num

num_bigint

algorithms.rs bigint.rs biguint.rs lib.rs macros.rs monty.rs

num_complex

cast.rs lib.rs pow.rs

num_cpus

lib.rs linux.rs

num_integer

average.rs lib.rs roots.rs

num_iter

num_rational

num_traits

object

once_cell

imp_std.rs lib.rs

ordered_float

ordermap

equivalent.rs lib.rs macros.rs mutable_keys.rs set.rs util.rs

osmesa_sys

owned_ttf_parser

convert.rs lib.rs owned.rs

parking_lot

condvar.rs deadlock.rs elision.rs lib.rs mutex.rs once.rs raw_mutex.rs raw_rwlock.rs remutex.rs rwlock.rs util.rs

parking_lot_core

thread_parker

linux.rs mod.rs

lib.rs parking_lot.rs spinwait.rs util.rs word_lock.rs

percent_encoding

petgraph

pin_project

pin_project_internal

pin_project

attribute.rs derive.rs mod.rs

lib.rs pinned_drop.rs project.rs utils.rs

pin_project_lite

pin_utils

lib.rs projection.rs stack_pin.rs

ppv_lite86

x86_64

lib.rs soft.rs types.rs

proc_macro2

detection.rs fallback.rs lib.rs marker.rs parse.rs wrapper.rs

proc_macro_hack

error.rs iter.rs lib.rs parse.rs quote.rs

proc_macro_nested

quote

ext.rs format.rs ident_fragment.rs lib.rs runtime.rs spanned.rs to_tokens.rs

rand

rand_chacha

chacha.rs guts.rs lib.rs

rand_core

block.rs error.rs impls.rs le.rs lib.rs os.rs

raw_window_handle

read_color

relevant

rendy

rendy_chain

chain

schedule

family.rs mod.rs queue.rs submission.rs

collect.rs lib.rs node.rs resource.rs sync.rs

rendy_command

buffer

encoder.rs level.rs mod.rs reset.rs state.rs submit.rs usage.rs

family

mod.rs queue.rs submission.rs

capability.rs fence.rs lib.rs pool.rs

rendy_core

types

mod.rs vertex.rs

backend.rs casts.rs features.rs lib.rs slow.rs wrap.rs

rendy_descriptor

allocator.rs lib.rs ranges.rs

rendy_factory

barriers.rs blitter.rs config.rs factory.rs lib.rs upload.rs

rendy_frame

cirque

command.rs mod.rs

frame.rs lib.rs

rendy_graph

graph

node

render

group

mod.rs simple.rs

mod.rs present.rs

rendy_init

rendy_memory

allocator

dedicated.rs dynamic.rs linear.rs mod.rs

heaps

heap.rs memory_type.rs mod.rs

mapping

mod.rs range.rs write.rs

block.rs lib.rs memory.rs usage.rs util.rs utilization.rs

rendy_mesh

format.rs lib.rs mesh.rs

rendy_resource

sampler

cache.rs mod.rs

buffer.rs escape.rs image.rs lib.rs resources.rs set.rs

rendy_shader

rendy_texture

format.rs lib.rs pixel.rs texture.rs

rendy_wsi

rustc_demangle

legacy.rs lib.rs v0.rs

rustc_hash

rusttype

ryu

buffer

pretty

exponent.rs mantissa.rs mod.rs

common.rs d2s.rs d2s_full_table.rs d2s_intrinsics.rs digit_table.rs f2s.rs f2s_intrinsics.rs lib.rs

same_file

scoped_tls

scopeguard

serde

de

from_primitive.rs ignored_any.rs impls.rs mod.rs utf8.rs value.rs

private

de.rs macros.rs mod.rs ser.rs

ser

fmt.rs impls.rs impossible.rs mod.rs

export.rs integer128.rs lib.rs macros.rs

serde_derive

internals

ast.rs attr.rs case.rs check.rs ctxt.rs mod.rs symbol.rs

bound.rs de.rs dummy.rs fragment.rs lib.rs pretend.rs ser.rs try.rs

serde_json

features_check

io

value

de.rs from.rs index.rs mod.rs partial_eq.rs ser.rs

de.rs error.rs iter.rs lib.rs macros.rs map.rs number.rs read.rs ser.rs

shaderc

shaderc_sys

shared_library

dynamic_library.rs lib.rs

slab

smallvec

smithay_client_toolkit

data_device

data_device.rs data_offer.rs data_source.rs mod.rs

keyboard

ffi.rs keysyms.rs mod.rs

pointer

mod.rs theme.rs

shell

mod.rs wl.rs xdg.rs zxdg.rs

utils

mempool.rs mod.rs

window

basic_frame.rs concept_frame.rs mod.rs

env.rs lib.rs output.rs surface.rs

smithay_clipboard

lib.rs threaded.rs

spirv_headers

autogen_spirv.rs lib.rs

stb_truetype

syn

takeable_option

texture

thiserror

aserror.rs display.rs lib.rs

thiserror_impl

ast.rs attr.rs expand.rs fmt.rs lib.rs prop.rs valid.rs

thread_profiler

time

display.rs duration.rs lib.rs parse.rs sys.rs

tracing

dispatcher.rs field.rs instrument.rs level_filters.rs lib.rs macros.rs span.rs stdlib.rs subscriber.rs

tracing_core

callsite.rs dispatcher.rs event.rs field.rs lib.rs metadata.rs parent.rs span.rs stdlib.rs subscriber.rs

ttf_parser

typed_arena

unicode_xid

lib.rs tables.rs

vecmath

lib.rs traits.rs

viewport

vk_sys

void

vulkano

buffer

cpu_access.rs cpu_pool.rs device_local.rs immutable.rs mod.rs slice.rs sys.rs traits.rs usage.rs view.rs

command_buffer

descriptor

descriptor_set

collection.rs fixed_size_pool.rs mod.rs persistent.rs std_pool.rs sys.rs unsafe_layout.rs

pipeline_layout

empty.rs limits_check.rs mod.rs runtime_desc.rs sys.rs traits.rs tweaks.rs union.rs

descriptor.rs mod.rs

device

extensions.rs mod.rs

framebuffer

attachments_list.rs compat_atch.rs desc.rs empty.rs framebuffer.rs macros.rs mod.rs sys.rs traits.rs

image

attachment.rs immutable.rs layout.rs mod.rs storage.rs swapchain.rs sys.rs traits.rs usage.rs

instance

debug.rs extensions.rs instance.rs layers.rs limits.rs loader.rs mod.rs

memory

pool

host_visible.rs mod.rs non_host_visible.rs pool.rs

device_memory.rs mod.rs

pipeline

query

swapchain

capabilities.rs display.rs mod.rs present_region.rs surface.rs swapchain.rs

sync

future

fence_signal.rs join.rs mod.rs now.rs semaphore_signal.rs

event.rs fence.rs mod.rs pipeline.rs semaphore.rs

extensions.rs features.rs format.rs lib.rs sampler.rs version.rs

vulkano_shaders

codegen.rs descriptor_sets.rs entry_point.rs enums.rs lib.rs parse.rs spec_consts.rs spirv_search.rs structs.rs

walkdir

dent.rs error.rs lib.rs util.rs

wayland_client

native_lib

display.rs event_queue.rs mod.rs proxy.rs

cursor.rs display.rs event_queue.rs globals.rs lib.rs proxy.rs sinks.rs

wayland_commons

debug.rs filter.rs lib.rs map.rs socket.rs user_data.rs wire.rs

wayland_cursor

wayland_egl

wayland_protocols

lib.rs misc.rs protocol_macro.rs stable.rs unstable.rs wlr.rs

wayland_sys

client.rs common.rs egl.rs lib.rs server.rs

wgpu

backend

direct.rs mod.rs native_gpu_future.rs

util

lib.rs macros.rs

wgpu_core

wgpu_types

winit

platform

desktop.rs mod.rs unix.rs

platform_impl

linux

wayland

event_loop

mod.rs proxy.rs sink.rs state.rs

seat

keyboard

handlers.rs keymap.rs mod.rs

pointer

data.rs handlers.rs mod.rs

text_input

handlers.rs mod.rs

touch

handlers.rs mod.rs

window

env.rs mod.rs output.rs

x11

dpi.rs error.rs event.rs event_loop.rs icon.rs lib.rs monitor.rs window.rs

x11

dpms.rs glx.rs internal.rs keysym.rs lib.rs link.rs xcursor.rs xf86vmode.rs xfixes.rs xft.rs xinerama.rs xinput.rs xinput2.rs xlib.rs xlib_xcb.rs xmd.rs xmu.rs xrandr.rs xrecord.rs xrender.rs xss.rs xt.rs xtest.rs

x11_clipboard

error.rs lib.rs run.rs

x11_dl

dpms.rs error.rs glx.rs internal.rs keysym.rs lib.rs link.rs xcursor.rs xf86vmode.rs xfixes.rs xft.rs xinerama.rs xinput.rs xinput2.rs xlib.rs xlib_xcb.rs xmd.rs xmu.rs xrandr.rs xrecord.rs xrender.rs xss.rs xt.rs xtest.rs

xcb

ffi

xcursor

lib.rs parser.rs

xdg

xml

use {FloatNum, Point, SignedNum};
use octant::Octant;
use steps::Steps;

/// An implementation of the [mid-point line drawing algorithm].
///
/// The biggest difference between this algorithm and [`Bresenham`] is that it uses floating-point points.
///
/// Example:
///
/// ```
/// extern crate line_drawing;
/// use line_drawing::Midpoint;
///
/// fn main() {
///     for (x, y) in Midpoint::<f32, i8>::new((0.2, 0.02), (2.8, 7.7)) {
///         print!("({}, {}), ", x, y);
///     }
/// }
/// ```
///
/// ```text
/// (0, 0), (1, 1), (1, 2), (1, 3), (2, 4), (2, 5), (2, 6), (3, 7), (3, 8),
/// ```
///
/// [mid-point line drawing algorithm]: http://www.mat.univie.ac.at/~kriegl/Skripten/CG/node25.html
/// [`Bresenham`]: struct.bresenham.html
pub struct Midpoint<I, O> {
    octant: Octant,
    point: Point<O>,
    a: I,
    b: I,
    k: I,
    end_x: O,
}

impl<I: FloatNum, O: SignedNum> Midpoint<I, O> {
    #[inline]
    pub fn new(start: Point<I>, end: Point<I>) -> Self {
        // Get the octant to use
        let octant = Octant::new(start, end);

        // Convert the points into the octant versions
        let start = octant.to(start);
        let end = octant.to(end);

        // Initialise the variables

        let a = -(end.1 - start.1);
        let b = end.0 - start.0;
        let c = start.0 * end.1 - end.0 * start.1;

        Self {
            octant,
            a,
            b,
            point: (O::cast(start.0.round()), O::cast(start.1.round())),
            k: a * (start.0.round() + I::one()) + b * (start.1.round() + I::cast(0.5)) + c,
            end_x: O::cast(end.0.round()),
        }
    }

    #[inline]
    pub fn steps(self) -> Steps<Point<O>, Self> {
        Steps::new(self)
    }
}

impl<I: FloatNum, O: SignedNum> Iterator for Midpoint<I, O> {
    type Item = Point<O>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.point.0 <= self.end_x {
            let point = self.octant.from(self.point);

            // Take an N step
            if self.k <= I::zero() {
                self.k += self.b;
                self.point.1 += O::one();
            }

            // Take an E step
            self.k += self.a;
            self.point.0 += O::one();

            Some(point)
        } else {
            None
        }
    }
}

#[test]
fn tests() {
    let midpoint = |a, b| Midpoint::new(a, b).collect::<Vec<_>>();

    assert_eq!(
        midpoint((0.0, 0.0), (-5.0, -5.0)),
        [(0, 0), (-1, -1), (-2, -2), (-3, -3), (-4, -4), (-5, -5)]
    );

    assert_eq!(
        midpoint((0.0, 0.0), (6.0, 3.0)),
        [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 3), (6, 3)]
    );
}