Algorithm – Kiểm tra một điểm nằm trên đoạn thẳng

Determine Point on LineCó nhiều cách để kiểm tra một điểm có thuộc đường thằng (tương tự với đoạn thẳng) hay không: bằng cách sử dụng các công thức hình học hoặc thuật toán vẽ đường thẳng,… Ngoài những cách trên, tôi sẽ giới thiệu một phương pháp đơn giản nhất là sử dụng phép so sánh góc để giải quyết vấn đề này.

Trong demo sau, khi bạn di chuyển chuột ngang lên trên đoạn thẳng, bạn sẽ đoạn thẳng chuyển sang màu đỏ.

Xem Demo.

Ý tưởng: Ta có đoạn thẳng AB tạo nên góc α (so với phương ngang hoặc phương bất kì), và mọi điểm thuộc AB đều tạo nên góc α so với phương ngang.

Hay nói cách khác, ta xem đoạn thẳng AB là đường chéo của một tam giác vuông ABM. Tỉ lệ giữa hai cạnh góc vuông của tam giác này sẽ bằng với tỉ lệ hai cạnh góc vuông tạo bởi tam giác vuông AXN. Minh họa như hình dưới đây:

Determine Point on Line

Như vậy việc xác định một điểm X có thuộc AB hay không chỉ cần dựa vào 2 yếu tố:

(1)   X phải nằm trong vùng hình chữ nhật được tạo bởi đường chéo AB (ngoại tiếp tam giác ABM).

(2)   Góc XAN và BAM phải bằng nhau.

Ngoài ra, do việc so sánh là kiểu số thực và có thể do độ rộng của đoạn thẳng khác nhau nên ta cần chấp nhận một giá trị sai số EPSILON nào đó.

Muốn chính xác hơn khi độ rộng của đoạn thẳng thay đổi, bạn có thể tính góc sai số cho phép bằng cách dựa vào ½ độ rộng đoạn thẳng và khoảng cách AX để tính. Tuy nhiên, điều này không quan trọng lắm và làm cho việc kiểm tra tốn thêm chi phí.

Để đơn giản, ta sẽ tính tỉ lệ (tan) thay vì tính góc α:

Line.prototype.contains = function(x, y) {
	if( 	x < Math.min(this.handler1.cx,this.handler2.cx) ||
		x > Math.max(this.handler1.cx,this.handler2.cx) ||
		y < Math.min(this.handler1.cy,this.handler2.cy) ||
		y > Math.max(this.handler1.cy,this.handler2.cy))
		return false;
	var dx = this.handler1.cx-this.handler2.cx;
	var dy = this.handler1.cy-this.handler2.cy;
    	var tan1 = Math.abs(dy/dx);
	var tan2 = Math.abs((y-this.handler1.cy)/(x-this.handler1.cx));
	return Math.abs(tan1 - tan2) < EPSILON;
}

Mã nguồn hoàn chỉnh:

<html>
<head>
  <script>
	/***************** Circle ***************/

function Circle(cx,cy,radius) {
    this.radius = radius? radius : Math.floor(Math.random() * 30) + 30;

    this.cx = cx ? cx : Math.floor(Math.random() * 400);
    this.cy = cy ? cy : Math.floor(Math.random() * 400);

    this.color = "green";
}
Circle.prototype.resetColor = function() {
    this.color = "green";
}
Circle.prototype.draw = function(context) {
    context.beginPath();
    context.fillStyle = this.color;
    context.arc(this.cx, this.cy, this.radius, 0, Math.PI * 2, true);
    context.closePath();
    context.fill();
}
Circle.prototype.setPosition = function(x, y) {
    this.cx = x + this.radius;
    this.cy = y + this.radius;
}
Circle.prototype.contains = function(x, y) {
    var dx = this.cx - x;
    var dy = this.cy - y;

    return Math.sqrt(dx * dx + dy * dy) <= this.radius;
}

/***************** Line ***************/

function Line(x1,y1,x2,y2) {
    this.color = "black";
	this.handler1 = new Circle(x1,y1,5);
	this.handler2 = new Circle(x2,y2,5);
}
Line.prototype.resetColor = function() {
    this.color = "black";
}
Line.prototype.contains = function(x, y) {
	if(	x < Math.min(this.handler1.cx,this.handler2.cx) ||
		x > Math.max(this.handler1.cx,this.handler2.cx) ||
		y < Math.min(this.handler1.cy,this.handler2.cy) ||
		y > Math.max(this.handler1.cy,this.handler2.cy))
		return false;
	var dx = this.handler1.cx-this.handler2.cx;
	var dy = this.handler1.cy-this.handler2.cy;
    var tan1 = Math.abs(dy/dx);
	var tan2 = Math.abs((y-this.handler1.cy)/(x-this.handler1.cx));

	return Math.abs(tan1 - tan2) < EPSILON;
}
Line.prototype.draw = function(context) {

	context.strokeStyle = this.color;
	context.beginPath();
	context.moveTo(this.handler1.cx,this.handler1.cy);
	context.lineTo(this.handler2.cx,this.handler2.cy);
	context.closePath();
	context.stroke();
	// draw handlers
	this.handler1.draw(context);
	this.handler2.draw(context);
}
 /************** Main *************/

var EPSILON = 0.01;
var _canvas;
var _context;
var _movingShape = false;
var _line;

function canvas_mousedown(e) {

    var x = e.pageX - _canvas.offsetLeft;
    var y = e.pageY - _canvas.offsetTop;
    if (_line.handler1.contains(x, y)) {
        _movingShape = _line.handler1;
    }else if (_line.handler2.contains(x, y)) {
        _movingShape = _line.handler2;
    }
}

function canvas_mousemove(e) {
	var x = e.pageX - _canvas.offsetLeft;
	var y = e.pageY - _canvas.offsetTop;

	if (_movingShape) {
        _movingShape.setPosition(x, y);
    }

	if(_line.contains(x,y))
		_line.color = "red";
	else
		_line.resetColor();

	draw();
}

function canvas_mouseup(e) {
    _movingShape = null;
}

function clear() {
    _context.clearRect(0, 0, _canvas.width, _canvas.height);
}

function draw() {
    clear();
    _line.draw(_context);
}

window.onload = function(){
	_canvas = document.getElementById("canvas");
	_context = _canvas.getContext("2d");

	_line = new Line(100, 100, 200, 200);
	_canvas.onmousedown = canvas_mousedown;
	_canvas.onmousemove = canvas_mousemove;
	_canvas.onmouseup = canvas_mouseup;

	draw();
}
  </script>
</head>
<body>
<h1>Sorting Visualizations:</h1>
<hr/>
<canvas id="canvas" width="400px" height="400px" style="border: 1px solid"></canvas>
</body>
</html>

YinYang’s Blog

Bài này đã được đăng trong Algorithms, General, HTML5 - Canvas và được gắn thẻ . Đánh dấu đường dẫn tĩnh.

2 bình luận về “Algorithm – Kiểm tra một điểm nằm trên đoạn thẳng”

Đã đóng bình luận.