Создание модуля WebAssembly с помощью Emscripten, AssemblyScript и Rust24.02.2023 20:46

#pragma once

#include 

struct Point
{
	Point() : x(0.0f), y(0.0f) { }
	Point(float _x, float _y) : x(_x), y(_y) { }

	std::string to_string() const
	{
		return "(" + std::to_string(x) + ", " + std::to_string(y) + ")";
	}

	float x;
	float y;
};

std::vector triangulate(std::vector& points);

#include "point.h"

#include 
#include 
#include 
#include 

struct TriangleCircle
{
    // triangle point indices
    int i;
    int j;
    int k;

    // circle center
    float x;
    float y;

    // the square of the circle radius
    float radius_sq;

    std::string to_string() const
    {
        return "<" + std::to_string(i) + ", " + std::to_string(j) + ", " + std::to_string(k) + "|" + std::to_string(x) + ", " + std::to_string(y) + "|" + std::to_string(radius_sq) + ">";
    }
};

std::vector build_supertriangle(const std::vector &points)
{
    float x_min = FLT_MAX;
    float y_min = FLT_MAX;
    float x_max = FLT_MIN;
    float y_max = FLT_MIN;

    for (size_t i = 0; i < points.size(); i++)
    {
        const Point p = points[i];
        if (p.x < x_min) { x_min = p.x; }
        if (p.x > x_max) { x_max = p.x; }
        if (p.y < y_min) { y_min = p.y; }
        if (p.y > y_max) { y_max = p.y; }
    }

    float dx = x_max - x_min;
    float dy = y_max - y_min;

    float d_max = std::max(dx, dy);
    float x_mid = x_min + dx * 0.5f;
    float y_mid = y_min + dy * 0.5f;

    return { 
        Point(x_mid - 20.0f * d_max, y_mid - d_max),
        Point(x_mid, y_mid + 20.0f * d_max),
        Point(x_mid + 20.0f * d_max, y_mid - d_max) };
}

TriangleCircle circumcircle(const std::vector &points, int i, int j, int k)
{
    const Point point_i = points[i];
    const Point point_j = points[j];
    const Point point_k = points[k];

    float x_1 = point_i.x;
    float y_1 = point_i.y;

    float x_2 = point_j.x;
    float y_2 = point_j.y;

    float x_3 = point_k.x;
    float y_3 = point_k.y;

    float y1_y2 = std::abs(y_1 - y_2);
    float y2_y3 = std::abs(y_2 - y_3);

    float center_x = 0.0f;
    float center_y = 0.0f;
    float m_1 = 0.0f;
    float m_2 = 0.0f;
    float mx_1 = 0.0f;
    float mx_2 = 0.0f;
    float my_1 = 0.0f;
    float my_2 = 0.0f;

    float EPSILON = 0.00001f;

    if (y1_y2 < EPSILON)
    {
        m_2 = -(x_3 - x_2) / (y_3 - y_2);
        mx_2 = (x_2 + x_3) / 2.0f;
        my_2 = (y_2 + y_3) / 2.0f;
        center_x = (x_2 + x_1) / 2.0f;
        center_y = m_2 * (center_x - mx_2) + my_2;
    }
    else if (y2_y3 < EPSILON)
    {
        m_1 = -(x_2 - x_1) / (y_2 - y_1);
        mx_1 = (x_1 + x_2) / 2.0f;
        my_1 = (y_1 + y_2) / 2.0f;
        center_x = (x_3 + x_2) / 2.0f;
        center_y = m_1 * (center_x - mx_1) + my_1;
    }
    else
    {
        m_1 = -(x_2 - x_1) / (y_2 - y_1);
        m_2 = -(x_3 - x_2) / (y_3 - y_2);
        mx_1 = (x_1 + x_2) / 2.0f;
        mx_2 = (x_2 + x_3) / 2.0f;
        my_1 = (y_1 + y_2) / 2.0f;
        my_2 = (y_2 + y_3) / 2.0f;
        center_x = (m_1 * mx_1 - m_2 * mx_2 + my_2 - my_1) / (m_1 - m_2);
        center_y = y1_y2 > y2_y3 ? (m_1 * (center_x - mx_1) + my_1) : (m_2 * (center_x - mx_2) + my_2);
    }

    float dx = x_2 - center_x;
    float dy = y_2 - center_y;

    return TriangleCircle{ i, j, k, center_x, center_y, dx*dx + dy*dy};
}

void remove_duplicates(std::vector &edges)
{
    int j = edges.size();
    while (j >= 2)
    {
        int b = edges[--j];
        int a = edges[--j];

        int i = j;
        while (i >= 2)
        {
            int n = edges[--i];
            int m = edges[--i];

            if ((a == m && b == n) || (a == n && b == m))
            {
                edges.erase(std::next(edges.begin(), j), std::next(edges.begin(), j + 2));
                edges.erase(std::next(edges.begin(), i), std::next(edges.begin(), i + 2));

                j -= 2;
                break;
            }
        }
    }
}

std::vector triangulate(std::vector &points)
{
    size_t points_count = points.size();

    // if the nmber is less than 3, nothing to do
    if (points_count < 3)
    {
        return std::vector(0);
    }

    // sort points by x coordinate
    // create array with indices 0, 1, 2, ...
    std::vector indices(points_count);
    for (size_t  i = 0; i < points_count; i++)
    {
        indices[i] = i;
    }

    // sort it by using input points
    std::sort(indices.begin(), indices.end(), [&points](int a, int b) { return points[a].x < points[b].x; });

    const std::vector st = build_supertriangle(points);
    // add points of the super triangle into input array
    points.insert(points.end(), st.begin(), st.end());

    // create buffers
    std::vector open_list;
    std::vector closed_list;
    std::vector edges_list;

    // init open buffer by super triangle
    open_list.push_back(circumcircle(points, points_count, points_count + 1, points_count + 2));
    
    for (size_t i = 0; i < points_count; i++)
    {
        int c = indices[i];
        Point p = points[c];
        edges_list.clear();

        for (int j = open_list.size() - 1; j >= 0; j--)
        {
            TriangleCircle t = open_list[j];
            
            float dx = p.x - t.x;
            if (dx > 0.0f && dx*dx > t.radius_sq)
            {
                open_list.erase(open_list.begin() + j);
                closed_list.push_back(t);
                continue;
            }

            float dy = p.y - t.y;
            if (dx*dx + dy*dy - t.radius_sq > 0.00001f)
            {
                continue;
            }

            open_list.erase(open_list.begin() + j);
            edges_list.insert(edges_list.end(), { t.i, t.j, t.j, t.k, t.k, t.i });
        }

        // delete edges with two triangles
        remove_duplicates(edges_list);

        // add triangles for the remain edges to the open list
        int k = edges_list.size();
        while (k >= 2)
        {
            int b = edges_list[--k];
            int a = edges_list[--k];
            open_list.push_back(circumcircle(points, a, b, c));
        }
    }

    // add to the closest list all triangles from the remain open list
    for (size_t i = 0; i < open_list.size(); i++)
    {
        closed_list.push_back(open_list[i]);
    }

    open_list.clear();
    edges_list.clear();

    // form the output array
    std::vector triangles;
    for (size_t i = 0; i < closed_list.size(); i++)
    {
        TriangleCircle t = closed_list[i];
        if (t.i < points_count && t.j < points_count && t.k < points_count)
        {
            triangles.insert(triangles.end(), { t.i, t.j, t.k });
        }
    }

    closed_list.clear();

    return triangles;
}

#pragma once
#include "point.h"
#include 

struct AABB
{
	float x_min;
	float y_min;
	float x_max;
	float y_max;

	std::string to_string()
	{
		return "|" + std::to_string(x_min) + ", " + std::to_string(y_min) + ", " + std::to_string(x_max) + ", " + std::to_string(y_max) + "|";
	}
};

class Trinangle
{
public:
	Trinangle(const std::vector& vertices);
	~Trinangle() {};
	AABB get_aabb();
	Point get_center();
	bool is_point_inside(const Point &point);
	std::string to_string();

	Point get_a();
	Point get_b();
	Point get_c();

private:
	Point a;
	Point b;
	Point c;

	AABB aabb;
	Point center;
};

class BVHNode
{
public:
	BVHNode(const std::vector &triangles);
	~BVHNode();

	AABB get_aabb();
	bool is_inside_aabb(const Point &point);
	Trinangle* sample(const Point &point);

private:
	Trinangle* triangle;
	BVHNode* left_node;
	BVHNode* right_node;
	AABB aabb;
};

#include 
#include 

#include "bvh.h"

Trinangle::Trinangle(const std::vector &vertices)
{
	a = vertices[0];
	b = vertices[1];
	c = vertices[2];

	float x_min = FLT_MAX;
	float y_min = FLT_MAX;
	float x_max = FLT_MIN;
	float y_max = FLT_MIN;

	float x_accum = 0.0f;
	float y_accum = 0.0f;

	for (size_t i = 0; i < vertices.size(); i++)
	{
		Point v = vertices[i];
		if (v.x < x_min) { x_min = v.x; }
		if (v.x > x_max) { x_max = v.x; }
		if (v.y < y_min) { y_min = v.y; }
		if (v.y > y_max) { y_max = v.y; }

		x_accum += v.x;
		y_accum += v.y;
	}

	aabb = AABB{ x_min, y_min, x_max, y_max };
	center = Point(x_accum / vertices.size(), y_accum / vertices.size());
}

AABB Trinangle::get_aabb()
{
	return aabb;
}

Point Trinangle::get_center()
{
	return center;
}

bool Trinangle::is_point_inside(const Point& point)
{
	float as_x = point.x - a.x;
	float as_y = point.y - a.y;

	bool s_ab = ((b.x - a.x) * as_y - (b.y - a.y) * as_x) > 0;

	if (((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0) == s_ab)
	{
		return false;
	}
	if (((c.x - b.x) * (point.y - b.y) - (c.y - b.y) * (point.x - b.x) > 0) != s_ab)
	{
		return false;
	}
	return true;
}

std::string Trinangle::to_string()
{
	return "<" + a.to_string() + ", " + b.to_string() + ", " + c.to_string() + ">";
}

Point Trinangle::get_a()
{
	return a;
}

Point Trinangle::get_b()
{
	return b;
}
Point Trinangle::get_c()
{
	return c;
}

AABB union_aabb(AABB &x, AABB &y)
{
	return AABB {
		std::min(x.x_min, y.x_min), std::min(x.y_min, y.y_min), 
		std::max(x.x_max, y.x_max), std::max(x.y_max, y.y_max) };
}

BVHNode::BVHNode(const std::vector& triangles)
{
	triangle = NULL;
	left_node = NULL;
	right_node = NULL;

	int objects_count = triangles.size();
	if (objects_count == 1)
	{
		triangle = triangles[0];
		aabb = triangle->get_aabb();
	}
	else
	{
		float x_median = 0.0f;
		float y_median = 0.0f;

		float x_min = FLT_MAX;
		float x_max = FLT_MIN;
		float y_min = FLT_MAX;
		float y_max = FLT_MIN;

		for (size_t i = 0; i < objects_count; i++)
		{
			Trinangle* t = triangles[i];
			Point c = t->get_center();
			x_median += c.x;
			y_median += c.y;

			if (c.x < x_min) { x_min = c.x; }
			if (c.x > x_max) { x_max = c.x; }
			if (c.y < y_min) { y_min = c.y; }
			if (c.y > y_max) { y_max = c.y; }
		}

		int split_axis = ((x_max - x_min) > (y_max - y_min)) ? 0 : 1;
		float median = split_axis == 0 ? (x_median / objects_count) : (y_median / objects_count);

		std::vector left;
		std::vector right;

		for (size_t i = 0; i < objects_count; i++)
		{
			Trinangle* t = triangles[i];
			Point c = t->get_center();
			float v = split_axis == 0 ? c.x : c.y;
			if (v < median)
			{
				left.push_back(t);
			}
			else
			{
				right.push_back(t);
			}
		}

		if (left.size() == 0)
		{
			left.push_back(right[right.size() - 1]);
			right.pop_back();
		}

		if (right.size() == 0)
		{
			right.push_back(left[left.size() - 1]);
			left.pop_back();
		}

		left_node = new BVHNode(left);
		right_node = new BVHNode(right);

		AABB left_aabb = left_node->get_aabb();
		AABB right_aabb = right_node->get_aabb();

		aabb = union_aabb(left_aabb, right_aabb);
	}
}

BVHNode::~BVHNode()
{
	if (triangle) { delete triangle; }
	if (left_node) { delete left_node; }
	if (right_node) { delete right_node; }
}

AABB BVHNode::get_aabb()
{
	return aabb;
}

bool BVHNode::is_inside_aabb(const Point& point)
{
	return aabb.x_min < point.x && aabb.y_min < point.y && aabb.x_max > point.x && aabb.y_max > point.y;
}

Trinangle* BVHNode::sample(const Point& point)
{
	if (is_inside_aabb(point))
	{
		if (!triangle && left_node && right_node)
		{
			Trinangle* left_sample = left_node->sample(point);
			Trinangle* right_sample = right_node->sample(point);

			if (!left_sample)
			{
				return right_sample;
			}
			else
			{
				if (!right_sample)
				{
					return left_sample;
				}
				else
				{
					Point l_c = left_sample->get_center();
					float l_dist = (l_c.x - point.x) * (l_c.x - point.x) + (l_c.y - point.y) * (l_c.y - point.y);

					Point r_c = right_sample->get_center();
					float r_dist = (r_c.x - point.x) * (r_c.x - point.x) + (r_c.y - point.y) * (r_c.y - point.y);

					if (l_dist < r_dist)
					{
						return left_sample;
					}
					else
					{
						return right_sample;
					}
				}
			}
		}
		else
		{
			if (triangle && triangle->is_point_inside(point))
			{
				return triangle;
			}
			else
			{
				return NULL;
			}
		}
	}
	else
	{
		return NULL;
	}
}

#include "delaunay.h"
#include "bvh.h"

#include 

void console_log(const std::vector& array)
{
    std::cout << "[";
    for (size_t i = 0; i < array.size(); i++)
    {
        std::cout << array[i] << (i == array.size() - 1 ? "" : ", ");
    }

    std::cout << "]" << std::endl;
}

int main()
{
    std::vector points = { 
        Point(-0.5, 3.0), 
        Point(8.0, -3.5), 
        Point(-7.0, 3.0), 
        Point(2.0, -10.0), 
        Point(7.0, 8.0), 
        Point(8.0, 5.5) 
    };
    std::vector triangle_indices = triangulate(points);

    console_log(triangle_indices);

    std::vector triangles(triangle_indices.size() / 3);
    for (size_t i = 0; i < triangles.size(); i++)
    {
        int a = triangle_indices[3 * i];
        int b = triangle_indices[3 * i + 1];
        int c = triangle_indices[3 * i + 2];
        std::vector vertices = { points[a], points[b], points[c] };
        triangles[i] = new Trinangle(vertices);
    }

    BVHNode* tree = new BVHNode(triangles);
    Point p = Point(0.0f, 0.0f);
    Trinangle* sample_result = tree->sample(p);

    if (sample_result)
    {
        std::cout << sample_result->to_string() << std::endl;
    }
    else
    {
        std::cout << "Empty sample" << std::endl;
    }
}

#include 
#include 

#include "point.h"
#include "delaunay.h"
#include "bvh.h"

using namespace emscripten;

emscripten::val build_triangulation(const emscripten::val &in_coordinates)
{
	// prepare input
	const std::vector coordinates = convertJSArrayToNumberVector(in_coordinates);

	int points_count = coordinates.size() / 2;
	std::vector points(points_count);
	for (size_t i = 0; i < points_count; i++)
	{
		points[i] = Point(coordinates[2*i], coordinates[2*i + 1]);
	}

	std::vector triangles = triangulate(points);

	// prepare output
	emscripten::val view{ emscripten::typed_memory_view(triangles.size(), triangles.data()) };
	emscripten::val result = emscripten::val::global("Int32Array").new_(triangles.size());
	result.call("set", view);

	return result;
}

class BVHNodeWrapper
{
public:
	BVHNodeWrapper(const emscripten::val &in_coordinates);
	BVHNodeWrapper(const emscripten::val &in_coordinates, const emscripten::val &in_triangles);
	~BVHNodeWrapper();

	emscripten::val sample(float x, float y);

private:
	BVHNode* bvh;
};

BVHNodeWrapper::BVHNodeWrapper(const emscripten::val &in_coordinates)
{
	const std::vector coordinates = convertJSArrayToNumberVector(in_coordinates);

	int points_count = coordinates.size() / 2;
	std::vector points(points_count);
	for (size_t i = 0; i < points_count; i++)
	{
		points[i] = Point(coordinates[2*i], coordinates[2*i + 1]);
	}

	std::vector trinagle_indices = triangulate(points);
	int trinagles_count = trinagle_indices.size() / 3;
	std::vector trinagles(trinagles_count);
	for (size_t i = 0; i < trinagles_count; i++)
	{
		int a = trinagle_indices[3 * i];
		int b = trinagle_indices[3 * i + 1];
		int c = trinagle_indices[3 * i + 2];

		std::vector vertices = { points[a], points[b], points[c] };
		trinagles[i] = new Trinangle(vertices);
	}

	bvh = new BVHNode(trinagles);
}

BVHNodeWrapper::BVHNodeWrapper(const emscripten::val &in_coordinates, const emscripten::val &in_triangles)
{
	const std::vector coordinates = convertJSArrayToNumberVector(in_coordinates);
	const std::vector triangles = convertJSArrayToNumberVector(in_triangles);

	int triangles_count = triangles.size() / 3;
	std::vector triangles_array(triangles_count);
	for (size_t i = 0; i < triangles_count; i++)
	{
		int a = triangles[3 * i];
		int b = triangles[3 * i + 1];
		int c = triangles[3 * i + 2];

		std::vector vertices = {
			Point(coordinates[2 * a], coordinates[2 * a + 1]),
			Point(coordinates[2 * b], coordinates[2 * b + 1]),
			Point(coordinates[2 * c], coordinates[2 * c + 1]) };
		triangles_array[i] = new Trinangle(vertices);
	}

	bvh = new BVHNode(triangles_array);
}

BVHNodeWrapper::~BVHNodeWrapper()
{
	delete bvh;
}

emscripten::val BVHNodeWrapper::sample(float x, float y)
{
	Point p = Point(x, y);
	Trinangle* s = bvh->sample(p);
	std::vector to_return(0);
	if (s)
	{
		Point a = s->get_a();
		Point b = s->get_b();
		Point c = s->get_c();

		to_return.insert(to_return.end(), { a.x, a.y, b.x, b.y, c.x, c.y });
	}

	emscripten::val view{ emscripten::typed_memory_view(to_return.size(), to_return.data()) };
	emscripten::val result = emscripten::val::global("Float32Array").new_(to_return.size());
	result.call("set", view);

	return result;
}

EMSCRIPTEN_BINDINGS(delaunay_module)
{
	class_("BVHNode")
		.constructor()
		.constructor()
		.function("sample", &BVHNodeWrapper::sample);
	function("build_triangulation", &build_triangulation);
}

class BVHNodeWrapper
{
public:
	BVHNodeWrapper(const emscripten::val &in_coordinates);
	BVHNodeWrapper(const emscripten::val &in_coordinates, const emscripten::val &in_triangles);
	~BVHNodeWrapper();

	emscripten::val sample(float x, float y);

private:
	BVHNode* bvh;
};

BVHNodeWrapper::BVHNodeWrapper(const emscripten::val &in_coordinates)
{
	const std::vector coordinates = convertJSArrayToNumberVector(in_coordinates);

	int points_count = coordinates.size() / 2;
	std::vector points(points_count);
	for (size_t i = 0; i < points_count; i++)
	{
		points[i] = Point(coordinates[2*i], coordinates[2*i + 1]);
	}

	std::vector trinagle_indices = triangulate(points);
	int trinagles_count = trinagle_indices.size() / 3;
	std::vector trinagles(trinagles_count);
	for (size_t i = 0; i < trinagles_count; i++)
	{
		int a = trinagle_indices[3 * i];
		int b = trinagle_indices[3 * i + 1];
		int c = trinagle_indices[3 * i + 2];

		std::vector vertices = { points[a], points[b], points[c] };
		trinagles[i] = new Trinangle(vertices);
	}

	bvh = new BVHNode(trinagles);
}

BVHNodeWrapper::BVHNodeWrapper(const emscripten::val &in_coordinates, const emscripten::val &in_triangles)
{
	const std::vector coordinates = convertJSArrayToNumberVector(in_coordinates);
	const std::vector triangles = convertJSArrayToNumberVector(in_triangles);

	int triangles_count = triangles.size() / 3;
	std::vector triangles_array(triangles_count);
	for (size_t i = 0; i < triangles_count; i++)
	{
		int a = triangles[3 * i];
		int b = triangles[3 * i + 1];
		int c = triangles[3 * i + 2];

		std::vector vertices = {
			Point(coordinates[2 * a], coordinates[2 * a + 1]),
			Point(coordinates[2 * b], coordinates[2 * b + 1]),
			Point(coordinates[2 * c], coordinates[2 * c + 1]) };
		triangles_array[i] = new Trinangle(vertices);
	}

	bvh = new BVHNode(triangles_array);
}

emscripten::val BVHNodeWrapper::sample(float x, float y)
{
	Point p = Point(x, y);
	Trinangle* s = bvh->sample(p);
	std::vector to_return(0);
	if (s)
	{
		Point a = s->get_a();
		Point b = s->get_b();
		Point c = s->get_c();

		to_return.insert(to_return.end(), { a.x, a.y, b.x, b.y, c.x, c.y });
	}

	emscripten::val view{ emscripten::typed_memory_view(to_return.size(), to_return.data()) };
	emscripten::val result = emscripten::val::global("Float32Array").new_(to_return.size());
	result.call("set", view);

	return result;
}

export class Point {
    private m_x: f32;
    private m_y: f32;

    constructor(in_x: f32 = 0.0, in_y: f32 = 0.0) {
        this.m_x = in_x;
        this.m_y = in_y;
    }

    @inline
    x(): f32 {
        return this.m_x;
    }

    @inline
    y(): f32 {
        return this.m_y;
    }

    toString(): string {
        return "(" + this.m_x.toString() + ", " + this.m_y.toString() + ")";
    }
}

import { Point } from "./point";

const EPSILON: f32 = 0.0001;

class PointExt extends Point {
    private m_index: i32;

    constructor(in_x: f32, in_y: f32, in_index: i32) {
        super(in_x, in_y);

        this.m_index = in_index;
    }

    index(): i32 {
        return this.m_index;
    }
}

class TriangleCircle {
    private m_i: i32;
    private m_j: i32;
    private m_k: i32;

    private m_x: f32;
    private m_y: f32;

    private m_radius_sq: f32;

    constructor(in_i: i32, in_j: i32, in_k: i32, in_x: f32, in_y: f32, in_r: f32) {
        this.m_i = in_i;
        this.m_j = in_j;
        this.m_k = in_k;

        this.m_x = in_x;
        this.m_y = in_y;

        this.m_radius_sq = in_r;
    }

    i(): i32 { return this.m_i; }
    j(): i32 { return this.m_j; }
    k(): i32 { return this.m_k; }

    x(): f32 { return this.m_x; }
    y(): f32 { return this.m_y; }

    radius_sq(): f32 { return this.m_radius_sq; }

    toString(): string {
        return "<" + this.m_i.toString() + ", " + this.m_j.toString() + ", " + this.m_k.toString() + "|" + this.m_x.toString() + ", " + this.m_y.toString() + "|" + this.m_radius_sq.toString() + ">";
    }
}

function maximum(a: f32, b: f32): f32 {
    if(a > b) {
        return a;
    } else {
        return b;
    }
}

function absolute(a: f32, b: f32): f32 {
    if(a > b) {
        return a - b;
    } else {
        return b - a;
    }
}

function build_supertriangle(points: StaticArray): StaticArray {
    let x_min: f32 = f32.MAX_VALUE;
    let y_min: f32 = f32.MAX_VALUE;
    let x_max: f32 = f32.MIN_VALUE;
    let y_max: f32 = f32.MIN_VALUE;

    for(let i = 0, len = points.length; i < len; i++) {
        const p = points[i];
        if (p.x() < x_min) { x_min = p.x(); }
        if (p.x() > x_max) { x_max = p.x(); }
        if (p.y() < y_min) { y_min = p.y(); }
        if (p.y() > y_max) { y_max = p.y(); }
    }

    const dx: f32 = x_max - x_min;
    const dy: f32 = y_max - y_min;

    const d_max: f32 = maximum(dx, dy);
    const x_mid: f32 = x_min + dx * 0.5;
    const y_mid: f32 = y_min + dy * 0.5;

    const vertices = new StaticArray(3);
    vertices[0] = new Point(x_mid - 20.0 * d_max, y_mid - d_max);
    vertices[1] = new Point(x_mid, y_mid + 20.0 * d_max);
    vertices[2] = new Point(x_mid + 20.0 * d_max, y_mid - d_max);
    return vertices;
}

function circumcircle(points: StaticArray, i: i32, j: i32, k: i32): TriangleCircle {
    const point_i = points[i];
    const point_j = points[j];
    const point_k = points[k];

    const x_1 = point_i.x();
    const y_1 = point_i.y();

    const x_2 = point_j.x();
    const y_2 = point_j.y();

    const x_3 = point_k.x();
    const y_3 = point_k.y();

    const y1_y2 = absolute(y_1, y_2);
    const y2_y3 = absolute(y_2, y_3);

    let center_x: f32 = 0.0;
    let center_y: f32 = 0.0;
    let m_1: f32 = 0.0;
    let m_2: f32 = 0.0;
    let mx_1: f32 = 0.0;
    let mx_2: f32 = 0.0;
    let my_1: f32 = 0.0;
    let my_2: f32 = 0.0;

    if (y1_y2 < EPSILON) {
        m_2 = -(x_3 - x_2) / (y_3 - y_2);
        mx_2 = (x_2 + x_3) / 2.0;
        my_2 = (y_2 + y_3) / 2.0;
        center_x = (x_2 + x_1) / 2.0;
        center_y = m_2 * (center_x - mx_2) + my_2;
    } else if (y2_y3 < EPSILON)
    {
        m_1 = -(x_2 - x_1) / (y_2 - y_1);
        mx_1 = (x_1 + x_2) / 2.0;
        my_1 = (y_1 + y_2) / 2.0;
        center_x = (x_3 + x_2) / 2.0;
        center_y = m_1 * (center_x - mx_1) + my_1;
    } else
    {
        m_1 = -(x_2 - x_1) / (y_2 - y_1);
        m_2 = -(x_3 - x_2) / (y_3 - y_2);
        mx_1 = (x_1 + x_2) / 2.0;
        mx_2 = (x_2 + x_3) / 2.0;
        my_1 = (y_1 + y_2) / 2.0;
        my_2 = (y_2 + y_3) / 2.0;
        center_x = (m_1 * mx_1 - m_2 * mx_2 + my_2 - my_1) / (m_1 - m_2);
        center_y = y1_y2 > y2_y3 ? (m_1 * (center_x - mx_1) + my_1) : (m_2 * (center_x - mx_2) + my_2);
    }

    const dx = x_2 - center_x;
    const dy = y_2 - center_y;

    return new TriangleCircle(i, j, k, center_x, center_y, dx*dx + dy*dy);
}

// retun new size of the edges array
function remove_duplicates(edges: StaticArray, in_length: i32): i32 {
    let j = in_length;
    while(j >= 2) {
        const b = edges[--j];
        const a = edges[--j];

        let i = j;
        while(i >= 2) {
            const n = edges[--i];
            const m = edges[--i];

            if((a == m && b == n) || (a == n && b == m)) {
                edges[j] = -1;
                edges[j + 1] = -1;

                edges[i] = -1;
                edges[i + 1] = -1;

                j -= 2;
                break;
            }
        }
    }

    // next remove all -1 values in the array
    let i = -1;  // actual new index
    j = 0;  // pointer to the value in the array
    while(j < in_length) {
        if(edges[j] == -1) {
            j += 1;
        } else {
            edges[++i] = edges[j++];
        }
    }

    return i + 1;
}

function remove_from_array(array: StaticArray, in_length: i32, remove_index: i32): i32 {
    for(let i = remove_index + 1; i < in_length; i++) {
        array[i - 1] = array[i];
    }

    return in_length - 1;
}

export function triangulate(in_points: StaticArray): StaticArray {
    const points_count: i32 = in_points.length;
    if(points_count < 3) {
        return new StaticArray(0);
    }

    // AS does not support closures, so, create array with extended points
    let ext_points = new StaticArray(points_count);
    for(let i = 0; i < points_count; i++) {
        const p = in_points[i];
        ext_points[i] = new PointExt(p.x(), p.y(), i);  // assign in dex to each point
    }

    // sort by using custom comparator
    ext_points.sort((a: PointExt, b: PointExt): i32 => {
        if(a.x() < b.x()) {
            return -1;
        } else if(a.x() > b.x())
        {
            return 1;
        } else {
            return 0;
        }
    });

    // extract indices from sorted array
    let indices = new StaticArray(points_count);
    for(let i = 0; i < points_count; i++) {
        indices[i] = ext_points[i].index();
    }

    const st = build_supertriangle(in_points);

    // create copy of the input points array and extend it by points from the super triangle
    const points = new StaticArray(points_count + 3);
    for(let i = 0; i < points_count; i++) {
        points[i] = in_points[i];
    }
    points[points_count] = st[0];
    points[points_count + 1] = st[1];
    points[points_count + 2] = st[2];

    // create buffers
    const buffers_max_size = 6 * (points_count + 3);
    let open_list = new StaticArray(buffers_max_size);
    let open_list_length = 0;  // manually count the used length

    let closed_list = new StaticArray(buffers_max_size);
    let closed_list_length = 0;

    let edges_list = new StaticArray(6 * buffers_max_size);  // here we place 6 put for each triangle
    let edges_list_length = 0;

    open_list[open_list_length++] = circumcircle(points, points_count, points_count + 1, points_count + 2);

    for(let i = 0; i < points_count; i++) {
        const c: i32 = indices[i];
        const p: Point = points[c];

        edges_list_length = 0;
        for(let j = open_list_length - 1; j >= 0; j--) {
            const t: TriangleCircle = open_list[j];
            const dx: f32 = p.x() - t.x();

            if(dx > EPSILON && dx*dx > t.radius_sq()) {
                open_list_length = remove_from_array(open_list, open_list_length, j);
                closed_list[closed_list_length++] = t;
                continue;
            }

            const dy: f32 = p.y() - t.y();
            if(dx*dx + dy*dy - t.radius_sq() > EPSILON) {
                continue;
            }

            open_list_length = remove_from_array(open_list, open_list_length, j);
            edges_list[edges_list_length++] = t.i();
            edges_list[edges_list_length++] = t.j();
            edges_list[edges_list_length++] = t.j();
            edges_list[edges_list_length++] = t.k();
            edges_list[edges_list_length++] = t.k();
            edges_list[edges_list_length++] = t.i();
        }
        
        edges_list_length = remove_duplicates(edges_list, edges_list_length);

        let k: i32 = edges_list_length;
        while(k >= 2) {
            const b = edges_list[--k];
            const a = edges_list[--k];

            open_list[open_list_length++] = circumcircle(points, a, b, c);
        }
    }

    for(let i = 0; i < open_list_length; i++) {
        closed_list[closed_list_length++] = open_list[i];
    }

    const triangles = new StaticArray(closed_list_length * 3);
    let t_index: i32 = 0;
    for(let i = 0; i < closed_list_length; i++) {
        const t = closed_list[i];
        if(t.i() < points_count && t.j() < points_count && t.k() < points_count) {
            triangles[3*t_index] = t.i();
            triangles[3*t_index + 1] = t.j();
            triangles[3*t_index + 2] = t.k();

            t_index += 1;
        }
    }
    return triangles.slice>(0, 3*t_index);
}

import { Point } from "./point";

@inline
function maximum(a: f32, b: f32): f32 {
    if(a > b) { return a;
    } else { return b; }
}

@inline
function minimum(a: f32, b: f32): f32 {
    if(a > b) { return b;
    } else { return a; }
}

@inline
function square(value: f32): f32 {
    return value * value;
}

class AABB {
    private m_x_min: f32;
    private m_y_min: f32;

    private m_x_max: f32;
    private m_y_max: f32;

    constructor(in_x_min: f32 = 0.0, in_y_min: f32 = 0.0, in_x_max: f32 = 0.0, in_y_max: f32 = 0.0) {
        this.m_x_min = in_x_min;
        this.m_y_min = in_y_min;

        this.m_x_max = in_x_max;
        this.m_y_max = in_y_max;
    }

    @inline
    x_min(): f32 { return this.m_x_min; }

    @inline
    y_min(): f32 { return this.m_y_min; }

    @inline
    x_max(): f32 { return this.m_x_max; }

    @inline
    y_max(): f32 { return this.m_y_max; }

    toString(): string {
        return "|" + this.m_x_min.toString() + ", " + this.m_y_min.toString() + ", " + this.m_x_max.toString() + ", " + this.m_y_max.toString() + "|";
    }
}

export class Triangle {
    private m_a: Point;
    private m_b: Point;
    private m_c: Point;

    private m_aabb: AABB;
    private m_cente
    
            
© Habrahabr.ru